A. Shift Sort
给定一个长度为 \(n\) 的二进制字符串 \(s\)，你可以进行如下操作任意次（包括零次）：
选择三个下标 \(1 \le i < j < k \le n\)，然后将 \(s_i, s_j, s_k\) 的值循环地向右或向左移动。
例如，对于二进制字符串 \(110110\)：
- 如果选择 \(i=1, j=2, k=3\) 并执行一次循环右移，字符串变为 \(011110\)；
- 如果选择 \(i=4, j=5, k=6\) 并执行一次循环左移，字符串变为 \(110101\)。
请你求出将给定二进制字符串排序所需的最小操作次数。
操作等价与交换一个 \(1\) 和一个 \(0\)，双指针模拟即可。
代码
#include <bits/stdc++.h>using namespace std;typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000086, MOD = 998244353, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];char s[N];
void solve() {res = 0;int l = 1, r = n;while (l < r) {while (l < r && s[l] == '0') l++;while (l < r && s[r] == '1') r--;if (l == r) break;swap(s[l], s[r]), res++;}printf("%lld\n", res);
}int main() {int T;cin >> T;while (T--) {cin >> n;scanf("%s", s + 1);solve();}return 0;
}
B. Another Divisibility Problem
Alice 和 Bob 在玩一个游戏，其中 Alice 给了 Bob 一个正整数 \(x < 10^8\)。
为了赢得游戏，Bob 需要找到另一个正整数 \(y < 10^9\)，使得 \(x \# y\) 可以被 \(x + y\) 整除。
这里 \(x \# y\) 表示将整数 \(x\) 和 \(y\) 按顺序拼接后形成的新整数。例如，如果 \(x = 835, y = 47\)，那么 \(x \# y = 83547\)。
然而，由于 Bob 很笨，他没办法找到这样的整数。请你来帮助他。
可以证明，这样的整数总是存在的。
令 \(y = 2x\)，此时 \(x + y = 3x\)，\(x \# y = 10\ldots 02x\)，\((x + y) \mid (x\#y)\)。
代码
#include <bits/stdc++.h>using namespace std;typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000086, MOD = 998244353, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];int main() {int T;cin >> T;while (T--) {cin >> n;printf("%d\n", n << 1);}return 0;
}
C. Ultimate Value
我们定义一个函数 \(f(a)\)，其中 \(a\) 是一个长度为 \(n\) 的数组：
\[f(a) = cost + (a_1 - a_2 + a_3 - a_4 + \cdots \pm a_n) \]其中 \(cost\) 初始为 0。
现在考虑这样一个场景：Alice 和 Bob 得到一个长度为 \(n\) 的数组 \(a\)。他们轮流进行游戏，最多可以进行 \(10^{100}\) 步，Alice 先手。
在每一回合中，他们必须执行以下操作之一（只能选择一个）：
- 结束游戏。
- 选择两个下标 \(l, r\)，其中 \(1 \leq l \leq r \leq n\)，交换 \(a_l\) 和 \(a_r\)；这一操作会使 \(cost\) 增加 \((r - l)\)。
假设 Alice 的目标是最大化 \(f(a)\)，而 Bob 的目标是最小化 \(f(a)\)。
你的任务是求出在双方都采取最优策略时，\(f(a)\) 的最终值。
在 Bob 进行操作交换 \(l,r\) 后，Alice 可以选择交换相同的 \(l,r\)，因此 Alice 每次操作都能够使 \(f(a)\) 变得比 Alice 上一次操作后更大，Bob 的最优做法是直接结束游戏。问题变为最多进行 \(1\) 次操作的 \(f(a)\) 的最大值。
如果 \(l,r\) 奇偶性相同，显然 \(r - l\) 最大时最优；如果 \(l\) 为奇数 \(r\) 为偶数，交换对答案的影响为 \(-2a_l + 2a_r + r - l\)，分成两部分 \(-2al - l\) 和 \(2ar + r\)，可以从左到右枚举，维护当前前缀奇数位置中 \(-2a_i - i\) 最大值 \(u\)，如果当前位置 \(i\) 为偶数，交换 \(i\) 和前面某个奇数的最大影响是 \(2a_i + i + u\)，当 \(l\) 为偶数 \(r\) 为奇数时影响为 \(2a_l - 2a_r + r - l = 2a_l - l - 2a_r + r\)，此时维护前缀偶数位置 \(2a_i - i\) 的最大值 \(v\)，对每个奇数位置计算 \(-2a_i + i + v\)。
代码
#include <bits/stdc++.h>using namespace std;typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000086, MOD = 998244353, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];void solve() {res = 0;for (int i = 1; i < n + 1; i++) res += w[i] * (i & 1 ? 1 : -1);priority_queue<ll, vector<ll>, less<ll> > q1, q2;ll t = (n - 1) % 2 == 0 ? n - 1 : n - 2;for (int i = 1; i < n + 1; i++) {if (i & 1) {if (q2.size()) t = max(t, -2ll * w[i] + i + q2.top());q1.push(-w[i] * 2ll - i);} else {if (q1.size()) t = max(t, 2ll * w[i] + i + q1.top());q2.push(w[i] * 2ll - i);}}printf("%lld\n", res + t);
}int main() {int T;cin >> T;while (T--) {cin >> n;for (int i = 1; i < n + 1; i++) scanf("%d", w + i);solve();}return 0;
}
D. A Cruel Segment's Thesis
给定数轴上的 \(n\) 个线段。第 \(i\) 个线段表示为 \([l_i, r_i]\)。最初，所有线段都是未标记的。
你重复执行以下操作，直到没有未标记的线段为止：
- 在第 \(k\) 次操作中，如果至少有两个未标记的线段，选择任意两个未标记线段 \([l_i, r_i]\) 和 \([l_j, r_j]\)，将它们都标记，并添加一个新的标记线段 \([x_k, y_k]\)，满足：$$l_i \le x_k \le r_i, \quad l_j \le y_k \le r_j, \quad x_k \le y_k$$
- 如果只剩下一个未标记的线段，则将它标记。
你的任务是求出在整个过程中，所有标记线段长度的最大可能和。注意，线段 \([l, r]\) 的长度为 \(r - l\)。
一次游戏等价与对每一条线段 \(i\)，先为结果加上 \(r_i - l_i\)，然后从 \(n\) 条线段中选出 \(\lfloor \frac{n}{2} \rfloor\) 条线段放入第一个集合，再从剩下的 \(\lfloor \frac{n + 1}{2} \rfloor\) 条线段中选出 \(\lfloor \frac{n}{2} \rfloor\) 条线段放入第二个集合，为结果加上第二个集合中每条线段的右端点并减去第一个集合中每条线段的左端点。
考虑 \(n\) 为偶数的情况，我们可以先把所有的线段放入第一个集合，然后从中选出 \(\frac{n}{2}\) 条线段放到第二个集合。对于某条线段 \(i\)，将其从第一个集合转移到第二个集合对结果的影响为 \(l_i + r_i\)，要使结果最大，应该尽可能去取 \(l + r\) 更大的线段。因此对所有线段按照 \(l + r\) 排序，将后面 \(\frac{n}{2}\) 条线段放入第二个集合。
当 \(n\) 为奇数时，存在一条线段，既不放入第一个集合也不放入第二个集合，可以枚举这条线段，剩下 \(n - 1\) 条线段的最大值用前缀和维护。
代码
#include <bits/stdc++.h>using namespace std;typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000086, MOD = 998244353, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];struct Edge {int l, r;
}e[N];
struct Node {int a, b;bool operator<(const Node& w) const {return a < w.a;}
}f[N];
ll s[N];void solve() {bool flag = 0;res = 0;for (int i = 1; i < n + 1; i++) res += e[i].r - e[i].l;priority_queue<pii, vector<pii>, less<pii> > q;for (int i = 1; i < n + 1; i++) {res -= e[i].l, f[i].a = e[i].l + e[i].r, f[i].b = e[i].l;}sort(f + 1, f + n + 1);for (int i = 1; i < n + 1; i++) s[i] = s[i - 1] + f[i].a;if (n & 1) {ll sum = res;for (int i = 1; i < n + 1; i++) {if (i <= n / 2 + 1) res = max(res, sum + s[n] - s[n / 2 + 1] + f[i].b);else res = max(res, sum + s[n] - s[n / 2] - f[i].a + f[i].b);}} else {res += s[n] - s[n >> 1];}printf("%lld\n", res);
}
int main() {int T;cin >> T;while (T--) {cin >> n;for (int i = 1; i < n + 1; i++) scanf("%d%d", &e[i].l, &e[i].r);solve();}return 0;
}
E1. Prime Gaming (Easy Version)
这是问题的简单版本。本版本与其他版本的区别在于 \(m \le 2\)。
一个有效配置定义为 \(n\) 堆石子的排列，满足：
- 每堆石子的数量是介于 \(1\) 到 \(m\) 之间的整数（包括 \(1\) 和 \(m\)）。
对于一个有效的 \(n\) 堆石子配置，某些从 \(1\) 到 \(n\) 的下标被标记为“好”。Alice 和 Bob 轮流进行游戏，总共 \(n-1\) 回合，Alice 先手。在每一回合中，他们必须执行以下操作：- 选择任意整数 \(i\)，满足 \(1 \le i \le p\)（其中 \(p\) 是剩余的石子堆数）且 \(i\) 是好下标，然后完全移除第 \(i\) 堆石子。
注意，每次操作后，剩余石子堆的数量会减 1，并重新编号。游戏在只剩下一堆石子时结束。保证下标 \(1\) 始终是好下标。
设 \(x\) 为最终剩余石子堆的石子数量。Alice 希望最大化 \(x\)，而 Bob 希望最小化 \(x\)。两人都采取最优策略。
求所有可能的有效配置中 \(x\) 的总和，对 \(10^9+7\) 取模。
当 \(m\) 为 \(1\) 时，只有 \(1\) 种配置且 \(x\) 为 \(1\)。
当 \(m\) 为 \(2\) 时，由于双方都是最优策略，任意配置的最终结果都是确定的。令 \(f_{i,j}\) 为当前还剩下 \(i\) 堆石子，所有石子的状态为 \(j\) 时的最终结果，对于第 \(i\) 堆石子，如果 \(j\) 的 \(i - 1\) 位为 \(1\)，则这堆石子数量为 \(2\) 个，否则为 \(1\) 个。初始状态为 \(f_{1,0} = 1, f_{1, 1} = 2\)。对于 \(f_{i,j}\)，如果 \(i > 1\) 且存在 \(k\) 满足 \(k\) 是好下标且 \(i \ge k\)，则 \(f_{i,j}\) 可以从 \(f_{i-1,\, (j \gg k \ll (k-1)) \mid (j \& ((1 \ll (k-1)) - 1))}\) 转移，如果当前是 Alice 操作，若存在可转移状态结果为 \(2\)，则 \(f_{i,j} = 2\)，否则 \(f_{i,j} = 1\)；如果当前是 Bob 操作，若存在可转移状态结果为 \(1\)，则 \(f_{i,j} = 1\)，否则 \(f_{i,j} = 1\)。\(x\) 的总和就是 \(\sum_{j=1}^{(1 \ll n) - 1} f_{n,j}\)，第一维可以通过滚动数组优化掉。
代码
#include <bits/stdc++.h>using namespace std;typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];int k;ll fac[N], inv[N];
inline ll qmi(ll a, ll b, ll c) { ll res = 1; while (b) { if (b & 1) res = res * a % c; a = a * a % c; b >>= 1; } return res; }
inline void init() {fac[0] = 1;for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % MOD;inv[N - 1] = qmi(fac[N - 1], MOD - 2, MOD);for (int i = N - 2; i > -1; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}ll C(int a, int b) { if (a < b) return 0; return fac[a] * inv[b] % MOD * inv[a - b] % MOD; }ll f[1 << 20];
bool st[50];
void solve() {if (m == 1) {puts("1");return;}vector<int> f(1 << n);f[0] = 1, f[1] = 2;for (int i = 2; i < n + 1; i++) {vector<int> g(1 << n);for (int j = 0; j < (1 << i); j++) {int t = (i & 1) == (n & 1) ? 1 : 2;for (int k = 0; k < i; k++)if (st[k]) {int p = (j >> (k + 1) << k) | (j & ((1 << k) - 1));if ((i & 1) == (n & 1) && f[p] == 2) t = 2;else if ((i & 1) != (n & 1) && f[p] == 1) t = 1;}g[j] = t;}swap(f, g);}res = 0;for (int i = 0; i < (1 << n); i++) res += f[i];printf("%lld\n", res);
}int main() {init();int T;cin >> T;while (T--) {memset(st, 0, sizeof st);scanf("%d%d%d", &n, &m, &k);for (int i = 1; i < k + 1; i++) scanf("%d", w + i), st[w[i] - 1] = 1;solve();}return 0;
}
E2. Prime Gaming (Hard Version)
这是问题的困难版本。本版本与简单版本的区别在于 \(m \le 10^6\)。
一个有效配置定义为 \(n\) 堆石子的排列，满足：
- 每堆石子的数量是介于 \(1\) 到 \(m\) 之间的整数（包括 \(1\) 和 \(m\)）。
对于一个有效的 \(n\) 堆石子配置，某些从 \(1\) 到 \(n\) 的下标被标记为“好”。Alice 和 Bob 轮流进行游戏，总共 \(n-1\) 回合，Alice 先手。在每一回合中，他们必须执行以下操作：- 选择任意整数 \(i\)，满足 \(1 \le i \le p\)（其中 \(p\) 是剩余的石子堆数）且 \(i\) 是好下标，然后完全移除第 \(i\) 堆石子。
注意，每次操作后，剩余石子堆的数量会减 1，并重新编号。游戏在只剩下一堆石子时结束。保证下标 \(1\) 始终是好下标。
设 \(x\) 为最终剩余石子堆的石子数量。Alice 希望最大化 \(x\)，而 Bob 希望最小化 \(x\)。两人都采取最优策略。
求所有可能的有效配置中 \(x\) 的总和，对 \(10^9+7\) 取模。
先对原问题进行转换，对于 \(t \in \{\,1, 2, \dots, m\,\}\)，我们计算所有配置中，最终结果 \(\ge t\) 的配置的数量，然后再将所有 \(t\) 的配置数量累加起来。对于其中一个配置，如果该配置的最终结果为 \(k\)，在转换后的问题中产生的贡献是 \(\sum_{t=1}^{k} 1 = k\)，因此转换后的问题跟原问题是等价的。
在固定了 \(t\) 后，每堆石子就只有 \(\ge t\) 和 $ < t $ 两种状态，可以用跟上一题完全一样的状态跟转移方程，唯一的区别在于这题 \(0\) 有 \(t - 1\) 种取值方式，\(1\) 有 \(m - t + 1\) 种取值方式。而对于一个配置的合法方案数，只跟配置中 \(\ge t\) 的数的数量有关，因此我们可以对每一个 \(i\) 计算满足 \(popcount = i\) 且最终结果为 \(1\) 的配置的数量为 \(cnt_i\)，答案就是 \(\sum_{i=0}^{n} \sum_{t=1}^{m} cnt_i \, (m - t + 1)^i \, (t - 1)^{n - i}\)。
代码
#include <bits/stdc++.h>using namespace std;typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000086, MOD = 1e9 + 7, INF = 0x3f3f3f3f;
ll res;
int n, m, cnt, w[N];int k;ll fac[N], inv[N];
inline ll qmi(ll a, ll b, ll c) { ll res = 1; while (b) { if (b & 1) res = res * a % c; a = a * a % c; b >>= 1; } return res; }
inline void init() {fac[0] = 1;for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % MOD;inv[N - 1] = qmi(fac[N - 1], MOD - 2, MOD);for (int i = N - 2; i > -1; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}
ll C(int a, int b) { if (a < b) return 0; return fac[a] * inv[b] % MOD * inv[a - b] % MOD; }ll f[1 << 20];
bool st[50];
void solve() {if (m == 1) {puts("1");return;}vector<int> f(1 << n);f[0] = 0, f[1] = 1;for (int i = 2; i < n + 1; i++) {vector<int> g(1 << n);for (int j = 0; j < (1 << i); j++) {int t = (i & 1) == (n & 1) ? 0 : 1;for (int k = 0; k < i; k++)if (st[k]) {int p = (j >> (k + 1) << k) | (j & ((1 << k) - 1));if ((i & 1) == (n & 1) && f[p] == 1) t = 1;else if ((i & 1) != (n & 1) && f[p] == 0) t = 0;}g[j] = t;}swap(f, g);}res = 0;vector<int> g(22);for (int i = 0; i < (1 << n); i++)if (f[i])g[__builtin_popcount(i)]++;for (int i = 0; i <= n; i++) {ll v = 0;for (int j = 1; j <= m; j++) {v = (v + qmi(m - j + 1, i, MOD) * qmi(j - 1, n - i, MOD)) % MOD;}res = (res + v * g[i]) % MOD;}printf("%lld\n", res);
}int main() {init();int T;cin >> T;while (T--) {memset(st, 0, sizeof st);scanf("%d%d%d", &n, &m, &k);for (int i = 1; i < k + 1; i++) scanf("%d", w + i), st[w[i] - 1] = 1;solve();}return 0;
}