蓝桥杯每日一题--第一周（包罗五题）

AcWing 6122. 农夫约翰的奶酪块

           农夫约翰有一块立方体外形的奶酪，它位于三维坐标空间中，从 (0,0,0)(0,0,0) 延伸至 (N,N,N)(N,N,N)。
  农夫约翰将对他的奶酪块实验一系列 QQ 次更新操纵。
  对于每次更新操纵，农夫约翰将从整数坐标 (x,y,z)(x,y,z) 到 (x&#43
;1,y&#43
;1,z&#43
;1)(x&#43
;1,y&#43
;1,z&#43
;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
  输入样例：

1. 2 5
2. 0 0 0
3. 1 1 1
4. 0 1 0
5. 1 0 0
6. 1 1 0

复制代码

输出样例：

1. 0
2. 0
3. 1
4. 2
5. 5

复制代码

样例表明

  在前三次更新操纵后，[0,1]×[0,2]×[0,1][0,1]×[0,2]×[0,1] 范围的 1×2×11×2×1 砖块与剩余的奶酪不重叠，因此它贡献了答案。
  
  

[img]https://i-blog.csdnimg.cn/img_convert/b2743
f4b604ac2452cd800a9261ebf8a.png[/img]

   思绪：本题是一个在三维空间的标题，目前我们接触最多的就是二维空间上面的标题，因此我们必要将三维空间拆分为二维空间，由于三维空间有三个维度，分别为x-y平面，x-z平面，y-z平面，我们可以用三个二维数组来表示。对于如何统计答案，形如式子（if (a[x][y] == n)）表示在这个平面上一连切割了n个方块，此时就可以将答案加1。(三个维度都必要举行判定)

1. #include<iostream>
2. using namespace std;
3. const int N = 1010;
4. int a[N][N], b[N][N], c[N][N];
6. int main() {
7.     int n, q;
8.     cin >> n >> q;
9.     int res = 0;
10.     while (q --) {
11.         int x, y, z;
12.         cin >> x >> y >> z;
13.         a[x][y] &#43
14. ;&#43
15. ;;
16.         b[y][z] &#43
17. ;&#43
18. ;;
19.         c[x][z] &#43
20. ;&#43
21. ;;
22.         if (a[x][y] == n) res &#43
23. ;&#43
24. ;;
25.         if (b[y][z] == n) res &#43
26. ;&#43
27. ;;
28.         if (c[x][z] == n) res &#43
29. ;&#43
30. ;;
31.         cout << res << endl;
32.     }
33. }

复制代码

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：

1. 10 2
2. zzmoozzmoo

复制代码

输出样例1：

1. 1
2. moo

复制代码

样例1表明

  在这个样例中，任何字符变化都不会影响答案。
  唯一贝茜大概发出的哞叫是 moo。
  输入样例2：

1. 17 2
2. momoobaaaaaqqqcqq

复制代码

输出样例2：

1. 3
3. aqq
4. baa
5. cqq

复制代码

样例2表明

  在这个样例中，位置 88（从零开始索引）的 a 大概是由 b 损坏导致的，这使得 baa 成为一种贝茜发出两次的大概的哞叫。
  别的，位置 1111 的 q 大概是由 c 损坏导致的，这使得 cqq 成为一种贝茜大概的哞叫。
  aqq 可以通过将 c 换成 a 来到达。
  输入样例3
：

1. 3
2. 1
3. ooo

复制代码

输出样例3
：

1. 25
2. aoo
3. boo
4. coo
5. doo
6. eoo
7. foo
8. goo
9. hoo
10. ioo
11. joo
12. koo
13. loo
14. moo
15. noo
16. poo
17. qoo
18. roo
19. soo
20. too
21. uoo
22. voo
23. woo
24. xoo
25. yoo
26. zoo

复制代码

 思绪：枚举每一个长度为3
的字符串，设为abb，首先判定原字符串中有多少个abb，然后再判定是否能够改变一个字符，再加一个abb。最后判定abb出现的次数是否至少是f个即可。

1. #include<bits/stdc&#43
2. ;&#43
3. ;.h>
5. using namespace std;
7. int main() {
8.     int n, f; cin >> n >> f;
9.     string s; cin >> s;
10.     vector<string> res;
11.     // 形如abb形，此时令c1为a，c2为b
12.     for (char c1 = &#3
13. 9;a&#3
14. 9;; c1 <= &#3
15. 9;z&#3
16. 9;; c1 &#43
17. ;&#43
18. ;) {
19.         for (char c2 = &#3
20. 9;a&#3
21. 9;; c2 <= &#3
22. 9;z&#3
23. 9;; c2 &#43
24. ;&#43
25. ;) {
26.             if (c1 == c2) continue;
27.             int cnt = 0, flag = 0;
28.             auto t = s;
29.             // 原本有多少个
30.             for (int i = 0; i < n - 2; i &#43
31. ;&#43
32. ;) {
33.                 if (t[i] == c1 && t[i &#43
34. ; 1] == c2 && t[i &#43
35. ; 2] == c2) {
36.                     cnt &#43
37. ;&#43
38. ;;
39.                     t[i] = t[i &#43
40. ; 1] = t[i &#43
41. ; 2] = &#3
42. 9;#&#3
43. 9;;
44.                 }
45.             }
46.             // 是否能变
47.             for (int i = 0; i < n - 2; i &#43
48. ;&#43
49. ;) {
50.                 if (t[i] == &#3
51. 9;#&#3
52. 9; || t[i &#43
53. ; 1] == &#3
54. 9;#&#3
55. 9; || t[i &#43
56. ; 2] == &#3
57. 9;#&#3
58. 9;) continue;
59.                 // axb || xbb || abx 三种情况可以变成 abb
60.                 if ((t[i &#43
61. ; 1] == t[i &#43
62. ; 2] && t[i &#43
63. ; 1] == c2) || (t[i] == c1 && t[i &#43
64. ; 2] == c2) || (t[i] == c1 && t[i &#43
65. ; 1] == c2)) {
66.                     flag = 1;
67.                 }
68.             }
69.             if (cnt &#43
70. ; flag >= f) {
71.                 string x = &#3
72. 4;&#3
73. 4;;
74.                 x &#43
75. ;= string(1, c1) &#43
76. ; string(2, c2);
77.                 res.push_back(x);
78.             }
79.         }
80.     }
81.     cout << res.size() << endl;
82.     for (auto x: res) {
83.         cout << x << endl;
84.     }
85. }

复制代码

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。
  输入样例：

1. 2
2. 4
3. 40 3
4. 0 20 10
5. 4
6. 10 20 3
7. 0 40

复制代码

输出样例：

1. 60 40
2. 60 40

复制代码

样例表明

  对于第一个测试用例，在最优策略下，
  

• 贝茜将堆叠中间两个蛋糕。现在蛋糕的巨细为 [40,50,10][40,50,10]。
  
• 埃尔茜将吃掉最左边的蛋糕。现在剩余的蛋糕的巨细为 [50,10][50,10]。
  
• 贝茜堆叠剩余的两个蛋糕。
  

  贝茜将吃到 3
0&#43
;20&#43
;10=603
0&#43
;20&#43
;10=60 的蛋糕，而埃尔茜将吃到 4040 的蛋糕。
  第二个测试用例是第一个测试用例反转的情况，因此答案雷同。
  思绪： 这是一个博弈论问题，一般的博弈论问题就是贪心问题。贝茜吃的蛋糕的总和是一段一连的子数组，也就是可以用前缀和来优化。不难发现，贝茜的操纵是随着埃尔西的变化而变化的，因此可以枚举埃尔西的吃蛋糕的数的最大和来确定贝茜的答案。

1. #include<bits/stdc&#43
2. ;&#43
3. ;.h>
5. using namespace std;
6. const int N = 500005;
7. int a[N];
8. long long s[N];
10. int main() {
11.     int t; cin >> t;
12.     while (t --) {
13.         memset(s, 0, sizeof s);
14.         memset(a, 0, sizeof a);
15.         int n; cin >> n;
16.         for (int i = 1; i<= n; i &#43
17. ;&#43
18. ;) cin >> a[i];
19.         for (int i = 1; i <= n; i &#43
20. ;&#43
21. ;) s[i] = s[i - 1] &#43
22. ; a[i];
23.         long long bexi_sum = 0, aerxi_sum = 0;
24.         int cnt = (n - 2) / 2;
25.         int i = 0, j = n;
26.         // k表示埃尔西在左边吃的蛋糕数
27.         for (int k = 0; k <= cnt; k &#43
28. ;&#43
29. ;) {
30.             long long x = s[k] &#43
31. ; s[n] - s[n - cnt &#43
32. ; k];
33.             if (x > aerxi_sum) {
34.                 aerxi_sum = x;
35.                 i = k &#43
36. ; 1, j = n - cnt &#43
37. ; k;
38.             }
39.         }
40.         bexi_sum = s[j] - s[i - 1];
41.         cout << bexi_sum << &#3
42. 4; &#3
43. 4; << aerxi_sum << endl;
44.     }
45. }

复制代码

AcWing 613
4. 哞叫时间II

   农夫约翰正在试图向埃尔茜描述他最喜欢的 USACO 竞赛，但她很难理解为什么他这么喜欢它。
  他说「竞赛中我最喜欢的部门是贝茜说『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。
  埃尔茜仍旧不理解，所以农夫约翰将竞赛以文本文件形式下载，并试图表明他的意思。
  竞赛被定义为一个包罗 NN 个整数的数组 a1,a2,…,aNa1,a2,…,aN。
  农夫约翰定义哞叫为一个包罗三个整数的数组，其中第二个整数等于第三个整数，但不等于第一个整数。
  一种哞叫被称为在竞赛中发生，假如可以从数组中移除整数，直到只剩下这一哞叫。
  由于贝茜据称「在整个竞赛中一直哞哞叫」，请帮助埃尔茜计算竞赛中发生的差别哞叫的数量！
  两种哞叫是差别的，假如它们并非由雷同的整数以雷同的顺序组成。
  输入格式

  输入的第一行包罗 NN。
  第二行包罗 NN 个空格分隔的整数 a1,a2,…,aNa1,a2,…,aN。
  输特别式

  输出竞赛中发生的差别哞叫的数量。
  注意这个问题涉及到的整数大概必要使用 64 位整数型（例如，Java 中的 “long”，C/C&#43
;&#43
; 中的 “long long”）。
  数据范围

  1≤N≤1061≤N≤106,
1≤ai≤N1≤ai≤N
  输入样例：

1. 6
2. 1 2 3
3. 4 4 4

复制代码

输出样例：

1. 3

复制代码

样例表明

  竞赛包罗三种差别的哞叫：1 4 4，2 4 4 和 3
4 4。
  思绪：定义一个cnt数组来统计这个字符是否大于2，然后对每一个数字（以本数字作为头字符）举行枚举。

1. #include<bits/stdc&#43
2. ;&#43
3. ;.h>using namespace std;const int N = 1000010;int a[N];int cnt[N]; //用来统计有多少种字符的个数大于2int vis[N];int main() {    int n; cin >> n;    for (int i = 1; i <= n ; i &#43
4. ;&#43
5. ;) cin >> a[i];    int sum = 0; //有多少个大于个数2的数    long long res = 0;    for (int i = 1; i <= n; i &#43
6. ;&#43
7. ;) {        if (&#43
8. ;&#43
9. ; cnt[a[i]] == 2) sum &#43
10. ;&#43
11. ;; //只统计一次，并且还可以举行统计    }    for (int i = 1; i <= n; i &#43
12. ;&#43
13. ;) {        if (-- cnt[a[i]] == 1) sum --;        if (! vis[a[i]])            res &#43
14. ;= sum - (cnt[a[i]] >= 2);            vis[a[i]] = 1;    }    cout << res << endl;}

复制代码

AcWing 613
5. 奶牛体检

   农夫约翰的 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&#43
;1N&#43
;1 行，第 ii 行包罗使得 i−1i−1 头奶牛被查抄的差别操纵 (l,r)(l,r) 的数量。
  数据范围

  1≤N≤75001≤N≤7500,
1≤ai,bi≤N1≤ai,bi≤N
  输入样例1：

1. 3
2. 1 3
3. 23
4. 2 1

复制代码

输出样例1：

1. 3
2. 3
3. 00

复制代码

样例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：

1. 3
2. 1 2 3
3. 1 2 3

复制代码

输出样例2：

1. 03
2. 03

复制代码

样例2表明

  三种导致 3
3
 头奶牛被查抄的大概操纵为 (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
：

1. 71 3
2. 2 2 1 3
3. 23
4. 2 2 1 2 3
5. 1

复制代码

输出样例3
：

1. 0
2. 6
3. 14
4. 6
5. 2
6. 0
7. 0
8. 0

复制代码

样例3
表明

  两种导致 44 头奶牛被查抄的大概操纵为 (l=4,r=5)(l=4,r=5) 和 (l=5,r=7)(l=5,r=7)。
   思绪：枚举每一个区间，从中间向双方举行枚举，将区间字符反转后，对答案举行统计。其中由中间向双方枚举的方法有两种，一种是由一个点向双方举行扩展，一个是由相邻两个点向双方举行扩展，然后判定对答案举行统计。

1. #include<bits/stdc&#43
2. ;&#43
3. ;.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 &#43
4. ;&#43
5. ;) cin >> a[i];    for (int i = 1; i <= n; i &#43
6. ;&#43
7. ;) cin >> b[i];        int cnt = 0; //由几头奶牛会被诊断    for (int i = 1; i <= n; i &#43
8. ;&#43
9. ;)        if (a[i] == b[i])            cnt &#43
10. ;&#43
11. ;;        for (int i = 1; i <= n; i &#43
12. ;&#43
13. ;) {        for (int j = 0; j < 2; j &#43
14. ;&#43
15. ;) {            int sum = cnt; // 对每一个区间都举行判定的暂时变量            for (int l = i, r = i &#43
16. ; j; l >= 1 && r <= n; l --, r &#43
17. ;&#43
18. ;) {                if (a[l] == b[l]) sum --; //反转前假如雷同，则反转后诊断的牛就要减一                if (a[r] == b[r]) sum --; //同理                if (a[l] == b[r]) sum &#43
19. ;&#43
20. ;; //假如反转后雷同，则诊断的牛加1                if (a[r] == b[l]) sum &#43
21. ;&#43
22. ;;                ans[sum] &#43
23. ;&#43
24. ;; //诊断牛为sum的数目加1            }        }    }        for (int i = 0; i <= n; i &#43
25. ;&#43
26. ;) {        cout << ans[i] << endl;    }}

复制代码

此后会一连更新，继续加油！！！！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123
.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。