A. Shift Sort
题意：一个\(01\)串，每次可以选择\(i, j, k\)三个位置让它们左移或右移，求使得字符串升序的最小操作数。
记有\(cnt\)个\(0\)，如果一个\(0\)不在前\(cnt\)个位置里，那么它需要一次交换，且每次交换最多让一个\(0\)复位。所以这样位置的个数就是答案。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::string s;std::cin >> n >> s;int cnt = std::ranges::count(s, '0');int ans = 0;for (int i = 0; i < cnt; ++ i) {ans += s[i] == '1';}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
B. Another Divisibility Problem
题意：给你一个\(x\)，求一个\(y\)，使得\(x+y\)整除\(x\)和\(y\)拼接后的数字。
记\(y\)有\(k\)位，那么\(x+y = x\times 10^k + y\)，减去一个\(x+y\)后等于\(x\times (10^k - 1)\)，这个数要整除\(x+y\)，那么\(x+y\)得是\(x\)的倍数，则\(y\)是\(x\)的倍数。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {i64 x;std::cin >> x;for (i64 y = x; ; y += x) {std::string s = std::to_string(x) + std::to_string(y);i64 z = 0;for (auto & x : s) {z = z * 10 + x - '0';}if (z % (x + y) == 0) {std::cout << y << "\n";return;}}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
C. Ultimate Value
题意：一个数字\(a\)的代价为加上奇数位的和减去偶数的的和加\(cost\)，其中\(cost\)为操作中产生的代价。\(Alice\)和\(Bob\)两个人轮流操作，\(Alice\)先手，每次操作选择一个\(i, j(i < j)\)交换\(a_i, a_j\)，\(cost\)增加\(j - i\)，或者终止操作。\(Alice\)希望代价最大，\(Bob\)希望最小。求最终代价。
结论是\(Alice\)要么直接终止，要么操作一次后\(Bob\)直接终止。
因为如果轮到\(Bob\)操作，发现交换\(i, j\)会减少代价，那么之后\(Alice\)可以重复交换\(i, j\)，这样数组没变，代价增加了\(2\times(j-i)\)。不如直接终止比赛。
那么问题就变为最多交换一次后的最大代价。
如果交换的数的位置奇偶性相同，代价为\(j-i\)。
如果\(i\)是奇数，\(j\)是偶数，那么代价增加\(2\times a_j + j - 2\times a_i - i\)。这个可以从后往前做，记录一个\(max2\)表示偶数位置最大的\(2\times a_j - j\)。
同理如果\(i\)是偶数，\(j\)是奇数，代价增加\(2\times a_i - i - 2\times a_j - j\)。也可以维护一个\(max1\)。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<i64> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}i64 ans = 0;for (int i = 0; i < n; ++ i) {ans += i % 2 ? -a[i] : a[i];}i64 max = n % 2 ? n - 1 : n - 2;i64 max1 = -1e18, max2 = -1e18;for (int i = n - 1; i >= 0; -- i) {if (i % 2 == 0) {max = std::max(max, max2 - 2 * a[i] - (i + 1));max1 = std::max(max1, -2 * a[i] + (i + 1));} else {max = std::max(max, max1 + 2 * a[i] - (i + 1));max2 = std::max(max2, 2 * a[i] + (i + 1));}}std::cout << ans + max << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
D. A Cruel Segment's Thesis
题意：\(n\)个\([l, r]\)，价值原来的所有\(r-l\)的和，然后你需要两两匹配，价值加上\(l_i \leq x \leq r_i, l_j \leq y \leq r_j\)的\(y - x\)的最大值。如果\(n\)是偶数则留一个不匹配。求最大价值。
一个区间对答案的贡献是要么被加上\(r\)，要么被减去\(l\)。那么加上所有区间的\(r\)都是加上的，然后考虑选出\(\lfloor \frac{n}{2} \rfloor\)个\(l_i\)减去，这样的区间因为之前加过\(r\)，现在又减去\(l\)，所以贡献加上\(-r_i - l_i\)。那么选出最大的\(\lfloor \frac{n}{2} \rfloor\)个这样的贡献。
然后如果\(n\)是偶数，可以匹配完，直接加上前一半就行，如果\(n\)是奇数，考虑枚举不匹配的区间，然后根据这个区间的\(-r_i - l_i\)是不是前\(\lfloor \frac{n}{2} \rfloor\)个大的讨论即可，选择使得贡献减少最小的区间。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;i64 ans = 0;std::vector<i64> l(n), r(n);std::vector<std::pair<i64, int>> a(n);for (int i = 0; i < n; ++ i) {std::cin >> l[i] >> r[i];ans += r[i] - l[i];a[i] = {-r[i] - l[i], i};ans += r[i];}std::ranges::sort(a, std::greater<>());std::vector<int> st(n);i64 sum = 0;for (int i = 0; i < n / 2; ++ i) {sum += a[i].first;st[a[i].second] = 1;}if (n % 2 == 0) {ans += sum;} else {i64 max = -1e18;for (int i = 0; i < n; ++ i) {if (!st[i]) {max = std::max(max, -r[i] + sum);} else {max = std::max(max, sum - (-r[i] - l[i]) - r[i] + a[n / 2].first);}}ans += max;}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;std::cin >> t;while (t -- ) {solve();}return 0;
}
E1. Prime Gaming (Easy Version)
题意：有\(n\)堆石头，每堆的石头数在\([1, m]\)之间。有些位置是可以操作的，\(Alice\)和\(Bob\)轮流操作，每次选择一个可以操作的位置把这个位置上的石堆删掉，然后后面的往前移。最后剩下的一堆的石头数就是价值。\(Alice\)希望价值最大，\(Bob\)希望价值最小。求所有情况下的价值总和。
\(n \leq 20, m \leq 2\)。
如果\(m=1\)，答案是\(1\)。
记\(f[i][0/1][s]\)表示长度为\(i\)的数组，轮到\(Alice/Bob\)操作，且状态为\(s\)能否取到\(2\)。其中\(s\)是一个二进制数，第\(i\)位为\(0\)表示第\(i\)堆石头有一个石头，否则有两个石头。
那么枚举操作的位置，预处理一个\(ns[s][k]\)表示删掉\(s\)的第\(k\)位后的状态，就可以枚举操作的位置转移，其中\(Alice\)只需要有一个为\(1\)的状态能转移过来就是\(1\)，\(Bob\)只需要有一个为\(0\)的状态转移过来就是\(0\)。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;const int mod = 1e9 + 7;bool f[21][2][1 << 20];
int ns[1 << 20][20];
int c[20];void init() {for (int s = 0; s < 1 << 20; ++ s) {int x = 0;for (int i = 0; i < 20; ++ i) {int y = x;for (int j = i + 1; j < 20; ++ j) {if (s >> j & 1) {y |= 1 << (j - 1);}}ns[s][i] = y;if (s >> i & 1) {x |= 1 << i;}}}
}void solve() {int n, m;std::cin >> n >> m;int k;std::cin >> k;memset(c, 0, sizeof c);for (int i = 0; i < k; ++ i) {int x;std::cin >> x;c[x - 1] = 1;}if (m == 1) {std::cout << 1 << "\n";return;}f[1][0][1] = f[1][1][1] = 1;f[1][0][0] = f[1][1][0] = 0;for (int i = 2; i <= n; ++ i) {for (int s = 0; s < 1 << i; ++ s) {f[i][0][s] = 0;for (int k = 0; k < i; ++ k) {if (c[k]) {f[i][0][s] |= f[i - 1][1][ns[s][k]];}}f[i][1][s] = 1;for (int k = 0; k < i; ++ k) {if (c[k]) {f[i][1][s] &= f[i - 1][0][ns[s][k]];}}}}int ans = 0;for (int s = 0; s < 1 << n; ++ s) {ans = (ans + f[n][0][s] + 1) % mod;}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;init();std::cin >> t;while (t -- ) {solve();}return 0;
}