【Codeforces】Codeforces|【Codeforces】Codeforces Round #531 【Codeforces】CodeforcesRound#531

Problem A 从n个数的和，也就是入手。
如果和为奇数，显然无法二等分，其最小的差只能为1。
如果和为偶数，显然其可以二等分，故其最小的差可以为0。
具体的分割策略的话，可以求出向下取整，然后在n个数中找出部分数凑出这个数，剩下的作为另一部分。自行dp一下可以发现这总能够凑得出来的。

类比一下用不同面额的金币凑出各种金额的问题就行了。实在不行自己写个dp验证一下。

时间复杂度为

#include using namespace std; int main() { int n; while(cin >> n) { n = (n + 1) >> 1; cout << n%2 << endl; } return 0; }

Problem B 首先，先列出会输出NO的情况：

颜色太少（k太小）
颜色太多（k太大）

对于第二种情况的话，当且仅当的时候会发生。
而对于第一种情况的话，当且仅当k小于最少使用颜色数的时候会发生。
重点在于最少使用颜色数。这个其实就是数组a中重复次数最多的元素重复的次数。
排除掉NO的情况之后，k种颜色的涂法就是：

先按最少使用颜色数的方案涂（枚举1到k，每次用该颜色涂尽可能多的元素）
然后看还剩多少种颜色需要涂，去找重复颜色的块去涂即可（例如，有两个元素都是颜色1的话，其中就有一个可以涂成别的颜色）

用最暴力的方法来做的话，时间复杂度为

#include #include using namespace std; int main() { int a[5005], n, k; int ans[5005]; while(cin >> n >> k) { for(int i = 0; i < n; i++) { cin >> a[i]; } memset(ans, -1, sizeof(ans)); if(n < k) { cout << "NO" << endl; continue; }int cnt = 0; for(int i = 1; i <= k; i++) { bool vis[5005] = {0}; if(cnt == n) { for(int j = 0; j < n; j++) { if(vis[ans[j]]) { ans[j] = i; i++; if(i > k) { break; } } else { vis[ans[j]] = true; } } } else { for(int j = 0; j < n; j++) { if(ans[j] == -1) { if(vis[a[j]]) { continue; } vis[a[j]] = true; ans[j] = i; cnt++; } } } }if(cnt == n) { cout << "YES" << endl; for(int i = 0; i < n; i++) { if(i) { cout << " "; } cout << ans[i]; } cout << endl; } else { cout << "NO" << endl; } } return 0; }

Problem C 分情况讨论：
如果的话，显然跟他慢慢耗总能踹爆所有门的，答案为n。
否则，只要无法一次踹爆的门他都能跟你耗让那个门耐久越来越高。所以需要挑能一次踹爆的门下手。当然他也知道这一点，所以每当你一次踹爆一个门的时候他就会修一个【能被你一次踹爆的门】，使其成为【无法被你一次踹爆的门】。直接计算即可。
时间复杂度为

#include using namespace std; int a[1005]; int main() { int n, x, y; while(cin >> n >> x >> y) { for(int i = 0; i < n; i++) { cin >> a[i]; }if(x > y) { cout << n << endl; } else { int cnt = 0; for(int i = 0; i < n; i++) { if(a[i] <= x) { cnt++; } } cout << (cnt + 1) / 2 << endl; } } return 0; }

Problem D 考虑两种情况：

小的数位有多出的，大的数位有缺少的：为了让字典序最小，我们需要尽可能的替换掉靠后的小的数位为更大的数位。
大的数位有多出的，小的数位有缺少的：为了让字典序最小，我们需要尽可能的替换掉靠前的大的数位为更小的数位。

基于这个思想写个函数然后对所有可能的数位组合（其实就三种：0和1，0和2，1和2）调用一下就行了。
时间复杂度为

#include #include #include using namespace std; string s; int cnt[5], n; void Fix(int a, int b) { int pos = 0; while((cnt[a] < 0) && (cnt[b] > 0)) { if(s[pos] == b + '0') { s[pos] = a + '0'; cnt[a]++; cnt[b]--; } pos++; }pos = n - 1; while((cnt[b] < 0) && (cnt[a] > 0)) { if(s[pos] == a + '0') { s[pos] = b + '0'; cnt[b]++; cnt[a]--; } pos--; } }int main() { while(cin >> n) { cin >> s; for(int i = 0; i < 3; i++) { cnt[i] = -1 * (n / 3); } for(int i = 0; i < n; i++) { cnt[s[i] - '0']++; }Fix(0, 2); Fix(0, 1); Fix(1, 2); cout << s << endl; } return 0; }

Problem E 一个显然的性质是，对于任意区间，如果，那么对于数组而言，这个区间内的数必须相同。
于是我们便可以提出若干个这样的区间，然后对这些区间进行合并（有相交区域的区间可以合并成一个新的大区间），最终我们可以得到若干个互不相交的区间。
设这些区间数为，那么答案显然就是。
提取区间的话我们可以使用一个map用于记录每种数字的最大下标。那么合并区间的话我们便可以从左往右扫，每次通过这个map来更新区间右值，直至无法更新为止。
时间复杂度为

#include #include #include using namespace std; typedef long long LL; const LL mod = 998244353; LL GetAns(int p) { p -= 1; LL ans = 1; while(p--) { ans <<= 1; ans %= mod; } return ans; }map mapR; int a[200005]; int FindR(int pos) { int ret = pos; for(int i = pos; i <= ret; i++) { ret = max(ret, mapR[a[i]]); } return ret; }int main() { int n; while(~scanf("%d",&n)) { mapR.clear(); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); mapR[a[i]] = i; }int pos = 0; int cnt = 0; while(pos < n) { pos = FindR(pos) + 1; cnt++; }printf("%lld\n", GetAns(cnt)); } return 0; }

Problem F 【【Codeforces】Codeforces|【Codeforces】Codeforces Round #531】首先需要计算出对于任意两行（第i行和第j行）：

如果第j行接在第i行下面的话，两行中每列的两个数的差的绝对值的最小值
如果以第i行为结尾，第j行为开头的话，第i行中每个数与第j行中同样位置的下一个数的差的绝对值的最小值（也就是）

对于第一个计算的量而言，将每一行看作是一个点，且每个针对有序数对计算出来的量作为从点i到点j的有向边的权值。就可以构成一个有向图（我们假设该有向图为图A）。以同样的方法对第二个计算出来的量建图可以得到另一个有向图B。
于是问题就转换为，在有向图A中求一条路径使其经过所有的点，且【所经过的边的权值】和【这条路径上的终点和起点在图B上的边的权值】的最小值最大。
对于前者的话显然就是一个旅行商问题的变体，照着旅行商问题的解法便可以解出来。现在需要处理掉的是后者。事实上我们可以通过枚举起点来简化后者的问题。对于每个枚举的起点求出【经过所有点的权值的最小值最大】的路径。根据终点不同会有n条不同的路径。然后对这些路径再去查图B再求一遍两两最小，然后从中取最大即可。
不知道旅行商问题的同学可以自行学习一下状态压缩dp。旅行商问题算是状态压缩dp的一个入门题目。
总的时间复杂度为，前者为建图过程的复杂度，后者为枚举起点+状压dp的时间复杂度。

#include #include #include #include #include using namespace std; const int INF = 1.5e9; int e[25][25], nxt[25][25]; int a[25][10005]; void Build(int &n, int &m) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { int w = INF; for(int k = 0; k < m; k++) { w = min(w, abs(a[i][k] - a[j][k])); } e[i][j] = w; w = INF; for(int k = 1; k < m; k++) { w = min(w, abs(a[i][k-1] - a[j][k])); } nxt[i][j] = w; } } }int dp[70000][25]; int GetAns(int &src, int &n) { memset(dp, -1, sizeof(dp)); dp[1 << src][src] = INF; for(int bitm = 1; bitm < (1 << n); bitm++) { for(int i = 0; i < n; i++) { if(!(bitm & (1 << i)))continue; for(int j = 0; j < n; j++) { if(i == j)continue; if(!(bitm & (1 << j)))continue; if(bitm == (1 << j))continue; dp[bitm][i] = max(dp[bitm][i], min(dp[bitm - (1 << i)][j], e[j][i])); } } }int ret = -1; for(int i = 0; i < n; i++) { ret = max(ret, min(dp[(1 << n) - 1][i], nxt[i][src])); } return ret; }int main() { int n, m; while(~scanf("%d%d", &n, &m)) { for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { scanf("%d", &a[i][j]); } }Build(n, m); int ans = -1; for(int i = 0; i < n; i++) { ans = max(ans, GetAns(i, n)); } printf("%d\n", ans); } return 0; }