Codeforces Round #732 (Div. 2)【ABCD】

比赛链接: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

后记

蛮有思维难度的一场比赛,学到很多 ( ̄▽ ̄) /

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zzgdws.html