【CodeForces】Codeforces Global Round 9 【OJ】CodeForces

比赛链接点击打开链接
官方题解点击打开链接
Problem A. Sign Flipping 将奇数位的数取非正值，偶数位的数取非负值即可。
单组数据时间复杂度O ( N ) O(N) O(N) 。

#include using namespace std; const int MAXN = 3e5 + 5; typedef long long ll; template void chkmax(T &x, T y) {x = max(x, y); } template void chkmin(T &x, T y) {x = min(x, y); } template void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } int main() { int T; read(T); while (T--) { int n; read(n); for (int i = 1; i <= n; i++) { int x; read(x); if (i & 1) printf("%d ", -abs(x)); else printf("%d ", abs(x)); } printf("\n"); } return 0; }

Problem B. Neighbor Grid 若一个格子上初始时的数大于与其相邻的格子数，则答案显然为 No 。
否则，将所有格子上的数增加至与其相邻的格子数一定会形成一组合法解。
单组数据时间复杂度O ( N × M ) O(N\times M) O(N×M) 。

#include using namespace std; const int MAXN = 305; const int dx[4] = {0, 0, 1, -1}; const int dy[4] = {1, -1, 0, 0}; typedef long long ll; template void chkmax(T &x, T y) {x = max(x, y); } template void chkmin(T &x, T y) {x = min(x, y); } template void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } int n, m, a[MAXN][MAXN], d[MAXN][MAXN]; int main() { int T; read(T); while (T--) { read(n), read(m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) read(a[i][j]), d[i][j] = 0; for (int i = 1; i <= n - 1; i++) for (int j = 1; j <= m; j++) d[i][j]++, d[i + 1][j]++; for (int i = 1; i <= n; i++) for (int j = 1; j <= m - 1; j++) d[i][j]++, d[i][j + 1]++; bool ans = true; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (a[i][j] > d[i][j]) ans = false; if (ans) { puts("YES"); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) printf("%d ", d[i][j]); printf("\n"); } } else puts("NO"); } return 0; }

Problem C. Element Extermination 答案为 Yes 当且仅当a 1 ≤ a N a_1\leq a_N a1?≤aN? 。
考虑其必要性，若a 1 > a N a_1>a_N a1?>aN? ，则无论如何操作，序列中第一个元素将始终大于最后一个元素，从而不可能使序列的长度减少至2 2 2 以下。考虑其充分性，则在保证a 1 ≤ a N a_1\leq a_N a1?≤aN? 的情况下任意操作即可构造出一组消除方案，由于a 1 ≤ a N a_1\leq a_N a1?≤aN? ，序列长度≥ 2 \geq2 ≥2 的时候，一定存在可以操作的位置。
单组数据时间复杂度O ( N ) O(N) O(N) 。

#include using namespace std; const int MAXN = 3e5 + 5; typedef long long ll; template void chkmax(T &x, T y) {x = max(x, y); } template void chkmin(T &x, T y) {x = min(x, y); } template void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } int main() { int T; read(T); while (T--) { int n; read(n); int x = 0, y = 0; for (int i = 1; i <= n; i++) { int z; read(z); if (i == 1) x = z; else y = z; } if (x < y) puts("YES"); else puts("NO"); } return 0; }

Problem D. Replace by MEX 考虑通过操作序列使得a i = i ? 1 a_i=i-1 ai?=i?1 。
【【CodeForces】Codeforces Global Round 9】令序列当前的 Mex 为x( x ≤ N ) x\ (x\leq N) x (x≤N) ，显然，序列中此时不存在元素x x x 。
若x < N x 若x = N x=N x=N ，则任意操作一个尚不满足a i = i ? 1 a_i=i-1 ai?=i?1 的位置。
单组数据时间复杂度O ( N 2 ) O(N^2) O(N2) ，操作次数不超过2 N 2N 2N 。

#include using namespace std; const int MAXN = 1005; typedef long long ll; template void chkmax(T &x, T y) {x = max(x, y); } template void chkmin(T &x, T y) {x = min(x, y); } template void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } int n, a[MAXN]; int cur() { static int vis[MAXN], tag = 0; tag++; for (int i = 1; i <= n; i++) vis[a[i]] = tag; int ans = 0; while (vis[ans] == tag) ans++; return ans; } bool check() { for (int i = 2; i <= n; i++) if (a[i - 1] > a[i]) return false; return true; } int main() { int T; read(T); while (T--) { read(n); for (int i = 1; i <= n; i++) read(a[i]); vector ans; while (!check()) { int val = cur(); if (val != n) { a[val + 1] = val; ans.push_back(val + 1); } else { int pos = 0; for (int i = 1; i <= n; i++) if (a[i] != i - 1) pos = i; a[pos] = val; ans.push_back(pos); } } cout << ans.size() << endl; for (auto x : ans) printf("%d ", x); printf("\n"); } return 0; }

Problem E. Inversion SwapSort 考虑在不破坏后续元素的相对大小关系的情况下，将最小的元素移动至a 1 a_1 a1? ，同时消耗掉所有的包含位置1 1 1 的逆序对( 1 , x i ) (1,x_i) (1,xi?) 贡献的操作。
则按照a x i a_{x_i} axi?? 从大到小的顺序依次操作( 1 , x i ) (1,x_i) (1,xi?) 即可。
由此，我们将问题缩小了规模，可以递归解决。
时间复杂度O ( N 2 L o g N ) O(N^2LogN) O(N2LogN) 。

#include using namespace std; const int MAXN = 1005; typedef long long ll; template void chkmax(T &x, T y) {x = max(x, y); } template void chkmin(T &x, T y) {x = min(x, y); } template void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } int n, a[MAXN]; int main() { read(n); vector > ans; for (int i = 1; i <= n; i++) read(a[i]); for (int i = 1; i <= n; i++) { vector p; for (int j = i + 1; j <= n; j++) if (a[j] < a[i]) p.push_back(j); sort(p.begin(), p.end(), [&] (int x, int y) { if (a[x] != a[y]) return a[x] > a[y]; else return x > y; }); for (auto x : p) ans.emplace_back(i, x); } cout << ans.size() << endl; for (auto x : ans) printf("%d %d\n", x.first, x.second); return 0; }

Problem F. Integer Game 令a < b < c a 则1 1 1 号玩家可以直接取胜当且仅当2 2 2 号玩家上一次操作了c c c ，且
b ? a = c ? b b-a=c-b b?a=c?b
1 1 1 号玩家可以采取如下策略保证自己获胜：
( 1 ) (1) (1) 、令x = 1 0 9 + 7 x=10^9+7 x=109+7 ，保证在2 2 2 号玩家完成操作后，被操作的数是最大的。
( 2 ) (2) (2) 、令a < b < c , x = 2 c ? b ? a a( 3 ) (3) (3) 、令a < b < c , x = c ? b a 时间复杂度O ( 1 ) O(1) O(1) 。

#include using namespace std; const int MAXN = 3e5 + 5; typedef long long ll; template void chkmax(T &x, T y) {x = max(x, y); } template void chkmin(T &x, T y) {x = min(x, y); } template void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } ll a[4]; int res; void getres(int &res) { cin >> res; if (res == 0) exit(0); } ll gety() { ll Max = 0, ans = 0; for (int i = 1; i <= 3; i++) chkmax(Max, a[i]); for (int i = 1; i <= 3; i++) if (Max == a[i]) ans += a[i] * 2; else ans -= a[i]; return ans; } int main() { read(a[1]), read(a[2]), read(a[3]); puts("First"); int x = 1e9 + 7; cout << x << endl; getres(res); a[res] += x; ll y = gety(); cout << y << endl; getres(res); a[res] += y; sort(a + 1, a + 4); assert(a[2] - a[1] == a[3] - a[2]); cout << a[2] - a[1] << endl; getres(res), assert(false); return 0; }

Problem G. Tree Modification 枚举最终形成的菊花的中心x x x ，考虑如何以最少的操作次数完成转化。
令距离x x x 为偶数的节点数为A n s Ans Ans ，则不难构造出一种A n s ? 1 Ans-1 Ans?1 次操作的方案。并且，考虑图的二分图染色，可以发现，一次操作仅改变了一个点的颜色，因此A n s ? 1 Ans-1 Ans?1 也是操作次数的下界。
由此，答案即为将图二分图染色后，点数较少的颜色的点数? 1 -1 ?1 。
由于写程序的时候没有分析透彻，下文的代码使用了换根树形 DP 的方式计算了以上数值。
时间复杂度O ( N ) O(N) O(N) 。

#include using namespace std; const int MAXN = 2e5 + 5; typedef long long ll; template void chkmax(T &x, T y) {x = max(x, y); } template void chkmin(T &x, T y) {x = min(x, y); } template void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } int ans, dp[MAXN][2], sum[MAXN][2]; vector a[MAXN]; void update(int pos) { dp[pos][0] = sum[pos][1] + 1; dp[pos][1] = sum[pos][0]; } void getdp(int pos, int fa) { for (auto x : a[pos]) if (x != fa) { getdp(x, pos); sum[pos][0] += dp[x][0]; sum[pos][1] += dp[x][1]; } update(pos); } void getans(int pos, int fa) { chkmin(ans, dp[pos][0] - 1); for (auto x : a[pos]) if (x != fa) { sum[pos][0] -= dp[x][0]; sum[pos][1] -= dp[x][1]; update(pos); sum[x][0] += dp[pos][0]; sum[x][1] += dp[pos][1]; update(x); getans(x, pos); sum[x][0] -= dp[pos][0]; sum[x][1] -= dp[pos][1]; update(x); sum[pos][0] += dp[x][0]; sum[pos][1] += dp[x][1]; update(pos); } } int main() { int n; read(n); for (int i = 1; i <= n - 1; i++) { int x, y; read(x), read(y); a[x].push_back(y); a[y].push_back(x); } ans = n + 1; getdp(1, 0); getans(1, 0); cout << ans << endl; return 0; }

Problem H. Set Merging 首先，考虑一个操作次数N 2 N^2 N2 的解法，我们需要对所有区间，求出对应的集合。
考虑对权值分治，令M = ? N 2 ? M=\lfloor\frac{N}{2}\rfloor M=?2N?? ，首先求出数组a i a_i ai? 权值在[ 1 , M ] [1,M] [1,M] 内的子序列所有区间对应的集合，以及数组a i a_i ai? 权值在[ M + 1 , N ] [M+1,N] [M+1,N] 内的子序列所有区间对应的集合。此时，原数组的任意一个区间对应的集合都可以通过不少于一次操作获得。
考虑分析其操作次数T ( N ) T(N) T(N) ，有
T ( N ) = ( N + 1 2 ) + T ( ? N 2 ? ) + T ( ? N 2 ? ) ≈ N 2 T(N)=\binom{N+1}{2}+T(\lfloor\frac{N}{2}\rfloor)+T(\lceil\frac{N}{2}\rceil)\approx N^2 T(N)=(2N+1?)+T(?2N??)+T(?2N??)≈N2
对于原问题，考虑对权值进行分块处理，令块长为B B B ，则总操作次数约为
N B × B 2 + Q × N B \frac{N}{B}\times B^2+Q\times \frac{N}{B} BN?×B2+Q×BN?
那么，令B = Q B=\sqrt{Q} B=Q ? 即可。
时间复杂度O ( N 2 + N Q ) O(N^2+N\sqrt{Q}) O(N2+NQ ?) ，操作次数约为2 N Q 2N\sqrt{Q} 2NQ ? 。

#include using namespace std; const int MAXN = 5005; const int MAXQ = 2e5 + 5; const int Limit = 2.2e6; typedef long long ll; template void chkmax(T &x, T y) {x = max(x, y); } template void chkmin(T &x, T y) {x = min(x, y); } template void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } struct info { int l[MAXN], r[MAXN]; vector > home; void init(int x) { home.resize(x + 1); for (int i = 0; i <= x; i++) home[i].resize(x + 1); } int query(int ql, int qr) { if (l[ql] > r[qr]) return 0; else return home[l[ql]][r[qr]]; } } res[MAXN]; int n, q, size, a[MAXN], b[MAXN], k[MAXQ]; int tot, block, ql[MAXN], qr[MAXN], belong[MAXN]; vector > ans; int merge(int x, int y) { if (x == 0 || y == 0) return x + y; ans.emplace_back(x, y); assert(++size <= Limit); return size; } info getres(int l, int r) { if (l == r) { info ans; for (int i = 1; i <= n; i++) { ans.l[i] = 1 + (i > b[l]); ans.r[i] = (i >= b[r]); } ans.init(1); ans.home[1][1] = b[l]; return ans; } int mid = (l + r) / 2; info ans, ansl, ansr; ansl = getres(l, mid); ansr = getres(mid + 1, r); for (int i = 1, j = 1, k = 0; i <= n; i++) { k += (l <= a[i] && a[i] <= r); ans.l[i] = j, ans.r[i] = k; j += (l <= a[i] && a[i] <= r); } ans.init(r - l + 1); for (int i = 1; i <= n; i++) if (l <= a[i] && a[i] <= r) { for (int j = i; j <= n; j++) if (l <= a[j] && a[j] <= r) { ans.home[ans.l[i]][ans.r[j]] = merge(ansl.query(i, j), ansr.query(i, j)); } } return ans; } int main() { read(n), read(q), size = n; for (int i = 1; i <= n; i++) read(a[i]), b[a[i]] = i; block = 1 << 8; for (int i = 1; i <= n; i++) { if (i % block == 1 % block) ql[++tot] = i; qr[tot] = i, belong[i] = tot; } for (int i = 1; i <= tot; i++) res[i] = getres(ql[i], qr[i]); for (int i = 1; i <= q; i++) { int ql, qr, cur = 0; read(ql), read(qr); for (int j = 1; j <= tot; j++) cur = merge(cur, res[j].query(ql, qr)); k[i] = cur; } printf("%d\n", size); for (auto x : ans) printf("%d %d\n", x.first, x.second); for (int i = 1; i <= q; i++) printf("%d ", k[i]); printf("\n"); return 0; }