Codeforces Global Round 26 A~E

本文主要是介绍Codeforces Global Round 26 A~E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A.Strange Splitting（思维）

题意：

将非空数组的范围定义为最大值减去最小值。例如，$[1,4,2]$的范围是$4-1=3$。

给你一个长度为$n\ge 3$的数组$a_1,a_2,\dots ,a_n$。保证$a$被排序。

你必须给$a$中的每个元素涂上红色或蓝色，以便：

• 红色元素的范围不等于蓝色元素的范围，并且
• 每种颜色至少有一个元素。

如果不存在这样的着色，则输出$NO$。如果存在多种有效着色，则可以输出其中任何一种。

分析：

如果$a_1=a_n$，无解。

如果$a_2=a_n$，$a_1,a_2$涂成红色，否则只把$a_1$涂成红色。

代码：

#include<bits/stdc++.h>using namespace std;
const int N = 1e6 + 10;
int a[N];void solve() {int n;cin >> n;for (int i = 1; i <= n; ++i)cin >> a[i];if (a[1] == a[n]) {cout << "NO" << endl;return;}cout << "YES" << endl;if (a[2] != a[n]) {cout << "R";for (int i = 2; i <= n; ++i) {cout << "B";}cout << endl;return;}cout << "RR";for (int i = 3; i <= n; ++i) {cout << "B";}cout << endl;
}int main() {int t;cin >> t;while (t--)solve();return 0;
}

B.Large Addition（模拟）

题意：

如果一个数位介于$5$和$9$之间（含），则该数位为大数。如果一个正整数的所有位数都是大数，那么这个正整数就是大正整数。

给你一个整数$x$。它可以是两个位数相同的大正整数之和吗？

分析：

由于大于等于$5$小于等于$9$的数不管这么组合，两个数字相加的和一定在$10-18$之间，那么可以得到如果给出的数的第一位上不是$1$或者最后一位上是$9$或者或者中间有一位上是$0$，那么就是不存在的，否则就是可行的。

代码：

#include<bits/stdc++.h>typedef long long LL;
using namespace std;void solve() {LL x;cin >> x;bool flag = 1;if (x % 10 == 9)flag = 0;x /= 10;while (x) {int y = x % 10;if ((y + 9) % 10 == 9)flag = 0;if (x < 10 && y > 1)flag = 0;x /= 10;}if (flag)cout << "YES" << endl;elsecout << "NO" << endl;
}int main() {int t;cin >> t;while (t--)solve();return 0;
}

C1.Magnitude (Easy Version)（贪心）

题意：

两个版本的问题是不同的。

给你一个长度为$n$的数组$a$。从$c=0$开始。然后，对于从$1$到$n$的每一个$i$（按递增顺序）做下面的操作之一：

• 选项$1$: 设置$c$至$c+a_i$。
• 选项$2$: 设置$c$至$|c+a_i|$，$|x|$是$x$的绝对值。

设上述步骤后$c$的最大终值等于$k$。求出$k$。

分析：

发现要么一直不用$2$操作，要么在答案取到最小值的时候使用一遍$2$操作让其变为相对大一些的值。显然使用多遍$2$操作是不优的。然后还能发现若存在一个位置$P$使得前缀和小于$0$，那么这个地方实验$2$操作较优。因此若不存在一个前缀和的值小于$0$那么就不应该使用$2$操作。否则一定在任意一个值最小的位置使用一次$2$操作即可。

代码：

#include<bits/stdc++.h>typedef long long LL;
using namespace std;
const int N = 1e6 + 10;
LL a[N], pre[N];void solve() {LL n, id = -1;cin >> n;for (LL i = 1; i <= n; i++) {cin >> a[i];pre[i] = pre[i - 1] + a[i];}LL mi = 0;for (LL i = n; i; i--) {if (pre[i] < mi) {mi = pre[i];id = i;}}if (id == -1)cout << pre[n] << endl;else {LL s = 0;for (LL i = 1; i <= n; i++) {if (i <= id)s -= a[i];elses += a[i];}cout << s << endl;}
}int main() {int t;cin >> t;while (t--)solve();return 0;
}

C2.Magnitude (Hard Version)（贪心）

题意：

两个版本的问题是不同的。

给你一个长度为$n$的数组$a$。从$c=0$开始。然后，对于从$1$到$n$的每个$i$（按递增顺序），做以下操作之一：

• 选项$1$：设置$c$至$c+a_i$。
• 选项$2$：设置$c$至$|c+a_i|$，$|x|$是$x$的绝对值。

假设经过上述程序后，$c$的最大终值等于$k$。求得出$c=k$的唯一程序的个数。如果在任意索引$i$处，一个程序选择了选项$1$，而另一个程序选择了选项$2$，即使$c$的值在该轮之后对两个程序都相等，那么这两个程序也是不同的。

由于答案可能很大，输出对$998244353$取模的结果。

分析：

每一步结束之后，若当前的前缀和取到了全部前缀和的最小值，则这一步对答案造成了$2^{n-i+r}$贡献，其中$r$是在这一步操作中前缀和不小于$0$的位置的数量。若全部操作中没有任何一个前缀和小于$0$则答案为$2^n$。

不存在任何一个前缀和使得这个前缀和不大于$0$。此时对于任意一个位置$1$操作和$2$操作没有任何本质区别。任意一步都可以在$1$操作和$2$操作中任选一个操作执行。

存在一个前缀和使得这个前缀和不大于$0$。因为执行完这一步之后后面不论怎么走答案都不会偏离最大值（参见$C1$的结论），所以说后面的任意一步都可以在$1$操作和$2$操作中任选，即$2^{n-i}$种不同选择；若前面有前缀和大于等于$0$的那么$1$操作和$2$操作没有本质的区别，若有$r$个满足这样条件的则有$2^r$种不同选择。根据乘法原理可知对答案的贡献为$2^{n-i+r}$。其中$r$可以在枚举的时候扫一遍得出答案。

代码：

#include<bits/stdc++.h>typedef long long LL;
using namespace std;
const int N = 1e6 + 10;
const int MOD = 998244353;
LL a[N], pre[N], bin[N];void solve() {int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];pre[i] = pre[i - 1] + a[i];}LL mi = 0, r = 0;for (int i = 1; i <= n; i++)mi = min(mi, pre[i]);if (mi == 0)cout << bin[n] << endl;else {int ans = 0;for (int i = 1; i <= n; i++) {if (pre[i] >= 0)r++;if (pre[i] == mi)ans = (ans + bin[n - i + r]) % MOD;}cout << ans << endl;}
}int main() {int t;cin >> t;bin[0] = 1;for (int i = 1; i < N; i++)bin[i] = bin[i - 1] * 2 % MOD;while (t--)solve();return 0;
}

D.“a” String Problem（数学）

题意：

给你一个由小写拉丁字符组成的字符串$s$。请计算非空字符串$t\ne$"$\text{a}$"的个数。使得可以将$s$分割为满足以下条件的一些子字符串：

• 每个子串要么等于$t$要么等于"$\text{a}$"，并且
• 至少有一个子串等于$t$。

${}^{†}$字符串$s$的分区是由一些$k$字符串$t_1,t_2,\dots ,t_k$（称为子串）组成的有序序列，使得$t_1+t_2+\dots +t_k=s$，其中$+$表示连接操作。

分析：

设$s$长度为$n$。特判全为$a$的情况，共$n-1$种方案。

设$s$中非$a$字符的数量为$m$。

如果$t$中有$k$个非$a$字符，把$t$掐头去尾忽略前后的$a$后，原串里一定恰好存在$\frac{m}{k}$个$t\prime$，且$k\mid m$。

枚举$k$。记录第$i$个非$a$字符的位置为$p_i$（从$0$开始），如果$s_{p_i}\ne s_{p_i-k}$或不在分割处的$p_i-p_{i-1}\ne p_{i-k}-p_{i-k-1}$，$t\prime$不合法。

把$t\prime$还原为$t$，枚举左边有的$a$个数$l\in [0,p_0]$。

设$x$为分割处的最小间隔$min(p_i-p_{i-1})$，$k\mid i$，则右边的$a$个数$r\in [0,min(x-l,n-p_{m-1}-1)]$。

代码：

#include<bits/stdc++.h>typedef long long LL;
using namespace std;
const int MOD = 998244353;void solve() {string s;cin >> s;int n = s.length();if (count(s.begin(), s.end(), 'a') == n) {cout << n - 1 << endl;return;}vector<int> a;for (int i = 0; i < n; ++i) {if (s[i] != 'a') {a.emplace_back(i);}}int m = a.size();LL ans = 0;for (int i = 1; i <= m; ++i) {if (m % i) {continue;}int ok = 1;for (int j = i; j < m; ++j) {int o = j % i;if (s[a[j]] != s[a[o]] || (o && a[o] - a[o - 1] != a[j] - a[j - 1])) {ok = 0;break;}}if (ok) {int mi = n;for (int j = i; j < m; j += i) {mi = min(mi, a[j] - a[j - 1] - 1);}int r = n - a.back() - 1;for (int l = 0; l <= a[0]; ++l) {ans += max(0, min(r + 1, mi - l + 1));}}}cout << ans << endl;
}int main() {int t;cin >> t;while (t--)solve();return 0;
}

E.Shuffle（树形DP）

题意：

两只饥饿的小熊猫奥斯卡和卢拉有一棵有$n$个节点的树$T$。它们愿意在整棵树$T$上精确地执行一次下面的洗牌程序。通过这个洗牌过程，他们将从旧树的节点中创建一棵新树。

1. 从原始树$T$中选择任意一个节点$V$。创建一棵以$V$为根的新树$T_2$。
2. 从$T$中移除$V$，这样原树就会分裂成一个或多个子树（如果$V$是$T$中的唯一节点，则子树数量为零）。
3. 用同样的方法对每棵子树进行洗牌（同样选择任意节点作为根节点），然后将所有洗牌后子树的根节点连接回$V$以完成$T_2$的构建。

这样，奥斯卡和卢拉就得到了一棵新树$T_2$。它们只能吃树叶，而且非常饥饿，因此请找出在所有树中，只需一次洗牌就能生成的树叶的最大数量。

请注意，树叶是阶数为$1$的所有节点。因此，如果树根只有一个子节点，那么它就可以被视为树叶。

分析：

把一个点的父亲儿子都加到$T_2$后，这个点就是叶子，且与之直接相连的点都不是叶子。（所有相邻点都是这个点的祖先）。

所有的叶子构成一个独立集，我们找去除根后最大的。

枚举每个节点作为初始的根，换根进行$dp$。如果根本身就是叶子还要在加一。

具体来说，第一次扫描以$1$为根求出$f_{x,1/0}$表示以$x$为根的子树中$x$选/不选的最大独立集：
$\{\begin{array}{l}{f}_{x,0}={\sum }_{y\in g_x}\max (f_{y,0},f_{y,1})\\ f_{x,1}={\sum }_{y\in g_x}{f}_{y,0}\end{array}$

第二次扫描求出$h_{x,1/0}$表示选/不选$x$的最大独立集，
$h_{1,0/1}=f_{1,0/1}$，$\{\begin{array}{l}{h}_{x,0}=\max (h_{fa,1},f_{x,0}+(h_{fa,0}-\max (f_{x,1},f_{x,0})))\\ h_{x,1}=f_{x,1}+(h_{fa,0}-\max (f_{x,1},f_{x,0}))\end{array}$

用$h_{x,0}+[x\text{ is leaf}]$更新答案。

代码：

#include<bits/stdc++.h>using namespace std;
const int MOD = 998244353;void solve() {int n;cin >> n;vector<vector<int>> g(n + 1);for (int i = 1; i < n; ++i) {int x, y;cin >> x >> y;g[x].emplace_back(y);g[y].emplace_back(x);}vector<array<int, 2>> f(n + 1, {0, 0});auto dfs = [&](auto &&dfs, int x, int fa) -> void {f[x][0] = 0;f[x][1] = 1;for (int y: g[x]) {if (y != fa) {dfs(dfs, y, x);f[x][0] += max(f[y][0], f[y][1]);f[x][1] += f[y][0];}}};dfs(dfs, 1, 0);vector<array<int, 2>> h(n + 1);h[1][0] = f[1][0];h[1][1] = f[1][1];int ans = h[1][0] + (g[1].size() == 1);auto dfs2 = [&](auto &&dfs2, int x, int fa) -> void {int tmp = h[fa][0] - max(f[x][0], f[x][1]);h[x][1] = f[x][1] + tmp;h[x][0] = max(h[fa][1], f[x][0] + tmp);tmp = h[x][0] + (g[x].size() == 1);ans = max(ans, tmp);for (int y: g[x]) {if (y != fa) {dfs2(dfs2, y, x);}}};for (int y: g[1]) {dfs2(dfs2, y, 1);}cout << ans << endl;
}int main() {int t;cin >> t;while (t--)solve();return 0;
}

赛后交流

在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。

群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。

这篇关于Codeforces Global Round 26 A~E的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---