第十四届蓝桥杯大赛软件赛省赛（C/C++ 大学C组）
蓝���杯 2023年省赛真题 C/C++ 大学C组
- 试题 A: 求和
- 试题 B: 工作时长
- 试题 C: 三国游
- 试题 D: 填充
- 试题 E: 翻转
- 试题 F: 子矩阵
- 试题 G: 互质数的个数
- 试题 H: 异或和之差
- 试题 I: 公因数匹配
- 试题 J: 子树的大小
试题 A: 求和
本题总分： 5 5 5 分
【问题描述】
求 1 1 1 （含）至 20230408 20230408 20230408 （含）中每个数的和。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
204634714038436
自然数列求和， 1 + 2 + ⋯ + n = n ( n + 1 ) 2 1+2+\cdots+n=\cfrac {n(n+1)}2 1+2+⋯+n=2n(n+1)。
#include int main() { printf("%lld", 20230408 * (20230408 + 1ll) / 2); }或者迭代答案。
#include int main() { long long ans = 0; for (int i = 1; i freopen("lock-in.all.txt", "r", stdin); std::priority_queue Y + Z X > Y + Z X>Y+Z 时，我们认为魏国获胜。小蓝想知道游戏结束时如果有其中一个国家获胜，最多发生了多少个事件?如果不存在任何能让某国获胜的情况，请输出 − 1 −1 −
【输入格式】
输入的第一行包含一个整数 n n n。
第二行包含 n n n 个整数表示 A i A_i Ai，相邻整数之间使用一个空格分隔。
第三行包含 n n n 个整数表示 B i B_i Bi，相邻整数之间使用一个空格分隔。
第四行包含 n n n 个整数表示 C i C_i Ci，相邻整数之间使用一个空格分隔。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
3 1 2 2 2 3 2 1 0 7
【样例输出】
2
【样例说明】
发生两个事件时，有两种不同的情况会出现获胜方。
发生 1 , 2 1, 2 1,2 事件时蜀国获胜。
发生 1 , 3 1, 3 1,3 事件时吴国获胜。
【评测用例规模与约定】
对于 40 % 40\% 40% 的评测用例， n ≤ 500 n ≤ 500 n≤500；
对于 70 % 70\% 70% 的评测用例， n ≤ 5000 n ≤ 5000 n≤5000；
对于所有评测用例， 1 ≤ n ≤ 1 0 5 ， 1 ≤ A i , B i , C i ≤ 1 0 9 1 ≤ n ≤ 10^5，1 ≤ A_i, B_i,C_i ≤ 10^9 1≤n≤105，1≤Ai,Bi,Ci≤
贪心
同时考虑三个国家是相当困难的，于是考虑分别求出魏蜀吴分别获胜的话最大事件数，最优答案就是这若干个数中的最大值。
以魏举例，记第 i i i 个事件对魏获胜的贡献为 x i − y i − z i x_i -y_i -z_i xi−yi−zi，按贡献降序重排事件，找到一个 k k k，满足 ∑ i = 1 k x i > ∑ i = 1 k ( y i + z i ) \sum_{i=1}^kx_i >\sum_{i=1}^k(y_i + z_i) ∑i=1kxi>∑i=1k(yi+zi) 且 k k k 尽可能大，若 k b.x - b.y - b.z; }, [](long long x, long long y, long long z) -> bool { return x > y + z; }), std::max( greedy([](tuple a, tuple b)-> bool { return a.y - a.x - a.z > b.y - b.x - b.z; }, [](long long x, long long y, long long z) -> bool { return y > x + z; }), greedy([](tuple a, tuple b)-> bool { return a.z - a.x - a.y > b.z - b.x - b.y; }, [](long long x, long long y, long long z) -> bool { return z > x + y; }) ))); }
22岁，喜欢屎山代码。
试题 D: 填充
时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 10 10 10 分
【问题描述】
有一个长度为 n n n 的 01 01 01 串，其中有一些位置标记为 ? ? ?，这些位置上可以任意填充 0 0 0 或者 1 1 1，请问如何填充这些位置使得这个 01 01 01 串中出现互不重叠的 00 00 00 和 11 11 11 子串最多，输出子串个数。
【输入格式】
输入一行包含一个字符串。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
1110?0
【样例输出】
2
【样例说明】
如果在问号处填 0 0 0，则最多出现一个 00 00 00 和一个 11 ： 111000 11：111000 11：
【评测用例规模与约定】
对于所有评测用例， 1 ≤ n ≤ 1000000 1 ≤ n ≤ 1000000 1≤n≤
贪心
如果以01相接的地方为断点，将01串拆分开来，如1110?0拆分成111、0?0，则显然第二段中的问号应填0，于是只需考虑若干问号存在01之间的情况，如果若干问号的左侧段长为奇数，则考虑将一个问号变为左侧段对应的值，使总答案加一，然后将所有问号变为右侧段对应的值，若剩余问号为奇数则这个数字除二向下取整是雷打不动的，而多余的一个变为左侧对答案无贡献，所以直接变右，这么模拟着递推过来就行。
实现时连续的问号同时当做0、1来看待，然后找到子串后清空累计即可。
#include int ans, cnt['1' + 1]; char buf[1000010]; int main() { gets(buf); for (int i = 0; buf[i]; ++i) { if (buf[i] == '?') { if (cnt['0']) ++cnt['0']; else if (cnt['1']) ++cnt['1']; else ++cnt['0'], ++cnt['1']; } else ++cnt[buf[i]], cnt[buf[i] ^ 1] = 0; if (cnt['0'] == 2 || cnt['1'] == 2) ++ans, cnt['0'] = cnt['1'] = 0; } printf("%d", ans); }好像又把代码写成一坨了
试题 E: 翻转
时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 15 15 15 分
【问题描述】
小蓝用黑白棋的 n n n 个棋子排成了一行，他在脑海里想象出了一个长度为 n n n 的 01 01 01 串 T T T，他发现如果把黑棋当做 1 1 1，白棋当做 0 0 0，这一行棋子也是一个长度为 n n n 的 01 01 01 串 S S S。
小蓝决定，如果在 S S S 中发现一个棋子和它两边的棋子都不一样，就可以将其翻转变成另一个颜色。也就是说，如果 S S S 中存在子串 101 101 101 或者 010 010 010，就可以选择将其分别变为 111 111 111 和 000 000 000，这样的操作可以无限重复。
小蓝想知道最少翻转多少次可以把 S S S 变成和 T T T 一模一样。
【输入格式】
输入包含多组数据。
输入的第一行包含一个正整数 D D D 表示数据组数。
后面 2 D 2D 2D 行每行包含一个 01 01 01 串，每两行为一组数据，第 2 i − 1 2i − 1 2i−1 行为第 i i i 组数据的 T i T_i Ti，第 2 i 2i 2i 行为第 i i i 组数据的 S i S_i Si， S i S_i Si 和 T i T_i Ti 长度均为 n i n_i ni。
【输出格式】
对于每组数据，输出一行包含一个整数，表示答案，如果答案不存在请输出 −
【样例输入】
2 1000111 1010101 01000 11000
【样例输出】
2 -1
【评测用例规模与约定】
对于 20 % 20\% 20% 的评测用例， 1 ≤ ∑ 1 D n i ≤ 10 1 ≤\sum_1^{{}_D} n_i ≤ 10 1≤∑1Dni≤10；
对于所有评测用例，保证 1 ≤ ∑ 1 D n i ≤ 1 0 6 ， n i > 0 1 ≤\sum_1^{{}_D} n_i ≤ 10^6 ，n_i > 0 1≤∑1Dni≤106，ni>0。
由题意可知，端点棋子是无法翻转的，而当某一个棋子翻转时，它与相邻棋子连续相同，故无法产生新的翻转点，因此端点特判然后遍历模拟就行。
#include char T[1000010], S[1000010]; int D, cnt; int main() { for (scanf("%d\n", &D); gets(T + 1), gets(S + 1), D--;) { for (int i = 1; S[i]; ++i) { if (S[i] == T[i]) continue; if (S[i - 1] == S[i] ^ 1 && S[i - 1] == S[i + 1]) S[i] ^= 1, ++cnt; else { cnt = -1; break; } } printf("%d\n", cnt), cnt = 0; } }试题 F: 子矩阵
时间限制: 2.0 s 2.0\mathrm s 2.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 15 15 15 分
【问题描述】
给定一个 n × m n × m n×m （ n n n 行 m m m 列）的矩阵。
设一个矩阵的价值为其所有数中的最大值和最小值的乘积。求给定矩阵的所有大小为 a × b a × b a×b （ a a a 行 b b b 列）的子矩阵的价值的和。
答案可能很大，你只需要输出答案对 998244353 998244353 998244353 取模后的结果。
【输入格式】
输入的第一行包含四个整数分别表示 n , m , a , b n, m, a, b n,m,a,b，相邻整数之间使用一个空格分隔。
接下来 n n n 行每行包含 m m m 个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 A i , j A_{i, j} Ai,j。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
2 3 1 2 1 2 3 4 5 6
【样例输出】
58
【样例说明】
1 × 2 + 2 × 3 + 4 × 5 + 5 × 6 = 58 1 × 2 + 2 × 3 + 4 × 5 + 5 × 6 = 58 1×2+2×3+4×5+5×6=
【评测用例规模与约定】
对于 40 % 40\% 40% 的评测用例， 1 ≤ n , m ≤ 100 1 ≤ n, m ≤ 100 1≤n,m≤100；
对于 70 % 70\% 70% 的评测用例， 1 ≤ n , m ≤ 500 1 ≤ n, m ≤ 500 1≤n,m≤500；
对于所有评测用例， 1 ≤ a ≤ n ≤ 1000 1 ≤ b ≤ m ≤ 1000 1 ≤ A i , j ≤ 1 0 9 1 ≤ a ≤ n ≤ 1000\ 1 ≤ b ≤ m ≤ 1000\ 1 ≤ A_{i, j} ≤ 10^9 1≤a≤n≤1000 1≤b≤m≤1000 1≤Ai,j≤
通过单调队列，先将矩阵(i-a+1,j)(i,j)的最值求出，然后如法炮制求出(i-a+1,j-b+1)(i,j-b+1)、(i-a+1,j-b+2)(i,j-b+2)、…、(i-a+1,j)(i,j)的最值，即(i-a+1,j-b+1)(i,j)的最值。
单调队列求最值懒得讲了，关键字：单调队列、滑动窗口、区间最值，自己搜着看吧。
#include int n, m, a, b, maxh, maxt, minh, mint, max[1000][1000], min[1000][1000], maxq[1010], minq[1010]; int main() { scanf("%d %d %d %d", &n, &m, &a, &b); for (int i = 0; i i) ++minh; min[i][j] = max[minq[minh]][j]; max[i][j] = max[maxq[maxh]][j]; if (i - a >= 0) { while (maxh != maxt && max[i - a][j] >= max[maxq[maxt - 1]][j]) --maxt; while (minh != mint && max[i - a][j] maxh = maxt = minh = mint = 0; for (int j = 0; j = 1) { if (b & 1) p = p * a % MOD; a = a * a % MOD; } return p; } long long a, b, ans; int main() { scanf("%d %lld", &a, &b); ans = qpow(a, b); for (int p = 2; p * p if (a % p == 0) { ans = ((ans * qpow(p, MOD - 2)) % MOD) * (p - 1) % MOD; while (a % p == 0) a /= p; } } if (a 1) ans = ((ans * qpow(a, MOD - 2)) % MOD) * (a - 1) % MOD; printf("%lld", ans); }截止2023年5月12日16:31:11，dotcpp上的民间数据有误，当 a a a取 a b a^b ab余数部分，并且 a n s ∤ p ans\not|\ p ans∣ p时才能通过所有用例，错的离谱，害得我de半天bug。
试题 H: 异或和之差
时间限制: 1.0 s 1.0\mathrm s 1.0s 内存限制: 256.0 M B 256.0\mathrm{MB} 256.0MB 本题总分： 20 20 20 分
【问题描述】
给定一个含有 n n n 个元素的数组 A i A_i Ai，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。
【输入格式】
输入的第一行包含一个整数 n n n 。
第二行包含 n n n 个整数 A i A_i Ai，相邻整数之间使用一个空格分隔。
【输出格式】
输出一行包含一个整数表示答案。
【样例输入】
6 1 2 4 9 2 7
【样例输出】
14
【样例说明】
两个子段可以分别选 1 1 1 和 4 ， 9 ， 2 4，9，2 4，9，2，差值为 15 − 1 = 14 15 − 1 = 14 15−1=
【评测用例规模与约定】
对于 40 % 40\% 40% 的评测用例， n ≤ 5000 n ≤ 5000 n≤5000；
对于所有评测用例， 2 ≤ n ≤ 2 × 1 0 5 ， 0 ≤ A i ≤ 2 20 2 ≤ n ≤ 2 × 10^5，0 ≤ A_i ≤ 2^{20} 2≤n≤2×105，0≤Ai≤
01字典树，里面存前缀异或和，然后查询[1,i][i,n]的最值，做个dp最后枚举答案。
#include #include int n, m = 20, ans, cur, a[200010], lmax, lmin, rmax[200010], rmin[200010], trie[800010][2]; void add(int x) { int rt = 0; for (int i = m; ~i; --i) { int b = (x >> i) & 1; if (!trie[rt][b]) trie[rt][b] = ++cur; rt = trie[rt][b]; } } int xor_max(int x) { int rt = 0, max = 0; for (int i = m; ~i; --i) { int b = (x >> i) & 1; if (trie[rt][b ^ 1]) { rt = trie[rt][b ^ 1]; max |= 1 int rt = 0, min = 0; for (int i = m; ~i; --i) { int b = (x > i) & 1; if (trie[rt][b]) rt = trie[rt][b]; else { rt = trie[rt][b ^ 1]; min |= 1 scanf("%d", &n); for (int i = 1; i add(s), s ^= a[i]; rmax[i] = std::max(rmax[i + 1], xor_max(s)); rmin[i] = std::min(rmin[i + 1], xor_min(s)); } for (; cur; --cur) trie[cur][0] = trie[cur][1] = 0; trie[0][1] = trie[0][0] = 0; for (int i = 1, s = 0; i