说明/背景

此文仅为作者的个人见解，原题为第十六届蓝桥杯省赛c++b组原题。可以在以下链接找到对应的评测：https://www.luogu.com.cn/problem/list?tag=363%7C62&page=1

难度参考洛谷评测

1.密密摆放入门

题目描述

小蓝有一个大箱子，内部的长宽高分别是 200、250、240（单位：毫米），他要用这个大箱子来放一些同样大小的小盒子，小盒子的外部长宽高分别是 30、40、50（单位：毫米）。小盒子允许从各个方向旋转（包括可以平放和倒放）。请问小蓝最多可以在一个大箱子里面放多少个小盒子
输入格式：无。
输出格式：直接填答案。

思路

语法题。箱子容积/单个盒子体积向下取整即可。时间复杂度O(1)。

代码

void solve()
{
   	cout << (200 * 250 * 240) / (30 * 40 * 50) << endl;
    return ;
}

2.脉冲强度之和普及-

题目描述

在蓝桥电子工坊，工程师小蓝正在设计一款智能脉冲生成器，用于驱动一种新型设备。该设备的运行依赖于特定的脉冲强度，用正整数 p 表示，其必须满足以下三个条件：
1.可由连续 10 个正整数之和组成：即存在一个正整数 k，使得脉冲强度 p=k+(k+1)+(k+2)+⋯+(k+9)。
2.各个数位上的数字都相同：例如 1111、22222、333333 等。
3.数值不超过 20255202：即 1≤p≤20255202。
通过计算所有符合条件的脉冲强度之和，小蓝能够优化设备运行模式。对此，请帮助他计算这一总和。
输入格式：无。
输出格式：直接写答案。

思路

思维题。考虑第一个条件，反推k=(p - 45) / 10 且 (p - 45) % 10 != 0。第二个条件，可以通过两重for循环，第一层为1、11、111...。第二层为1--9 则 i*j就可以完成模拟各个位数数字相同，且根据第三个条件，只需要满足i*j<20255202即可。时间复杂度O(n^2)。

代码

void solve()
{
   	int n = 20255202;
   	int ans = 0;
    for (int i = 1 ; i <= n ; i = i * 10 + 1 )
    {
        for (int j = 1 ; j * i <= n && j < 10 ; j ++ )
        {
            if (i * j <= 45) continue;
            int num = i * j; 
            if (!((num - 45) % 10))
                ans += num;
        }
    }
    
    cout << ans << endl;
    return ;
}

3.25之和入门

题目描述

小蓝最近对求和很着迷，给定一个正整数 n，他想求从 n 开始的连续 25 个整数的和，即 n+(n+1)+(n+2)+⋯+(n+24)，请帮帮他吧。
输入格式：输入一行包含一个正整数 $n$ 。
输出格式：输出一行包含一个整数表示答案。

示例

输入#1：1
输出#1：325
输入#2：10
输出#2：2800
数据规模：
对于 40% 的评测用例，1≤n≤100；
对于所有评测用例，1≤n≤10000。

思路

语法题。累加即可。时间复杂度O(n)。

代码

void solve()
{
   	int n;
   	cin >> n;
   	int ans = 0;
   	for (int i = n ; i < n + 25 ; i ++ ) ans += i;
   	cout << ans << endl;
    return ;
}

4.旗帜普及-

题目描述

小蓝要画一个 LANQIAO 图形，并把这个图形做成一个旗帜。图形的形状为一个 h×w 的矩形，其中 h 表示图形的高，w 表示图形的宽。当 h=5,w=10 时，图形如下所示：

图形的规律是：第一行用 LANQIAO 重复填入，第二行开始，每行向左移动一个字符，用 LANQIAO 重复填入。
小蓝需要把图形中的每个字母都剪出来，以粘贴到旗帜上，他想知道，给定图形的高和宽，图形中有多少个 A。
输入格式：输入的第一行包含两个正整数 $h, w$ ，用一个空格分隔。
输出格式：输出一行包含一个整数表示答案。

示例

输入#1 ： 5 10
输出#1：14
数据规模：
对于 30% 的评测用例，h=1，1≤w≤20；
对于 60% 的评测用例，1≤h,w≤20；
对于所有评测用例，1≤h,w≤100。

思路

bfs暴力。通过bfs按照LANQIAO的顺序来布置指定范围的图形。可以取每个字符ascll码的绝对值来优化计算过程。时间复杂度O(nm)。

代码

const int N = 110;
int g[N][N];
int dx[] = {1 , 0 , -1 , 0} , dy[] = {0 , -1 , 0 , 1};
bool flag[N][N];
int n , m;

void bfs(int x , int y)
{
    queue<PII> q;
    q.push({x , y});
    flag[x][y] = true;
    g[x][y] = 1;
    
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        
        x = t.first , y = t.second;
        
        for (int i = 0 ; i < 4 ; i ++ )
        {
            int xx = x + dx[i] , yy = y + dy[i];
            if (xx < 1 || yy < 1 || xx > n || yy > m) continue;
            if (g[xx][yy] || flag[xx][yy]) continue;
            
            flag[xx][yy] = true;
            
            g[xx][yy] = (g[x][y] + 1) % 8;
            if (!g[xx][yy]) g[xx][yy] = 1;
            q.push({xx , yy});
        }
    }
} 

void solve()
{
    cin >> n >> m;
   	
    bfs(1 , 1);   	
    
    int ans = 0;   	
    for (int i = 1 ; i <= n ; i ++ )
        for (int j = 1 ; j <= m ; j ++ )
            if (g[i][j] == 2 || g[i][j] == 6) ans ++;
            
    cout << ans << endl;
    return ;
}

5.消消乐普及-

题目描述

小蓝正在玩一个叫“一维消消乐”的游戏。游戏初始时给出一个长度为n的字符串S=S₀S₁…Sₙ₋₁，字符串只包含字符A和B。小蓝可以对这个字符串进行若干次操作，每次操作可以选择两个下标i，j∈[0，n - 1]，如果i<j且Sᵢ=A且Sⱼ=B，小蓝就可以把它们同时消掉。小蓝想知道在经过若干次操作后，直到无法对字符串继续进行操作时，字符串最多剩下多少个字符。
输入格式：输入一行包含一个长度为n的字符串S。
输出格式：输出一行包含一个整数表示答案。

示例

输入#1：BABAABBA
输出#1：4
样例说明：样例说明：先消掉(S₁，S₆)，再消掉(S₄，S₅)，此时剩下BBAA，无法继续进行操作。
数据规模：
对于10%的评测用例，1≤n≤20；
对于20%的评测用例，1≤n≤100；
对于50%的评测用例，1≤n≤10000；
对于所有评测用例，1≤n≤10⁶。

思路

双指针+贪心。由题可知：只能消去子串为"AB"，那么可以贪心的优先消去尽量前的A，通过双指针优化时间。时间复杂度：O(n)。

代码

void solve()
{
    string s;
    cin >> s;
    int l = 0 , r = s.size() - 1;
    
    int nums = 0;
    while(l < r)
    {
    	if (s[l] == 'A')
    	{
    		if (s[r] == 'B')
    		{
    			nums += 2;
    			l ++ , r --;
                continue;
            }
            else 
            {
                r --;
                continue;
            }
        }
        else l ++;
    }
    
    cout << s.size() - nums << endl;
    return ;
}

6.数列差分普及-

题目描述

小蓝有两个长度均为n的数列A={a₁，a₂，…，aₙ}和B={b₁，b₂，…，bₙ}，将两个数列作差定义为C=A-B={c₁=a₁-b₁，c₂=a₂-b₂，…，cₙ=aₙ-bₙ}。小蓝将对数列B进行若干次操作，每次操作可以将数列B中的任意一个数更改为任意一个整数。在进行完所有操作后，小蓝可以按任意顺序将数列B重排，之后再计算数列C。小蓝想知道，最少操作多少次可以使得数列C中的所有数都为正整数。
输入格式：
输入的第一行包含一个正整数n；
第二行包含n个整数a₁，a₂，…，aₙ，相邻整数之间使用一个空格分隔。
第三行包含n个整数b₁，b₂，…，bₙ，相邻整数之间使用一个空格分隔。
输出格式：
输出一行包含一个整数表示答案。

示例

输入#1：
4
22 31 12 14
3 19 27 44
输出#1：1
说明：其中一种方案：将44改为0，重新排列B为{19，27，3，0}，使得数列C={3，4，9，14}均为正整数。
数据规模：
对于30%的评测用例，n≤10；
对于所有评测用例，1≤n≤10⁵，-10⁹≤aᵢ≤10⁹，-10⁹≤bᵢ≤10⁹。

思路

贪心+双指针。题目意思也就是每一个对应的i 都有ai > bi。
且可以任意的排列b，也就是可以任意的排列a、b。
那么就是尽可能的使得大的a消去小的b，将a、b按照从小到大的顺序排列，依次对照a、b即可(因为如果ai > bi 则 ai 一定大于b.front ~ bi)。
时间复杂度：O(nlogn)。

代码

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1) , b(n + 1);
    for (int i = 1 ; i <= n ; i ++ ) cin >> a[i];
    for (int i = 1 ; i <= n ; i ++ ) cin >> b[i];
    
    sort(all(a)) , sort(all(b));

    int index = 1;
    for (int i = 1 ; i <= n ; i ++ )
        if (a[i] > b[index]) index ++;

    cout << n - index + 1 << endl;
    return ;
}

7.书上寻宝普及/提高-

题目描述

小蓝正在一棵含有 n 个结点的树的根结点 1 上，他准备在这棵树上寻宝。结点 i 上有一个物品，价值为 w i 。然而，小蓝每次寻宝只能从根节点出发走不超过 k 步，每步只能选择走 1 条边或者 2 条边，之后会自动拾取最终停留的结点上的物品并被传送回根结点。请求出小蓝最终能获得的物品的总价值。
输入格式：输入的第一行包含两个正整数n，k，用一个空格分隔。第二行包含n个正整数w₁，w₂，…，wₙ，相邻整数之间使用一个空格分隔。接下来n - 1行，每行包含两个正整数uᵢ，vᵢ，用一个空格分隔，表示结点uᵢ和结点vᵢ之间有一条边。
输出格式：输出一行包含一个整数表示答案。

示例

输入#1：
8 2
6 3 3 1 5 4 3 4
1 2
2 3
2 4
4 5
5 6
6 7
7 8
输出#1：22
说明：
走0步能到的结点：1；
走1步能到的结点：2，3，4；
走2步能到的结点：3，4，5，6；
因此能到的结点为：1，2，3，4，5，6。
能获得的总价值为22。
数据规模：
对于20%的评测用例，1≤n≤15；
对于所有评测用例，0≤k<n≤10⁵，1≤wᵢ≤10⁶，1≤uᵢ，vᵢ≤n。

思路

bfs暴力。最多走k步，且每步限制在1--2条边。其实就是只要距离根节点边数小于2 * k 的点我们都可以走到。
那么就很简单了，遍历一遍图，标记所有能走到的点最后累加即可。
通过list标记k步内能走到的结点，flag标记目前访问过的结点。时间复杂度O(n)。

代码

const int N = 2e5 + 10;

int e[N] , ne[N] , idx , h[N];
int w[N] , n , k;
bool flag[N] , list[N];

void add(int a , int b)
{
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++;
}

void bfs(int s)
{
    queue<PII> q;
    q.push({0 , s});
    flag[s] = true;
    list[s] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        int deth = t.first , index = t.second;

        if (deth >= k * 2) continue;

        for (int i = h[index] ; ~i ; i = ne[i])
        {
            int j = e[i];

            if (!flag[j])
            {
                list[j] = true;
                flag[j] = true;
                q.push({deth + 1 , j});
            }
        }
    }
}

void solve()
{
    memset(h , -1 , sizeof h);
    cin >> n >> k;
    for (int i = 1 ; i <= n ; i ++ ) cin >> w[i];

    for (int i = 1 ; i < n ; i ++ ) 
    {
        int a , b;
        cin >> a >> b;
        add(a , b);
        add(b , a);
    }

    bfs(1);

    int ans = 0;
    for (int i = 1 ; i <= n ; i ++ ) 
        if (list[i]) ans += w[i];
    
    cout << ans << endl;
    return ;
}

8.翻转硬币

题目描述

给定 n 行 m 列共 n×m 个硬币，对于任意一个硬币，我们将其价值视为与其相邻（指上、下、左、右相邻）的硬币中与其正反相同的硬币数的平方。你可以进行任意次操作，每次可以选择任意一行并将该行的硬币全部翻转。求所有硬币的价值之和最大可能是多少。
输入格式：
输入的第一行包含两个正整数 n,m，用一个空格分隔。
接下来 n 行，每行包含 m 个 0 或 1，表示给定的 n×m 个硬币。
输出格式：输出一行包含一个整数表示答案。