农夫约翰的奶酪块

知识点

解题思路

一个1 * 1 * N的方块的插入方向有三种：
- 沿x轴方向
- 沿y轴方向
- 沿z轴方向
所以用三个数组表示某一个面背后的的缺口的数量
如果某一个面背后缺口的数量已经达到n了，那么说明可以增加一种插入方案

实现代码

#include <bits/stdc++.h>
using namespace std;

const int N= 1100;

int a[N][N], b[N][N], c[N][N];
int n, m;


int main(){
    int res = 0;
    cin >> n >> m;
    for(int i = 0; i < m; i ++){
        int x, y, z;
        cin >> x >> y >> z;
        if(++ a[x][y] == n)
            res ++;
        if(++ b[x][z] == n)
            res ++;
        if(++ c[y][z] == n)
            res ++;

        cout << res << endl;
    }

    return 0;
}

哞叫时间

知识点

枚举
printf和scanf函数
- printf函数
- scanf函数

解题思路

根据题意，我们要统计出现次数大于等于m次的abb子串
总体思路：将字符串中的每个字符进行修改操作，之后遍历以这个字符分别为最后一个字符，倒数第二个字符，和第一个字符的长度为3的子串
- 时间复杂度：$\Omega(25 \times N)$
初始化两个数组：
- int cnt[a][b]：记录每个abb型子串出现的次数
- int st[N][N]：记录每个abb型是否可以作为答案的状态
建立update函数
- 输入参数为：int l, int r, int v
- 对该范围内长度为3的子串的cnt数组进行更新，对于满足条件的abb数组在其cnt数值上+ v
遍历每个字符，将字符修改为除自己其他25个英文字母，对上述的三种子串利用update函数进行判断
最后遍历cnt和st数组，输出res和符合条件的abb型子串

实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 20200, M = 26;

char s[N];
int n, m;
int cnt[M][M];
int st[M][M];

void update(int l, int r, int v){
    l = max(l, 0), r = min(r, n - 1);
    for(int i = l; i + 2 <= r; i ++){
        char a = s[i], b = s[i + 1], c = s[i + 2];
        if(a != b && b == c){
            cnt[a][b] += v;
            if(cnt[a][b] == m)
                st[a][b] = 1;

        }
    }
}

int main(){
    cin >> n >> m >> s;


    for(int i = 0; i < n; i ++)
        s[i] -= 'a';
    // 先统计原串
    update(0, n - 1, 1);
    // 再统计修改一个字符之后的abb型数量
    for(int i = 0; i < n; i ++){
        char t = s[i];
        update(i - 2, i + 2, -1);
        for(int j = 0; j < 26; j ++){
            if(j != t){
                s[i] = j;
                update(i - 2, i + 2, 1);
                update(i - 2, i + 2, -1);
            }
        }

        s[i] = t;
        update(i - 2, i + 2, 1);
    }

    int ans = 0;

    for(int i = 0; i < 26; i ++)
        for(int j = 0; j < 26; j ++)
            if(st[i][j])
                ans ++;

    cout << ans << endl;
    for(int i = 0; i < 26; i ++)
        for(int j = 0; j < 26; j ++)
            if(st[i][j])
                printf("%c%c%c\n", i + 'a', j + 'a', j + 'a');


    return 0;

}

蛋糕游戏

知识点

求前缀和

解题思路

我们设定贝茜和埃尔茜分别为A和B
最后一步一定是由A来完成的，因为1个蛋糕是奇数，只能通过两个蛋糕合并为一个蛋糕，然后吃掉
所以，我们知道，在理想情况下（B不会吃掉A合并的蛋糕）除了A最开始合并吃掉的2个蛋糕，其余时间都是B吃一个A吃一个成对出现，所以A会比B多吃两个蛋糕
可得：A吃掉的蛋糕数为$\frac{N}{2} + 1$，B吃掉的蛋糕数为$\frac{N}{2} - 1$

如果两个大括号内数的和等于$\frac{N}{2} - 1$的话，那么B是一定可以吃掉的
- 因为，在理想情况下，B可以吃掉$\frac{N}{2} - 1$个蛋糕，倘若其中一个蛋糕被A合并了，那么B可以尽早完成吃掉$\frac{N}{2} - 1$个蛋糕的任务，并最终可能吃$\geq \frac{N}{2} - 1$个蛋糕
对于B吃的蛋糕，我们将从两边挑选最大的蛋糕给B吃。给定中间序列$\frac{N}{2} + 1$个蛋糕，使用$S_{min}$来表示这个$\frac{N}{2} + 1$个蛋糕大小和的最小值。综上，B吃的蛋糕可以表示为：$B \geq T - S_{min}$
接下俩继续探究A能否吃$\frac{N}{2} + 1$个蛋糕

在游戏开始时，我们假定A首先吃掉中间的两个蛋糕，随后蛋糕序列的样式变为上述图片中所显示的。
在接下来中，B吃掉一个左右任一序列中一个蛋糕，A随即吃掉另一序列（右左）中的一个蛋糕。这样的吃法可以保证A吃掉$\frac{N}{2} - 1$个蛋糕。
最后，加上最开始吃掉的2个蛋糕，A一共吃掉了$\frac{N}{2} + 1$个蛋糕
继续分析，不论B怎么选择，A一定可以吃掉$\frac{N}{2} + 1$个蛋糕，并且这些蛋糕大小加和最小，即为$S_{min}$。
综上，我们构造出了一种策略，使得A可以吃$\frac{N}{2} + 1$个蛋糕，并且大小加和至少为$S_{min}$。所以，B吃的蛋糕又可以表示为：$B \leq T - S_{min}$

实现代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 5e5 + 100;


int n;
LL s[N];

int main(){

    int T;
    cin >> T;
    // 刺挠
    while(T --){
        cin >> n;
        LL a = 1e15;
        int l = n / 2 + 1;
        for(int i = 1; i <= n; i ++){
            int x;
            cin >> x;
            s[i] = s[i - 1] + x;
            if(i >= l)
                a = min(a, s[i] - s[i - l]);
        }
        cout << a << " " << s[n] - a << endl;
    }

    return 0;
}

2025第一周蓝桥杯每日一题

农夫约翰的奶酪块

知识点

解题思路

实现代码

哞叫时间

知识点

解题思路

实现代码

蛋糕游戏

知识点

解题思路

实现代码

Enjoy Reading This Article?