蓝桥杯每日一题--第一周（包含五题）
AcWing 6122. 农夫约翰的奶酪块
农夫约翰有一块立方体形状的奶酪，它位于三维坐标空间中，从 (0,0,0)(0,0,0) 延伸至 (N,N,N)(N,N,N)。
农夫约翰将对他的奶酪块执行一系列 QQ 次更新操作。
对于每次更新操作，农夫约翰将从整数坐标 (x,y,z)(x,y,z) 到 (x+1,y+1,z+1)(x+1,y+1,z+1) 处切割出一个 1×1×11×1×1 的奶酪块，其中 0≤x,y,z<N0≤x,y,z<N。
输入保证在农夫约翰切割的位置上存在一个 1×1×11×1×1 的奶酪块。
由于农夫约翰正在玩牛的世界，当下方的奶酪被切割后，重力不会导致上方的奶酪掉落。
在每次更新后，输出农夫约翰可以将一个 1×1×N1×1×N 的砖块插入奶酪块中的方案数，使得砖块的任何部分都不与剩余的奶酪重叠。
砖块的每个顶点在全部三个坐标轴上均必须具有整数坐标，范围为 [0,N][0,N]。
农夫约翰可以随意旋转砖块。
输入格式
输入的第一行包含 NN 和 QQ。
以下 QQ 行包含 xx，yy 和 zz，为要切割的位置的坐标。
输出格式
在每次更新操作后，输出一个整数，为所求的方案数。
数据范围
2≤N≤10002≤N≤1000,
1≤Q≤2×1051≤Q≤2×105,
0≤x,y,z<N输入样例：
2 5 0 0 0 1 1 1 0 1 0 1 0 0 1 1 0输出样例：
0 0 1 2 5样例解释
在前三次更新操作后，[0,1]×[0,2]×[0,1][0,1]×[0,2]×[0,1] 范围的 1×2×11×2×1 砖块与剩余的奶酪不重叠，因此它贡献了答案。
思路：本题是一个在三维空间的题目，目前我们接触最多的就是二维空间上面的题目，因此我们需要将三维空间拆分为二维空间，因为三维空间有三个维度，分别为x-y平面，x-z平面，y-z平面，我们可以用三个二维数组来表示。对于如何统计答案，形如式子（if (a[x][y] == n)）表示在这个平面上连续切割了n个方块，此时就可以将答案加1。(三个维度都需要进行判断)
#include<iostream>
using namespace std;
const int N = 1010;
int a[N][N], b[N][N], c[N][N];
int main() {
int n, q;
cin >> n >> q;
int res = 0;
while (q --) {
int x, y, z;
cin >> x >> y >> z;
a[x][y] ++;
b[y][z] ++;
c[x][z] ++;
if (a[x][y] == n) res ++;
if (b[y][z] == n) res ++;
if (c[x][z] == n) res ++;
cout << res << endl;
}
}AcWing 6123. 哞叫时间
农夫约翰正在试图向埃尔茜描述他最喜欢的 USACO 竞赛，但她很难理解为什么他这么喜欢它。
他说「竞赛中我最喜欢的部分是贝茜说 『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。
埃尔茜仍然不理解，所以农夫约翰将竞赛以文本文件形式下载，并试图解释他的意思。
竞赛被定义为一个长度为 NN 的小写字母字符串。
一种哞叫一般地定义为子串 cicjcjcicjcj，其中某字符 cici 之后紧跟着 22 个某字符 cjcj，且 ci≠cjci≠cj。
根据农夫约翰的说法，贝茜哞叫了很多，所以如果某种哞叫在竞赛中出现了至少 FF 次，那可能就是贝茜发出的。
然而，农夫约翰的下载可能损坏，文本文件可能存在至多一个字符与原始文件不同。
将可能的误差考虑在内，输出所有可能是贝茜发出的哞叫，按字母顺序排序。
输入格式
输入的第一行包含 NN 和 FF，表示字符串的长度以及贝茜的哞叫的频次下限。
第二行包含一个长度为 NN 的小写字母字符串，表示竞赛。
输出格式
输出可能是贝茜发出的哞叫的数量，以下是按字典序排序的哞叫列表。
每行输出一种哞叫。
数据范围
3≤N≤200003≤N≤20000,
1≤F≤N1≤F≤N输入样例1：
10 2 zzmoozzmoo输出样例1：
1 moo样例1解释
在这个样例中，任何字符变化都不会影响答案。
唯一贝茜可能发出的哞叫是
moo。输入样例2：
17 2 momoobaaaaaqqqcqq输出样例2：
3 aqq baa cqq样例2解释
在这个样例中，位置 88（从零开始索引）的
a可能是由b损坏导致的，这使得baa成为一种贝茜发出两次的可能的哞叫。此外，位置 1111 的
q可能是由c损坏导致的，这使得cqq成为一种贝茜可能的哞叫。
aqq可以通过将c换成a来达到。输入样例3：
3 1 ooo输出样例3：
25 aoo boo coo doo eoo foo goo hoo ioo joo koo loo moo noo poo qoo roo soo too uoo voo woo xoo yoo zoo
思路：枚举每一个长度为3的字符串，设为abb，首先判断原字符串中有多少个abb，然后再判断是否能够改变一个字符，再加一个abb。最后判断abb出现的次数是否至少是f个即可。
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, f; cin >> n >> f;
string s; cin >> s;
vector<string> res;
// 形如abb形，此时令c1为a，c2为b
for (char c1 = 'a'; c1 <= 'z'; c1 ++) {
for (char c2 = 'a'; c2 <= 'z'; c2 ++) {
if (c1 == c2) continue;
int cnt = 0, flag = 0;
auto t = s;
// 原本有多少个
for (int i = 0; i < n - 2; i ++) {
if (t[i] == c1 && t[i + 1] == c2 && t[i + 2] == c2) {
cnt ++;
t[i] = t[i + 1] = t[i + 2] = '#';
}
}
// 是否能变
for (int i = 0; i < n - 2; i ++) {
if (t[i] == '#' || t[i + 1] == '#' || t[i + 2] == '#') continue;
// axb || xbb || abx 三种情况可以变成 abb
if ((t[i + 1] == t[i + 2] && t[i + 1] == c2) || (t[i] == c1 && t[i + 2] == c2) || (t[i] == c1 && t[i + 1] == c2)) {
flag = 1;
}
}
if (cnt + flag >= f) {
string x = "";
x += string(1, c1) + string(2, c2);
res.push_back(x);
}
}
}
cout << res.size() << endl;
for (auto x: res) {
cout << x << endl;
}
}AcWing 6118. 蛋糕游戏
贝茜和埃尔茜发现了一行 NN 个蛋糕（NN 为偶数），大小依次为 a1,a2,…,aNa1,a2,…,aN。
两头奶牛都想吃到尽可能多的蛋糕。
但是，作为非常文明的奶牛，她们决定玩一个游戏来分割蛋糕！
游戏在两头奶牛之间轮流进行回合。
每个回合进行以下两者之一：
- 贝茜选择两个相邻的蛋糕并将它们堆叠起来，制造大小为两者大小之和的一个新蛋糕。
- 埃尔茜选择最左边或最右边的蛋糕藏起来。
当只剩下一个蛋糕时，贝茜吃掉它，而埃尔茜吃掉她藏起来的所有蛋糕。
如果两头奶牛都采取最优策略以最大化她们吃到的蛋糕量，并且贝茜先进行回合，那么每头奶牛将会吃到多少蛋糕？
输入格式
每个测试点包含 TT 个独立的测试用例。
每个测试用例的格式如下。
第一行包含 NN。
下一行包含 NN 个空格分隔的整数 a1,a2,…,aNa1,a2,…,aN。
输出格式
对于每个测试用例，输出一行，包含 bb 和 ee，表示贝茜和埃尔茜在两头奶牛都采取最优策略的情况下分别吃到的蛋糕量。
数据范围
1≤T≤101≤T≤10,
2≤N≤5×1052≤N≤5×105,
1≤ai≤1091≤ai≤109,
输入保证一个测试点中的所有 NN 之和不超过 106106。输入样例：
2 4 40 30 20 10 4 10 20 30 40输出样例：
60 40 60 40样例解释
对于第一个测试用例，在最优策略下，
- 贝茜将堆叠中间两个蛋糕。现在蛋糕的大小为 [40,50,10][40,50,10]。
- 埃尔茜将吃掉最左边的蛋糕。现在剩余的蛋糕的大小为 [50,10][50,10]。
- 贝茜堆叠剩余的两个蛋糕。
贝茜将吃到 30+20+10=6030+20+10=60 的蛋糕，而埃尔茜将吃到 4040 的蛋糕。
第二个测试用例是第一个测试用例反转的情况，因此答案相同。
思路： 这是一个博弈论问题，一般的博弈论问题就是贪心问题。贝茜吃的蛋糕的总和是一段连续的子数组，也就是可以用前缀和来优化。不难发现，贝茜的操作是随着埃尔西的变化而变化的，因此可以枚举埃尔西的吃蛋糕的数的最大和来确定贝茜的答案。
#include<bits/stdc++.h>
using namespace std;
const int N = 500005;
int a[N];
long long s[N];
int main() {
int t; cin >> t;
while (t --) {
memset(s, 0, sizeof s);
memset(a, 0, sizeof a);
int n; cin >> n;
for (int i = 1; i<= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];
long long bexi_sum = 0, aerxi_sum = 0;
int cnt = (n - 2) / 2;
int i = 0, j = n;
// k表示埃尔西在左边吃的蛋糕数
for (int k = 0; k <= cnt; k ++) {
long long x = s[k] + s[n] - s[n - cnt + k];
if (x > aerxi_sum) {
aerxi_sum = x;
i = k + 1, j = n - cnt + k;
}
}
bexi_sum = s[j] - s[i - 1];
cout << bexi_sum << " " << aerxi_sum << endl;
}
}AcWing 6134. 哞叫时间II
农夫约翰正在试图向埃尔茜描述他最喜欢的 USACO 竞赛，但她很难理解为什么他这么喜欢它。
他说「竞赛中我最喜欢的部分是贝茜说『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。
埃尔茜仍然不理解，所以农夫约翰将竞赛以文本文件形式下载，并试图解释他的意思。
竞赛被定义为一个包含 NN 个整数的数组 a1,a2,…,aNa1,a2,…,aN。
农夫约翰定义哞叫为一个包含三个整数的数组，其中第二个整数等于第三个整数，但不等于第一个整数。
一种哞叫被称为在竞赛中发生，如果可以从数组中移除整数，直到只剩下这一哞叫。
由于贝茜据称「在整个竞赛中一直哞哞叫」，请帮助埃尔茜计算竞赛中发生的不同哞叫的数量！
两种哞叫是不同的，如果它们并非由相同的整数以相同的顺序组成。
输入格式
输入的第一行包含 NN。
第二行包含 NN 个空格分隔的整数 a1,a2,…,aNa1,a2,…,aN。
输出格式
输出竞赛中发生的不同哞叫的数量。
注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，Java 中的 “long”，C/C++ 中的 “long long”）。
数据范围
1≤N≤1061≤N≤106,
1≤ai≤N1≤ai≤N输入样例：
6 1 2 3 4 4 4输出样例：
3样例解释
竞赛包含三种不同的哞叫：
1 4 4，2 4 4和3 4 4。
思路：定义一个cnt数组来统计这个字符是否大于2，然后对每一个数字（以本数字作为头字符）进行枚举。
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int a[N];
int cnt[N]; //用来统计有多少种字符的个数大于2
int vis[N];
int main() {
int n; cin >> n;
for (int i = 1; i <= n ; i ++) cin >> a[i];
int sum = 0; //有多少个大于个数2的数
long long res = 0;
for (int i = 1; i <= n; i ++) {
if (++ cnt[a[i]] == 2) sum ++; //只统计一次，并且还可以进行统计
}
for (int i = 1; i <= n; i ++) {
if (-- cnt[a[i]] == 1) sum --;
if (! vis[a[i]])
res += sum - (cnt[a[i]] >= 2);
vis[a[i]] = 1;
}
cout << res << endl;
}AcWing 6135. 奶牛体检
农夫约翰的 NN 头奶牛站成一行，奶牛 11 在队伍的最前面，奶牛 NN 在队伍的最后面。
农夫约翰的奶牛也有许多不同的品种。
他用从 11 到 NN 的整数来表示每一品种。
队伍从前到后第 ii 头奶牛的品种是 aiai。
农夫约翰正在带他的奶牛们去当地的奶牛医院进行体检。
然而，奶牛兽医非常挑剔，仅愿意当队伍中第 ii 头奶牛为品种 bibi 时对其进行体检。
农夫约翰很懒惰，不想完全重新排列他的奶牛。
他将执行以下操作恰好一次。
- 选择两个整数 ll 和 rr，使得 1≤l≤r≤N1≤l≤r≤N。反转队伍中第 ll 头奶牛到第 rr 头奶牛之间的奶牛的顺序。
农夫约翰想要衡量这种方法有多少效果。
对于每一个 c=0…Nc=0…N，请帮助农夫约翰求出使得恰好 cc 头奶牛被检查的不同操作 (l,r)(l,r) 的数量。
两种操作 (l1,r1)(l1,r1) 和 (l2,r2)(l2,r2) 不同，如果 l1≠l2l1≠l2 或者 r1≠r2r1≠r2。
输入格式
输入的第一行包含 NN。
第二行包含 a1,a2,…,aNa1,a2,…,aN。
第三行包含 b1,b2,…,bNb1,b2,…,bN。
输出格式
输出 N+1N+1 行，第 ii 行包含使得 i−1i−1 头奶牛被检查的不同操作 (l,r)(l,r) 的数量。
数据范围
1≤N≤75001≤N≤7500,
1≤ai,bi≤N1≤ai,bi≤N输入样例1：
3 1 3 2 3 2 1输出样例1：
3 3 0 0样例1解释
如果农夫约翰选择 (l=1,r=1)(l=1,r=1)，(l=2,r=2)(l=2,r=2) 或 (l=3,r=3)(l=3,r=3)，则没有奶牛将会被检查。
注意这些操作并没有改变奶牛的位置。
以下操作会导致一头奶牛被检查。
- (l=1,r=2)(l=1,r=2)：农夫约翰反转第一头和第二头奶牛的顺序，因此新队伍中每头奶牛的品种将为 [3,1,2][3,1,2]。第一头奶牛将会被检查。
- (l=2,r=3)(l=2,r=3)：农夫约翰反转第二头和第三头奶牛的顺序，因此新队伍中每头奶牛的品种将为 [1,2,3][1,2,3]。第二头奶牛将会被检查。
- (l=1,r=3)(l=1,r=3)：农夫约翰反转第一头，第二头和第三头奶牛的顺序，因此新队伍中每头奶牛的品种将为 [2,3,1][2,3,1]。第三头奶牛将会被检查。
输入样例2：
3 1 2 3 1 2 3输出样例2：
0 3 0 3样例2解释
三种导致 33 头奶牛被检查的可能操作为 (l=1,r=1)(l=1,r=1)，(l=2,r=2)(l=2,r=2) 和 (l=3,r=3)(l=3,r=3)。
输入样例3：
7 1 3 2 2 1 3 2 3 2 2 1 2 3 1输出样例3：
0 6 14 6 2 0 0 0样例3解释
两种导致 44 头奶牛被检查的可能操作为 (l=4,r=5)(l=4,r=5) 和 (l=5,r=7)(l=5,r=7)。
思路：枚举每一个区间，从中间向两边进行枚举，将区间字符反转后，对答案进行统计。其中由中间向两边枚举的方法有两种，一种是由一个点向两边进行扩展，一个是由相邻两个点向两边进行扩展，然后判断对答案进行统计。
#include<bits/stdc++.h>
using namespace std;
const int N = 7510;
int a[N], b[N], ans[N];
int main() {
int n; cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++) cin >> b[i];
int cnt = 0; //由几头奶牛会被诊断
for (int i = 1; i <= n; i ++)
if (a[i] == b[i])
cnt ++;
for (int i = 1; i <= n; i ++) {
for (int j = 0; j < 2; j ++) {
int sum = cnt; // 对每一个区间都进行判断的临时变量
for (int l = i, r = i + j; l >= 1 && r <= n; l --, r ++) {
if (a[l] == b[l]) sum --; //反转前如果相同，则反转后诊断的牛就要减一
if (a[r] == b[r]) sum --; //同理
if (a[l] == b[r]) sum ++; //如果反转后相同，则诊断的牛加1
if (a[r] == b[l]) sum ++;
ans[sum] ++; //诊断牛为sum的数目加1
}
}
}
for (int i = 0; i <= n; i ++) {
cout << ans[i] << endl;
}
}此后会持续更新，继续加油！！！！