比赛链接：https://codeforces.com/contest/1546
A. AquaMoon and Two Arrays 题意给出两个大小为 \(n\) 的数组 \(a, b\) ，每次可以选择 \(a\) 中的两个元素分别加一减一，计算将 \(a\) 变为 \(b\) 的操作次数和步骤。
题解数据范围较小，直接模拟即可。
若数据范围较大，可用栈或队列分别存储 \(a_i \lt b_i\) 和 \(a_i \gt b_i\) 的数，这样每次查找的时间复杂度就降到了 \(O_{(1)}\) 。
代码 #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n), b(n); int suma = 0, sumb = 0; for (int i = 0; i < n; i++) { cin >> a[i]; suma += a[i]; } for (int i = 0; i < n; i++) { cin >> b[i]; sumb += b[i]; } if (suma != sumb) { cout << -1 << "\n"; continue; } vector<pair<int, int>> op; for (int i = 0; i < n; i++) { while (a[i] < b[i]) { for (int j = i + 1; j < n; j++) { if (a[j] > b[j]) { --a[j], ++a[i]; op.emplace_back(j, i); break; } } } while (a[i] > b[i]) { for (int j = i + 1; j < n; j++) { if (a[j] < b[j]) { --a[i], ++a[j]; op.emplace_back(i, j); break; } } } } cout << op.size() << "\n"; for (auto [x, y] : op) { cout << x + 1 << ' ' << y + 1 << "\n"; } } return 0; } B. AquaMoon and Stolen String 题意有 \(n\) 个字符串，将 \(n - 1\) 个字符串中同一位上的字符相互交换，给出原来的 \(n\) 个字符串和操作后的 \(n - 1\) 个字符串，找出那个未被操作的字符串。
题解将同一位上的字符异或相消，最后剩下的就是未被操作字符串的字符。
代码 #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n, m; cin >> n >> m; string ans(m, 0); for (int i = 0; i < 2 * n - 1; i++) { string s; cin >> s; for (int j = 0; j < m; j++) { ans[j] ^= s[j]; } } cout << ans << "\n"; } return 0; } C. AquaMoon and Strange Sort 题意给出 \(n\) 个数，初始时均朝右（朝向不影响数值大小），每次操作可以选取相邻的两个数交换位置并反转朝向，判断能否将 \(n\) 个数排为升序后仍都朝右。
题解若一个数操作后仍朝右，那么它移动的距离一定是 2 的倍数，即位置的奇偶性不变，判断排序前后同一值的奇偶位置个数是否相同即可。
代码 #include <bits/stdc++.h> using namespace std; constexpr int N = 1e5 + 10; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<vector<int>> pos_before(N, vector<int> (2)); for (int i = 0; i < n; i++) { ++pos_before[a[i]][i & 1]; } sort(a.begin(), a.end()); vector<vector<int>> pos_after(N, vector<int> (2)); for (int i = 0; i < n; i++) { ++pos_after[a[i]][i & 1]; } cout << (pos_before == pos_after ? "Yes" : "No") << "\n"; } return 0; } D. AquaMoon and Chess 题意给出一个 01 串，每个 1 只能隔着一个 1 与 0 交换位置，计算 01 串最终可能状态的个数。
题解将相邻的两个 1 看作一个整体，设 0 的个数为 \(n\) ，无交集的 11 个数为 \(m\) ，答案即 \(C_{n + m}^{m}\) 。
在奇数长度的连续 1 串中，有一个 1 因为无法移动，在所有可能状态中的位置都是固定的。
代码 #include <bits/stdc++.h> using namespace std; constexpr int N = 1e6 + 100; constexpr int MOD = 998244353; int fac[N], inv[N]; int binpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = 1LL * res * a % MOD; a = 1LL * a * a % MOD; b >>= 1; } return res; } int C(int n, int m){ if(m < 0 or m > n) return 0; return 1LL * fac[n] * inv[m] % MOD * inv[n - m] % MOD; } void Init(){ fac[0] = 1; for (int i = 1; i < N; i++) fac[i] = 1LL * fac[i - 1] * i % MOD; inv[N - 1] = binpow(fac[N - 1], MOD - 2); for (int i = N - 2; i >= 0; i--) inv[i] = 1LL * inv[i + 1] * (i + 1) % MOD; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); Init(); int t; cin >> t; while (t--) { int n; cin >> n; string s; cin >> s; int one = 0; for (int i = 0; i + 1 < n; i++) { if (s[i] == '1' and s[i + 1] == '1') { ++one, ++i; } } int zero = count(s.begin(), s.end(), '0'); cout << C(one + zero, one) << "\n"; } return 0; } 参考https://codeforces.com/blog/entry/92739
后记蛮有思维难度的一场比赛，学到很多 (￣▽￣) /