部分题解(ABFGIK) 题目链接:2021中国大学生程序设计竞赛(CCPC)- 网络选拔赛
A. Cut The Wire 大意 有无穷多个点编号 $1,2,3,\dots$。对于编号为 $x$ 的点满足:
如果 $x$ 是偶数,则 $x$ 与 $\frac{x}{2}$ 之间有一条边。
如果 $x$ 是奇数,则 $x$ 与 $3x+1$ 之间有一条边。
给定 $n$,求有多少连边 $(a,b)$ 满足 $a\le n$ 且 $b > n$。
解析 对于第一个条件,可以转化为 $\forall x,(x,2x)\in E$,然后直接计数即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <vector> #include <set> #include <map> using namespace std ;#define ll long long int T;int n;ll ans, a, b; int main () { scanf ("%d" , &T); while (T--) { scanf ("%d" , &n); ans = 0 ; a = n - n / 2 ; b = n - (n - 1 ) / 3 ; if (b % 2 == 1 && n % 2 == 1 ) { b = (b + 1 ) / 2 ; } else { b = b / 2 ; } printf ("%lld\n" , a + b); } return 0 ; }
B. Time-division Multiplexing 大意 给定 $n$ 个字符串,每个长度不超过 $12$。生成一个无限长的字符串 $t$:初始化每个字符串的字符位置为开始位置,每一轮选取每个字符串对应位置的字符添到 $t$ 的末尾,再将字符串的位置向后挪一个;若已经到最后,则设在开始位置。
一个例子:若有两个字符串 abcd efghi
,则生成的字符串是 ae bf cg dh ai be cf dg ...
(为了方便查看,每一轮之间加了一个空格表示,但最终字符串是不包含这些空格的)。
求在无限长的字符串 $t$ 中找到包含所有字符串中出现的字符且长度最短的连续子串,求出其长度即可。
解析 虽然是无限长,但 $t$ 本身存在循环节,我们只要在相邻两个循环节 中寻找最小值即可。
考虑得到节选 $t$ 的最大长度:不同长度之间取最小公倍数得到轮数 $lcm(1,2,\dots,12)=27720$,每轮生成附加字符串长度 $n$,找两个循环节。
得到节选的字符串后,采用双指针解决问题即可。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <vector> #include <set> #include <map> using namespace std ;#define ll long long const int maxn = 110 ;int T;int n;int len[maxn];char s[maxn][20 ];int lcm, cur;char t[maxn * 27720 * 2 ];int vis[30 ], totchar, curchar;int l, r;int ans;int gcd (int x, int y) { return (!y) ? x : gcd(y, x % y); } int main () { scanf ("%d" , &T); while (T--) { memset (vis, 0 , sizeof (vis)); totchar = 0 ; scanf ("%d" , &n); for (int i = 1 ; i <= n; ++i) { scanf ("%s" , s[i]); len[i] = strlen (s[i]); for (int j = 0 ; j < len[i]; ++j) { if (!vis[s[i][j] - 'a' ]) { vis[s[i][j] - 'a' ] = 1 ; ++totchar; } } } lcm = len[1 ]; for (int i = 2 ; i <= n; ++i) { lcm = lcm / gcd(lcm, len[i]) * len[i]; } lcm = lcm * n * 2 ; cur = 0 ; for (int i = 0 ; cur < lcm; ++i) { for (int j = 1 ; j <= n; ++j) { t[cur++] = s[j][i % len[j]]; } } t[cur] = '\0' ; ans = lcm; memset (vis, 0 , sizeof (vis)); curchar = 0 ; r = 0 ; ++vis[t[r] - 'a' ]; ++curchar; for (l = 0 ; l < lcm; ++l) { while (r < lcm - 1 && curchar < totchar) { ++r; if (!vis[t[r] - 'a' ]) ++curchar; ++vis[t[r] - 'a' ]; } if (curchar == totchar) { ans = min(ans, r - l + 1 ); } --vis[t[l] - 'a' ]; if (!vis[t[l] - 'a' ]) --curchar; } printf ("%d\n" , ans); } return 0 ; }
F. Power Sum 大意 给定 $n$,构造长度为 $k\le n+2$ 的数组 $a,a_i\in{-1,1}$,满足 $\sum\limits_{i=1}^{k}{a_i\times i^2}=n$。
解析 平方的增长是比较迅猛的,考虑到题目给出的 $k$ 与 $n$ 范围相似,说明我们构造数组的思路也可以往线性增长上靠拢。考虑相邻的两个平方数相减 $(n+1)^2-n^2=2n+1$,如果直接相加,和仍然不是线性增长。可以考虑再次做差:
$$((n+3)^2-(n+2)^2)-((n+1)^2-n^2)=(2(n+1)+1-(2n+1))=4$$
可以发现恰好 $4$ 个数能构成 $+4$,且与位置无关,实现了线性。
之后我们可以将 $n$ 分解为 $n\pmod 4+\lfloor \frac{n}{4}\rfloor \times 4$,即前面处理得到 $1,2,3$,后面直接 $+4$ 循环即可。$1,2,3$ 的构造不再详细说明,可以发现该方法最长的构造长度恰好是 $n+2$。
提示 做题的时候发现,对于后半部分,如果四个四个字符循环输出会跑的非常慢,但如果把答案处理为一个字符串输出则快很多。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <vector> #include <set> #include <map> using namespace std ;#define ll long long const int maxn = 1000010 ;int T;int n, res, cur;char s[maxn];int main () { scanf ("%d" , &T); while (T--) { scanf ("%d" , &n); res = n % 4 ; cur = 0 ; if (res == 0 ) { printf ("%d\n" , n); } else if (res == 1 ) { printf ("%d\n" , n); s[cur++] = '1' ; } else if (res == 2 ) { printf ("%d\n" , n + 2 ); s[cur++] = '0' ; s[cur++] = '0' ; s[cur++] = '0' ; s[cur++] = '1' ; } else { printf ("%d\n" , n - 1 ); s[cur++] = '0' ; s[cur++] = '1' ; } n >>= 2 ; for (int i = 1 ; i <= n; ++i) { s[cur++] = '1' ; s[cur++] = '0' ; s[cur++] = '0' ; s[cur++] = '1' ; } s[cur] = '\0' ; printf ("%s\n" , s); } return 0 ; }
G. Function 大意 设 $g(x)$ 代表 $x$ 在十进制下每位数之和。
设 $f(x)=Ax^2g(x)+Bx^2+Cxg^2(x)+Dxg(x)$,给定 $A,B,C,D$ 和 $N\le 10^{6}$,求 $x\in[1,N]$ 情况下 $\min \lbrace{f(x)}\rbrace$。
解析 $g(x)$ 是处理的难点,如果能确定 $g(x)$,问题就转化为二次函数求极值的问题。
可以看出 $g(x)$ 的取值范围非常小(最大 $6\times 9=54$),考虑枚举 $g(x)$,对每个确定的 $g(x)$ 求 $f(x)$ 的极值即可。
该题要注意一下几点:
当 $g(x)$ 确定时,需要保证枚举的 $x$ 满足 $g(x)$ 条件。
确定 $g(x)$ 后,设 $f(x)=ax^2+bx$:
$a=0$,此时不是二次函数,取端点极值。注意此处的端点需满足 $g(x)$ 条件。
$a<0$,同 $a=0$。
$a>0$,取最靠近 $-\frac{b}{2a}$ 的,注意考虑该位置是否在满足 $g(x)$ 条件的 $x$ 范围内。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <vector> #include <set> #include <map> using namespace std ;#define ll long long vector <int > num[60 ];void init () { int res, tot; for (int i = 1 ; i <= 1000000 ; ++i) { res = i; tot = 0 ; while (res) { tot += res % 10 ; res /= 10 ; } num[tot].push_back(i); } } int T;int a, b, c, d, n;int g;ll A, B; ll ans; ll calc () { if (A <= 0 ) { int p = lower_bound(num[g].begin(), num[g].end(), n) - num[g].begin(); if (p >= num[g].size() || num[g][p] > n) --p; return min(A * num[g][0 ] * num[g][0 ] + B * num[g][0 ], A * num[g][p] * num[g][p] + B * num[g][p]); } else { ll mid = (-B) / (2 * A); int p = lower_bound(num[g].begin(), num[g].end(), mid) - num[g].begin(); ll res = 6e18 ; if (p-1 >= 0 && p-1 < num[g].size() && num[g][p-1 ] <= n) { res = min(res, A * num[g][p-1 ] * num[g][p-1 ] + B * num[g][p-1 ]); } if (p >= 0 && p < num[g].size() && num[g][p] <= n) { res = min(res, A * num[g][p] * num[g][p] + B * num[g][p]); } if (p+1 >= 0 && p+1 < num[g].size() && num[g][p+1 ] <= n) { res = min(res, A * num[g][p+1 ] * num[g][p+1 ] + B * num[g][p+1 ]); } p = lower_bound(num[g].begin(), num[g].end(), n) - num[g].begin(); if (p >= num[g].size() || num[g][p] > n) --p; res = min(min(res, A * num[g][0 ] * num[g][0 ] + B * num[g][0 ]), A * num[g][p] * num[g][p] + B * num[g][p]); return res; } } int main () { init(); scanf ("%d" , &T); while (T--) { ans = 6e18 ; scanf ("%d%d%d%d%d" , &a, &b, &c, &d, &n); for (g = 1 ; g <= 54 ; ++g) { if (num[g][0 ] > n) continue ; A = 1l l * a * g + b; B = 1l l * c * g * g + d * g; ans = min(ans, calc()); } printf ("%lld\n" , ans); } return 0 ; }
I. Command Sequence 大意 给定一段操作序列,由上、下、左、右组成,执行每个操作会往对应的方向走一步。
求有多少连续子序列,满足按照该子序列执行操作,最终会回到出发点。
解析 每次经过位置打个标记,该位置在前面出现的次数便是走到这一步的贡献。用一个 map 记录即可。
别忘了初始位置。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <vector> #include <set> #include <map> using namespace std ;#define ll long long const int maxn = 100010 ;int T;int n;int sum1, sum2;char s[maxn];ll ans = 0 ; struct node { int x, y; } cur; struct cmp { bool operator () (const node &a, const node &b) const { return (a.x == b.x) ? a.y < b.y : a.x < b.x; } }; map <node, int , cmp> mp;int main () { scanf ("%d" , &T); while (T--) { scanf ("%d" , &n); scanf ("%s" , s+1 ); ans = 0 ; sum1 = sum2 = 0 ; mp.clear(); cur = (node){0 , 0 }; mp[cur] = 1 ; for (int i = 1 ; i <= n; ++i) { if (s[i] == 'U' ) { ++sum1; } else if (s[i] == 'D' ) { --sum1; } else if (s[i] == 'L' ) { ++sum2; } else if (s[i] == 'R' ) { --sum2; } cur = (node){sum1, sum2}; if (mp.count(cur)) { ans += mp[cur]; ++mp[cur]; } else { mp[cur] = 1 ; } } printf ("%lld\n" , ans); } return 0 ; }
K. Shooting Bricks 大意 打砖块。
给你 $k$ 个小球,每个小球能打一个方块。给定 $n\times m$ 个方块,每次可以打一列中最靠外的一个。每个方块有一个得分,同时有些方块在被打碎后,可以获得另外一个球,这种方块用 Y 标识,其他的为 N。
求最大化得分。
解析 一种典型的错误做法 设 $v(i,j)$ 代表对于第 $i$ 列,用 $j$ 个球能得到的最大分数。 设 $f(i,j)$ 代表对于前 $i$ 列,用 $j$ 个球能得到的最大分数,那么状态转移方程: $$f(i,j)=\max\lbrace{f(i-1,j-k)+v(i,k)}\rbrace$$ 最终答案即为 $f(n,k)$。
这种做法忽略了一种问题:需要球的个数 $\not=$ 消耗球的个数 。 打个比方,某一列的方块情况为 YNY
,如果要打完该列所有的方块,消耗球的数量为 1,需要球的数量为 2。 因为在打完 N
之后,虽然看上去消耗一个球的同时又得到一个球没有影响,但必须先有球去打破该方块,才能得到分数的同时再得到一个奖励球。
正确思路 有一个很容易想到的贪心:优先打 Y 类型的方块。因为打 Y 类型的相当于不消耗,且只要有球就可以完成;如果先打了 N 类型的方块,则当没球的时候就没法打 Y 类型的方块,而这些方块可以在打 N 类型方块前完成。
由此我们可以得到一个结论:若场上存在 N 类型方块,则最后打的一定是 N 类型的方块。(如过全是 Y 类型的话,直接一个球打完了,不必进行讨论。)
我们假设最后一个打的方块在第 $k$ 列:
对于第 $k$ 列,打完最后一个 N 方块后便没有球了,就算后面有 Y 方块也无法得到分数。此时的计算个数由需要球的个数决定。
对于其他列,假设我们给该列分配了 $a$ 个球。那么在该列打破了 $a$ 个 N 类型方块后,由于至少有一个求留给了第 $k$ 列,我们可以用第 $k$ 列的球把后面的 Y 方块打破。此时的计算个数由消耗求的个数决定。
设 $v_1(i,j)$ 代表第 $i$ 列消耗 $j$ 个球能得到的最大分数,$v_2(i,j)$ 代表第 $i$ 列只有 $j$ 个球时能得到的最大分数。设 $f(i,j,0/1)$ 代表前 $i$ 列中用 $j$ 个球的最大值,$0/1$ 代表是否在前 $i$ 列中存在打的最后一列。
考虑转移,用 $x\gets y$ 表示用 $y$ 去更新 $x$。假设正在考虑第 $i$ 列:
第 $i$ 列是最后被打的方块所在的列:
前 $i-1$ 列中必定没有,且该列至少消耗一个球。$f(i,j,1)\gets f(i-1,j-k,0)+v_2(i,k),k>0$
第 $i$ 列不是最后被打的方块所在的列:
前 $i-1$ 列中有,前面至少消耗一个球。$f(i,j,1)\gets f(i-1,j-k,1)+v_1(i,k),k<j$
前 $i-1$ 列中无。$f(i,j,0)\gets f(i-1,j-k,0)+v_1(i,k)$
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <vector> #include <set> #include <map> using namespace std ;#define ll long long const int maxn = 210 ;int T;int n, m, K;int a[maxn][maxn];char c[maxn][maxn];int v1[maxn][maxn];int v2[maxn][maxn];int f[maxn][maxn][2 ];int tot;int main () { scanf ("%d" , &T); while (T--) { memset (f, 0 , sizeof (f)); memset (v1, 0 , sizeof (v1)); memset (v2, 0 , sizeof (v2)); scanf ("%d%d%d" , &n, &m, &K); for (int i = 1 ; i <= n; ++i) { for (int j = 1 ; j <= m; ++j) { scanf ("%d" , &a[i][j]); c[i][j] = getchar(); while (c[i][j] != 'Y' && c[i][j] != 'N' ) c[i][j] = getchar(); } } for (int j = 1 ; j <= m; ++j) { tot = 0 ; for (int i = n; i >= 1 ; --i) { if (c[i][j] == 'N' ) { ++tot; v1[j][tot] = v1[j][tot-1 ] + a[i][j]; v2[j][tot] = v1[j][tot]; } else { v1[j][tot] += a[i][j]; } } } for (int i = 1 ; i <= m; ++i) { for (int j = 0 ; j <= K; ++j) { for (int k = 0 ; k <= min(j, n); ++k) { if (k) f[i][j][1 ] = max(f[i][j][1 ], f[i-1 ][j-k][0 ] + v2[i][k]); if (k < j) f[i][j][1 ] = max(f[i][j][1 ], f[i-1 ][j-k][1 ] + v1[i][k]); f[i][j][0 ] = max(f[i][j][0 ], f[i-1 ][j-k][0 ] + v1[i][k]); } } } printf ("%d\n" , f[m][K][1 ]); } return 0 ; }
L. Remove 大意 一堆石子有 $n$ 个,给定质数集 $P$。每次操作可以从 $P$ 中选择一个数 $p$ ,从其中去掉 $n\pmod p$ 个石子。给定 $N$,求 $n=1,2,\dots,n$ 时至少多少次能够去掉所有石子。
解析 对于每次执行的操作,可以理解为 $n\to n - n\bmod p$,也可以理解为 $n\to \left\lfloor\frac{n}{p}\right\rfloor\times p$。
先考虑无解情况:最终会进入无论怎么操作,石子的个数不会减少的局面。容易想到 lcm,因为是质数集,也就是所有数的积。对于大于 lcm 的数,也无法通过操作得到小于 lcm 的数。
考虑针对 $n$ 选择合适的 $p$。这里我们可以从直觉上看出,随着 $n$ 增大,需要的步骤是单调不减的。证明详见后面。
有了这个结论,则我们每次选择的数为让 $n \bmod p$ 最大化的 $p$。
每次减法不太好想,我们可以换种思路。对于小于 $p_{max}$ 的数,我们可以直接 $1$ 步得到。对于有解的其他数,我们由小的数去更新大的数。
考虑一个数 $x$ 能推导出的数的范围:
关于单调性的证明 对于 $x$ 个石子,设需要的步数为 $f(x)$。
对于任意 $x$,证明 $f(x)\le f(x+1)$:
我们不妨设 $f(x)>f(x+1)$,即 $x-x\bmod p_1>x+1-(x+1)\bmod p_2$,移项后得到 $(x+1)\bmod p_2 - x\bmod p_1>1$,很明显不存在这种情况,矛盾。原式得证。
由此可以推出 $\forall x<y, f(x)\le f(y)$,单调性得证。