作为 \(2020\) 年的最后一篇博文，在今年 Codeforces 所有对积分 \(\ge 2100\) 以上 Rated 的比赛中，挑选了有代表性的 \(20\) 道思维题在这里分享。
以下列举的题目为后 \(10\) 题（\(7\) 月到 \(12\) 月），顺序为题目编号顺序。
1375F
题意
有三堆石子，数量分别为 \(a,b,c\)。
每次先手可以选择一个正整数 \(x\)，后手选择一堆石子使其数量加 \(x\)，在任意相邻的两轮中，后手不能选择同一堆石子。
如果后手操作之后有两堆石子个数相同，则先手获胜。如果 \(1000\) 轮内没有出现这种情况，则后手胜。
判断先手能否获胜，如果能则给出策略。
\(1\le a,b,c\le10^9\)，\(a,b,c\) 互不相同。
Solution
考虑什么情况下离胜利只有一步：假设 \(a<b<c\)，\(a,b,c\) 成等差数列，且上回操作加在了 \(c\) 上。令 \(x=b-a=c-b\) 就可以胜利。
我们的策略是：找一个合适的 \(x\)，使得 \(x\) 加在其中两堆上都能达到以上的状态。
令 \(x=2c-a-b\)，可以发现只要对面不把 \(x\) 加在 \(c\) 上，就能达到目的。
而如果对面这次把 \(x\) 加在了 \(c\) 上，下一次就无法加在 \(c\) 上了，仍然取 \(x=2c-a-b\) 即可把局面引导到离胜利只有一部的状态。
先手用以上策略就能必胜。
Code
#include <bits/stdc++.h>
typedef long long ll;
ll a[4], b[4];
void orz() {b[1] = a[1]; b[2] = a[2]; b[3] = a[3]; std::sort(b + 1, b + 4);}
int main()
{
int x;
std::cin >> a[1] >> a[2] >> a[3];
puts("First"); fflush(stdout); orz();
do printf("%lld\n", b[3] * 2 - b[1] - b[2]), fflush(stdout),
scanf("%d", &x), a[x] += b[3] * 2 - b[1] - b[2];
while (orz(), b[1] + b[3] != b[2] * 2);
printf("%lld\n", (orz(), b[2] - b[1])); fflush(stdout);
if (scanf("%d", &x), !x) return 0;
return 0;
}
1383E
题意
给定一个 \(01\) 串 \(s\)，每次可以找一个 \(1\le i<|s|\)，把 \(s_i\) 和 \(s_{i+1}\) 合并成一个，合并后的字符为 \(\max(s_i,s_{i+1})\)，合并后新字符和左右两侧的子串会连起来。
求任意次操作（可以是零次）之后，能得到多少种不同的 \(01\) 串，对 \(10^9+7\) 取模。
Solution
这是一道典型的 AtCoder 风格计数题。
最终得到的 \(01\) 串可以视为把原串划分成若干个子串，第 \(i\) 个子串中有 \(1\) 则最终串的第 \(i\) 位为 \(1\)，全 \(0\) 则最终串第 \(i\) 位为 \(0\)。
首先末尾的 \(0\) 会带来一些困扰，先把末尾的 \(0\) 全部去掉，算出来的答案乘上（原末尾 \(0\) 的个数加 \(1\)）即为最终答案。特判全 \(0\) 的情况。
这样对于一个特定的最终 \(01\) 串 \(t\)（最后一个数一定为 \(1\)），我们有一个贪心法则：
维护一个 \(j\) 初始为 \(1\)，让 \(i\) 从小到大：
（1）如果当前 \(t_i=1\) 就在 \(j\) 的后面找到第一个 \(1\) 设其位置为 \(k\)，把 \([j,k]\) 作为第 \(i\) 段，令 \(j\leftarrow k+1\)，\(i\leftarrow i+1\)。
（2）如果当前 \(t_{i\dots x}=0\) 且 \(t_{x+1}=1\)，则在 \(j\) 的后面找到第一个长度为 \(x-i+1\) 的全 \(0\) 段，设其末尾为 \(k\)，则把这 \(x-i+1\) 个 \(0\) 分配给第 \(i\) 段到第 \(x\) 段，令 \(j\leftarrow k+1\)，\(i\leftarrow x+1\)。
这样我们有了一个 DP：\(f_i\) 表示当前到了 \(s_i\) 的方案数。
第一种转移（\(t\) 下一个字符为 \(1\)）：如果 \(i\) 之后第一个 \(1\) 出现在 \(j\) 位置，则 \(f_j+=f_i\)。
第二种转移（\(t\) 后面有一段 \(x\) 个 \(0\)）：如果 \(i\) 之后第一个 \(0^x\) 的末尾出现在 \(j\) 位置，则 \(f_j+=f_i\)。
值得注意的是 \(f_0\) 进行第二种转移的时候 \(x\) 有上限（出现在 \(s\) 最前面的 \(0\) 个数），且只有 \(s_i=1\) 的时候才能用第二种转移。
这样暴力转移是 \(O(n^2)\) 的，考虑第二种转移的合法条件：设 \(c_i\) 表示以 \(i\) 结尾的最后一段 \(0\) 个数，则除了第一段零特殊处理之外，\(f_j+=f_i\) 需要满足的条件是 \(\min_{i<k<j}c_k<c_j\)。
显然对于特定的 \(j\)，能转移的 \(i\) 是一段区间，我们可以得到区间的左端点 \(r\) 是满足 \(r-1<j\) 且 \(c_{r-1}\ge c_j\) 的最大 \(r\)，用单调栈预处理出来之后，前缀和优化即可，\(O(n)\)。
Code
#include <bits/stdc++.h>
const int N = 1e6 + 5, djq = 1e9 + 7;
int n, a[N], f[N], ans, nxt[N], top, stk[N], pre[N], sum[N], endc;
char s[N];
int main()
{
scanf("%s", s + 1); n = strlen(s + 1);
int lst = n + 1;
while (s[n - endc] == '0') endc++;
if (endc == n) return std::cout << n << std::endl, 0;
for (int i = 1; i <= n; i++) a[i] = s[i] == '1' ? 0 : a[i - 1] + 1;
for (int i = n; i >= 0; i--)
if (nxt[i] = lst, s[i] == '1') lst = i;
f[0] = sum[0] = 1; stk[top = 0] = -1;
for (int i = 1; i <= n; i++)
{
while (top && a[stk[top]] < a[i]) top--;
pre[i] = stk[top]; stk[++top] = i;
}
for (int i = 0; i <= n; i++)
{
if (i) sum[i] = sum[i - 1];
if (s[i] == '0')
{
f[i] = sum[i];
if (pre[i] >= 0) f[i] = (f[i] - sum[pre[i]] + djq) % djq;
else if (a[i] < i) f[i] = (f[i] + djq - 1) % djq;
}
else if (i) sum[i] = (sum[i] + f[i]) % djq;
f[nxt[i]] = (f[nxt[i]] + f[i]) % djq;
}
for (int i = 1; i <= n; i++) if (s[i] == '1')
ans = (1ll * (endc + 1) * f[i] + ans) % djq;
return std::cout << ans << std::endl, 0;
}
1404D
题意
给定 \(n\)，求是否存在一种方案把 \(1\) 到 \(2n\) 的所有数划分成 \(n\) 个二元组，满足你无法在每个二元组中选出一个数，使得选出的所有 \(n\) 个数之和是 \(2n\) 的倍数。
如果是，则需要给出一种满足条件的划分方案；
如果否，则需要对于给定的一种划分方案，在每个二元组中选出一个数，使得选出的所有 \(n\) 个数之和是 \(2n\) 的倍数。
\(1\le n\le5\times10^5\)。
Solution
考虑这个构造：\((1,n+1)(2,n+2),\dots,(n,2n)\)。
容易证明选出的所有 \(n\) 个数之和必然在模 \(n\) 意义下与 \(\frac{n\times(n+1)}2\) 同余，当 \(n\) 为偶数时 \(\frac{n\times(n+1)}2\) 不是 \(n\) 的倍数，这样以任意方式选出的 \(n\) 个数之和都不可能是 \(n\) 的倍数。
\(n\) 为奇数时，由于所有数之和模 \(2n\) 等于 \(n\)，故我们只需找一个和是 \(n\) 的倍数的方案（如果这种方案下模 \(2n\) 等于 \(n\) 选补集即可）。
考虑建图：对于一个二元组 \((x,y)\)，连边 \((x\bmod n,y\bmod n)\)。
这样建出来的图每个点度数都为 \(2\)，构成若干个环。将每个环定向之后，选取每条边终点指向的数，这样就对于每个 \(0\le i<n\)，都取走了一个 \(\bmod n=i\) 的数，这 \(n\) 个数之和在模 \(n\) 意义下与 \(\frac{n\times(n+1)}2\) 同余，当 \(n\) 为奇数时 \(\frac{n\times(n+1)}2\) 是 \(n\) 的倍数，这样选出的 \(n\) 个数之和是 \(n\) 的倍数。
复杂度 \(O(n)\)。
Code
#include <bits/stdc++.h>
const int N = 1e6 + 5;
int n, p[N], ecnt = 1, nxt[N], adj[N], go[N], val[N];
bool vis[N], is[N], mark[N];
std::vector<int> a[N];
void add_edge(int u, int v, int w)
{
nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v; val[ecnt] = w;
}
int pos(int x) {return x > n ? x - n : x;}
int main()
{
int x;
std::cin >> n;
if (!(n & 1))
{
puts("First"); fflush(stdout);
for (int i = 1; i <= n; i++) printf("%d ", i);
for (int i = 1; i <= n; i++) printf("%d ", i);
puts(""); fflush(stdout);
scanf("%d", &x); return 0;
}
puts("Second"); fflush(stdout);
for (int i = 1; i <= (n << 1); i++) scanf("%d", &p[i]);
for (int i = 1; i <= (n << 1); i++) a[p[i]].push_back(i);
for (int i = 1; i <= n; i++)
add_edge(pos(a[i][0]), pos(a[i][1]), a[i][1]),
add_edge(pos(a[i][1]), pos(a[i][0]), a[i][0]);
for (int u = 1; u <= n; u++) if (!vis[u])
for (int v = u; !vis[v];)
{
int w;
for (int e = adj[v]; e; e = nxt[e])
if (!mark[e]) {mark[e] = mark[e ^ 1] = 1; w = go[e];
is[val[e]] = 1; break;}
vis[v] = 1; v = w;
}
int sum = 0;
for (int i = 1; i <= (n << 1); i++) if (is[i])
sum = (sum + i) % (n << 1);
for (int i = 1; i <= (n << 1); i++)
if ((sum > 0) ^ is[i]) printf("%d ", i);
return puts(""), fflush(stdout), scanf("%d", &x), 0;
}
1427D
题意
一开始一个数集内只有一个奇数 \(x\)，你需要运用加和异或两种运算（操作数为当前集合内的数，可以重复使用），使得最后集合内出现 \(1\)。
\(3\le x\le 999999\)，操作次数上限为 \(10^5\)，操作数需要在 \([0,5\times10^{18}]\) 内。
Solution
一个基本思路：每次都让 \(x\) 的位数变小。
设 \(x\) 最高位的位权为 \(2^c\)，则考虑 \(2^c\times x+x\) 这个数，可以发现这个数是由 \(x+1\) 和 \(x-2^c\) 拼接成的。
把这个数异或上 \(2^c\times x\) 再异或上 \(x\)，得到的数就是 \(((x\oplus x+1)-1)\times2^c\)。
注意到如果 \(x\) 末尾有 \(k\) 个 \(1\)，则 \(x\oplus x+1=2^{k+1}-1\)，所以上式的值为 \(cur=(2^k-1)\times 2^{c+1}\)。
然后考虑让 \(cur\) 异或上形如 \(2^i\times x\) 的若干个数，使得 \(cur\) 小于 \(2^c\)。
从高到低位处理，如果当前位权为 \(2^i\) 的位为 \(1\) 就异或上 \(2^{i-c}\times x\)，这样到最后就能使得 \(cur<2^c\)。
如果这样得到的 \(cur\) 为奇数则直接 \(x\leftarrow cur\)，否则把 \(cur\) 一直乘 \(2\) 直到和 \(x\) 拥有共同最高位后再让 \(x\) 异或上 \(cur\)，就实现了去掉最高位。
上面忽略了一种特殊情况：如果 \(x=2^{c+1}-1\)，则这时候得出来的 \(cur=0\)，不能用以上方法处理。
这时需要特殊判断：如果这种情况出现，则我们可以得到 \(2x\oplus4x=2^{c+2}+2\)，\((2x\oplus x)+x=2^{c+2}\)，异或一下可以得到 \(2\)，让 \(x\) 异或上 \(2\) 之后就避开了特殊情况，可以继续使用以上方法。
Code
#include <bits/stdc++.h>
typedef long long ll;
const int N = 1e5 + 5;
int a, q;
ll x[N], y[N];
char op[N];
void ADD(ll u, ll v) {x[++q] = u; y[q] = v; op[q] = '+';}
void XOR(ll u, ll v) {x[++q] = u; y[q] = v; op[q] = '^';}
void reduce()
{
int tmp = a, cnt = 0, fin;
while (tmp > 1) tmp >>= 1, cnt++;
if (a == (1 << cnt + 1) - 1)
{
ADD(a, a); XOR(a << 1, a); ADD((a << 1) ^ a, a);
ADD(a << 1, a << 1); XOR(a << 2, a << 1);
XOR(1 << cnt + 2, (1 << cnt + 2) | 2); XOR(a, 2); a ^= 2;
if (a == 1) return;
}
for (int i = 0; i <= cnt; i++) ADD(1ll * a << i, 1ll * a << i);
ADD(1ll * a << cnt, a); XOR((1ll * a << cnt) + a, 1ll * a << cnt);
ll now;
XOR(now = (1ll * a << cnt) + a ^ (1ll * a << cnt), a); now ^= a;
for (int i = cnt + 1; (now >> i) & 1; i++) fin = i;
for (int i = fin; i >= cnt; i--)
if ((now >> i) & 1) XOR(now, 1ll * a << i - cnt),
now ^= 1ll * a << i - cnt;
if (now & 1) return (void) (a = now);
while ((a ^ now) >= (1ll << cnt)) ADD(now, now), now <<= 1;
XOR(now, a); a ^= now;
}
int main()
{
std::cin >> a;
while (a > 1) reduce();
std::cout << q << std::endl;
for (int i = 1; i <= q; i++)
printf("%lld %c %lld\n", x[i], op[i], y[i]);
return 0;
}
1442D
题意
有 \(n\) 堆物品，第 \(i\) 堆物品有 \(t_i\) 个，价值分别为 \(a_{i,1},a_{i,2},\dots,a_{i,t_i}\)，满足 \(0\le a_{i,1}\le a_{i,2}\le\dots\le a_{i,t_i}\)。
对于每堆物品，你可以拿走前面的若干个物品，求拿走 \(k\) 个物品的最大总价值。
\(1\le n,k\le3000\)，\(1\le t_i\le10^6\)，\(k\le\sum_{i=1}^nt_i\le10^6\)，\(0\le a_{i,j}\le10^8\)。
Solution
结论：最多存在一个 \(i\) 满足第 \(i\) 堆取走的物品数不是 \(0\) 也不是 \(t_i\)。
证明：
设有两堆，这两堆拿走的最后一个物品价值分别为 \(x\) 和 \(y\)，第一堆的下一个物品价值为 \(u\)，第二堆的下一个物品价值为 \(v\)。
则第一堆物品多选一个，第二堆物品少选一个的价值增量为 \(u-y\)，第二堆物品多选一个，第一堆物品少选一个的价值增量为 \(v-x\)，这时需要满足 \(u<y,v<x\)。
与 \(x\le u,y\le v\) 合并起来可以得到 \(x\le u<y\le v<x\) 即 \(x<x\)，这是矛盾的。
于是我们有一个暴力：枚举一堆 \(i\)，剩下的 \(n-1\) 堆都是整堆取或者整堆不取，可以直接做一个 \(O(nk)\) 的背包 DP，设 DP 数组为 \(f\)，然后就可以枚举这一堆选的个数 \(x\) 用 \(\sum_{j=1}^xa_{i,j}+f_{k-x}\) 更新答案了。
这样的复杂度是 \(O(n^2k)\)，考虑如何避免每次做一遍背包。
可以分治：\(solve(l,r)\) 表示求出对于所有 \(l\le i\le r\)，去掉第 \(i\) 堆的背包数组。
分治过程即取 \(mid=\lfloor\frac{l+r}2\rfloor\)，递归到 \([l,mid]\) 前把第 \([mid+1,r]\) 堆全部加入，递归到 \([mid+1,r]\) 前把第 \([l,mid]\) 前全部加入。
这样复杂度是 \(O(nk\log n)\)。
Code
#include <bits/stdc++.h>
template <class T>
inline void read(T &res)
{
res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
if (bo) res = ~res + 1;
}
template <class T>
inline T Max(const T &a, const T &b) {return a > b ? a : b;}
typedef long long ll;
const int N = 3005, E = 16;
int n, k, t[N], top;
ll s[N], stk[E][N], f[N][N], ans;
std::vector<ll> a[N];
void xyz32768(int l, int r)
{
if (l == r)
{
for (int i = 0; i <= k; i++) f[l][i] = stk[top][i];
return;
}
int mid = l + r >> 1;
top++;
for (int i = 0; i <= k; i++) stk[top][i] = stk[top - 1][i];
for (int i = mid + 1; i <= r; i++)
for (int j = k; j >= t[i]; j--)
stk[top][j] = Max(stk[top][j], stk[top][j - t[i]] + s[i]);
xyz32768(l, mid); top--;
top++;
for (int i = 0; i <= k; i++) stk[top][i] = stk[top - 1][i];
for (int i = l; i <= mid; i++)
for (int j = k; j >= t[i]; j--)
stk[top][j] = Max(stk[top][j], stk[top][j - t[i]] + s[i]);
xyz32768(mid + 1, r); top--;
}
int main()
{
int x;
read(n); read(k);
for (int i = 1; i <= n; i++)
{
read(t[i]); a[i].push_back(0);
for (int j = 1; j <= t[i]; j++) read(x), a[i].push_back(x);
for (int j = 1; j <= t[i]; j++) a[i][j] += a[i][j - 1];
s[i] = a[i][t[i]];
}
xyz32768(1, n);
for (int i = 1; i <= n; i++)
for (int j = 0; j <= k && j <= t[i]; j++)
ans = Max(ans, f[i][k - j] + a[i][j]);
return std::cout << ans << std::endl, 0;
}
1442E
题意
给定一棵树，点有黑白灰三种，每次操作可以选择一个连通块，在这个连通块内选一个点子集，把这些点和相连的边删掉，这个点子集不能同时包含黑点和白点。
求删完这棵数的最小操作次数。
设树的点数为 \(n\)，\(1\le n\le2\times10^5\)，多测，数据组数不超过 \(10^5\)，所有数据的 \(n\) 之和不超过 \(2\times10^5\)。
Solution
结论：如果只有黑点和白点，且颜色段数最多的一条链段数为 \(l\)，则答案为 \(\lfloor\frac l2\rfloor+1\)。
证明：
当树为链时每次删掉首尾两段（若 \(l\) 为偶数则一开始先删一段）即可达到 \(\lfloor\frac l2\rfloor+1\)。
显然地我们可以得到答案的下界是 \(\lfloor\frac l2\rfloor+1\)。
考虑证明这个下界能取到：把同色点缩成一个，这样得到的树满足每条边连接的两个点异色，在直径上考虑：和之前删掉首尾两段一样，每次删掉所有跟直径有关的叶子，就能让直径长度减 \(2\)。
回到原问题，可以转化成把未染色的点（灰点）染成黑或白，使得颜色段数最多的链段数最少。
先二分段数不超过 \(mid\)，DP \(f_{u,0/1}\) 表示 \(u\) 的颜色为白或黑，\(u\) 的子树最大段数不超过 \(mid\) 的前提下，以 \(u\) 出发的最小段数。
转移直接从每个子树的最小段数合并，根据 \(u\) 和子节点颜色的异同计算贡献即可，算完之后如果某个 DP 值的最长链超过了 \(mid\) 就将其设为无效值。
复杂度 \(O(n\log n)\)。
Code
#include <bits/stdc++.h>
template <class T>
inline void read(T &res)
{
res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
if (bo) res = ~res + 1;
}
template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}
const int N = 2e5 + 5, M = N << 1, INF = 0x3f3f3f3f;
int n, a[N], ecnt, nxt[M], adj[N], go[M], f[N][2];
void add_edge(int u, int v)
{
nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
}
void dfs(int u, int fu, int mid)
{
f[u][0] = f[u][1] = INF;
if (a[u]) f[u][a[u] - 1] = 0; else f[u][0] = f[u][1] = 0;
int c0 = 0, c1 = 0;
for (int e = adj[u], v; e; e = nxt[e])
if ((v = go[e]) != fu)
{
dfs(v, u, mid);
if (a[u] != 2)
{
int t = Min(f[v][0], f[v][1] + 1);
if (t > f[u][0]) c0 = f[u][0], f[u][0] = t;
else if (t > c0) c0 = t;
}
if (a[u] != 1)
{
int t = Min(f[v][0] + 1, f[v][1]);
if (t > f[u][1]) c1 = f[u][1], f[u][1] = t;
else if (t > c1) c1 = t;
}
}
if (a[u] != 2 && f[u][0] + c0 > mid) f[u][0] = INF;
if (a[u] != 1 && f[u][1] + c1 > mid) f[u][1] = INF;
}
void work()
{
int x, y;
read(n); ecnt = 0;
for (int i = 1; i <= n; i++) read(a[i]), adj[i] = 0;
for (int i = 1; i < n; i++) read(x), read(y), add_edge(x, y);
int l = 0, r = n;
while (l <= r)
{
int mid = l + r >> 1;
if (dfs(1, 0, mid), Min(f[1][0], f[1][1]) < INF) r = mid - 1;
else l = mid + 1;
}
std::cout << (l + 3 >> 1) << std::endl;
}
int main()
{
int T; read(T);
while (T--) work();
return 0;
}
1444D
题意
给定 \(h\) 条横线和 \(v\) 条竖线，第 \(i\) 条横线长为 \(l_i\)，第 \(i\) 条竖线长为 \(p_i\)
要用这 \(h+v\) 条线在平面直角坐标系上依次连成一个多边形，需要满足这个多边形横竖边交替，且不能自交（在端点处重合不算自交）。
判断是否存在方案，如果存在则构造一个。
\(1\le h,v,l_i,p_i\le1000\)，多测，数据组数不超过 \(200\)，所有数据的 \(h+v\) 之和不超过 \(1000\)。
Solution
考虑为这个多边形每条边定向，使得所有边以逆时针顺次连接，横线可以分成向右或向左，竖线可以分成向上和向下。
有解的条件比较好猜：有解当且仅当 \(h=v\)，且 \(l\) 数组和 \(p\) 数组都能被分成两个和相等的集合。
可以用 bitset 优化背包 DP 来实现把 \(l\) 数组和 \(p\) 数组分成两个集合的操作。
考虑如何构造，先从一种特殊情况入手：\(l\) 数组和 \(p\) 数组分出的第一个集合大小相同。
设 \(l\) 分成的两个集合分别为 \(L_1,L_2\)，\(p\) 分成的两个集合分别为 \(P_1,P_2\)，\(X=\sum_{i\in L_1}l_i=\sum_{i\in L_2}l_i\)，\(Y=\sum_{i\in P_1}p_i=\sum_{i\in P_2}p_i\)，考虑先从 \((0,0)\) 利用 \(L_1\) 和 \(P_1\) 内的向量到达 \((X,Y)\)，再利用 \(L_2,P_2\) 内的向量回到原点。
重点在于如何做到不自交。先从 \((0,0)\) 到 \((X,Y)\)，考虑这样一个构造：
把 \(L_1\) 从长到短排序，\(P_1\) 从短到长排序，然后依次 \(i\) 从小到大，交替使用 \(L_1\) 排序后的第 \(i\) 个向量（向右）和 \(P_1\) 排序后的第 \(i\) 个向量（向上）。
我们可以证明这么走的范围一定会限制在 \((0,0)(X,Y)\) 连线的右下侧：
考虑归纳，设 \(L_1\) 中最长的线段为 \(a\)，\(P_1\) 中最短的线段为 \(b\)，则不难发现点 \((a,b)\) 必然在连线的右下侧，可以从 \((0,0)\) 走到 \((a,b)\)。而对于 \((a,b)\) 到 \((X,Y)\) 的过程是个规模小 \(1\) 的子问题，可以归纳下去。
\((X,Y)\) 到 \((0,0)\) 同理（只是变成了交替往左和往下走），不难发现两段路径必然第一段在 \((0,0)(X,Y)\) 连线的右下侧，第二段在连线的左上侧，不会发生自交。
如果 \(|L_1|\ne|P_1|\) 怎么办？考虑假设 \(|L_1|<|P_1|\)（如果不满足，交换 \(L_1,L_2\) 和 \(P_1,P_2\) 即可）。
考虑把这些向量分成三组，即路径分成三段：
（1）右向量为 \(L_1\)，上向量为 \(P_1\) 的前 \(|L_1|\) 个元素。
（2）左向量为 \(L_2\) 的前 \(|P_1|-|L_1|\) 个元素，上向量为 \(P_1\) 的后 \(|P_1-L_1|\) 个元素。
（3）左向量为 \(L_2\) 的后 \(|P_2|\) 个元素，下向量为 \(P_2\)。
不难发现第一段路径到达的点 \((x_1,y_1)\) 和第二段路径到达的点 \((x_2,y_2)\) 满足 \(x_2\le x_1\)，\(y_2\ge y_1\)，这时候对于第一段和第三段路径使用前面的构造方法，第二段路径任意（只需满足横竖边交替即可），仍然可以保证不自交。
设 \(h=v=n\)，\(\sum l+\sum p=m\)，则单组数据总复杂度 \(O(\frac{nm}{\omega})\)。
Code
#include <bits/stdc++.h>
template <class T>
inline void read(T &res)
{
res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
if (bo) res = ~res + 1;
}
const int N = 1005, M = N * N / 2;
int n, a[N], b[N], pa[N], pb[N], dx[N], dy[N];
std::bitset<M> f[N];
bool part(int *a, int *res)
{
f[0].reset(); f[0][0] = 1;
int sum = 0;
for (int i = 1; i <= n; i++) sum += a[i];
if (sum & 1) return 0; sum >>= 1;
for (int i = 1; i <= n; i++) f[i] = f[i - 1] | (f[i - 1] << a[i]);
if (!f[n][sum]) return 0;
for (int i = n; i >= 1; i--)
if (f[i - 1][sum]) res[i] = -1;
else res[i] = 1, sum -= a[i];
return 1;
}
inline bool o(int x, int y) {return x > y;}
void work()
{
int tn;
read(tn);
for (int i = 1; i <= tn; i++) read(a[i]);
read(n);
for (int i = 1; i <= n; i++) read(b[i]);
if (tn != n) return (void) puts("No");
if (!part(a, pa)) return (void) puts("No");
if (!part(b, pb)) return (void) puts("No");
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; i++) cnt1 += pa[i] > 0, cnt2 += pb[i] > 0;
if (cnt1 > cnt2)
{
for (int i = 1; i <= n; i++)
pa[i] = -pa[i], pb[i] = -pb[i];
cnt1 = n - cnt1; cnt2 = n - cnt2;
}
std::vector<int> posa, nega, posb, negb;
for (int i = 1; i <= n; i++)
(pa[i] > 0 ? posa : nega).push_back(a[i]),
(pb[i] > 0 ? posb : negb).push_back(b[i]);
std::sort(posa.begin(), posa.end(), o);
std::sort(posb.begin(), posb.end());
std::sort(nega.begin(), nega.end(), o);
std::sort(negb.begin(), negb.end());
for (int i = 1; i <= cnt1; i++) dx[i] = posa[i - 1], dy[i] = posb[i - 1];
for (int i = cnt1 + 1; i <= cnt2; i++)
dx[i] = -nega[i - cnt1 - 1], dy[i] = posb[i - 1];
for (int i = cnt2 + 1; i <= n; i++)
dx[i] = -nega[i - cnt1 - 1], dy[i] = -negb[i - cnt2 - 1];
puts("Yes");
for (int i = 1, x = 0, y = 0; i <= n; i++)
printf("%d %d\n", x, y), x += dx[i],
printf("%d %d\n", x, y), y += dy[i];
}
int main()
{
int T; read(T);
while (T--) work();
return 0;
}
1450G
题意
给定一个长度为 \(n\)，字符集为 \(20\) 的字符串，每次操作可以选择两个个字符 \(x\ne y\)，满足 \(x\) 和 \(y\) 都在现在的串中出现过，且如果字符 \(x\) 出现的位置从小到大依次为 \(i_1,i_2,\dots,i_m\)，则需要满足 \(\frac ab\times (i_m-i_1+1)\le m\)，把所有的字符 \(x\) 改成 \(y\)。
求出所有的字符 \(x\)，满足可以通过若干次操作使得所有的字符都变成 \(c\)。
\(1\le n\le 5000\)，\(1\le a\le b\le 10^5\)。
Solution
把一些字符合并成一个之后，这个字符可以用一个三元组 \((l,r,m)\) 表示，即出现的第一个和最后一个位置分别为 \(l\) 和 \(r\)，出现了 \(m\) 次。
结论：对于两个字符 \((l_1,r_1,m_1)\) 和 \((l_2,r_2,m_2)\)，如果 \([l_1,r_1]\) 和 \([l_2,r_2]\) 有交，且这两个字符都满足 \(\frac ab\times (r-l+1)\le m\)，则这两个字符合并后仍然满足。
证明：在所给的条件下，合并之后 \(m\) 等于 \(m_1\) 和 \(m_2\) 之和，\(r-l+1\) 小于 \(r_1-l_1+1\) 和 \(r_2-l_2+1\) 之和，易证。
回到原问题，设 \(f_S\) 表示字符集合 \(S\) 能否被合并成一个，\(g_S\) 表示字符集合 \(S\) 能否被合并成若干个满足 \(\frac ab\times (r-l+1)\le m\) 的字符。
不难发现把所有的字符都变成 \(c\)，相当于把除 \(c\) 以外的所有字符都合并成若干个满足 \(\frac ab\times (r-l+1)\le m\) 的字符之后再一一合并到 \(c\) 上。
所以 \(f_S=\bigcup_{c\in S}g_{S-c}\)，最终答案所有字符都能变成 \(c\) 当且仅当 \(g_{\Sigma-c}=true\)。
考虑 \(g\) 的转移，由之前的性质得到，\(S\) 合并成的字符区间两两不交。
到这里我们不难发现可以把 \(S\) 中的区间划分成若干个连通块，满足属于不同连通块的区间不交，求出这些连通块内部字符的区间并。
这时候可以注意到，如果把这些连通块从左到右排列，那么 \(S\) 中的字符合并成的每个字符一定对应了连续的几个连通块。
转化成段的划分问题，这时候就可以把原来的子集枚举改成分段 DP，\(O(|\Sigma|^2)\) 解决。
总复杂度 \(O(n+2^{|\Sigma|}|\Sigma|^2)\)。
Code
#include <bits/stdc++.h>
template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}
template <class T>
inline T Max(const T &a, const T &b) {return a > b ? a : b;}
const int N = 5005, E = 22, C = (1 << 20) + 5;
int n, a, b, m, bel[300], l[E], r[E], sze[E], tot, o[E], st[E], cnt, w;
bool is[300], f[C], g[C], h[C], fl[E];
char s[N], ch[E];
int main()
{
std::cin >> n >> a >> b;
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) is[s[i]] = 1;
for (char c = 'a'; c <= 'z'; c++) if (is[c]) ch[bel[c] = ++m] = c;
for (int i = 1; i <= n; i++) r[bel[s[i]]] = i, sze[bel[s[i]]]++;
for (int i = n; i >= 1; i--) l[bel[s[i]]] = i;
f[0] = g[0] = 1;
for (int S = 1; S < (1 << m); S++)
{
tot = w = 0;
for (int i = 1; i <= m; i++)
if ((S >> i - 1) & 1) o[++tot] = i,
f[S] |= g[S ^ (1 << i - 1)];
std::sort(o + 1, o + tot + 1, [&](int x, int y)
{return r[x] < r[y];});
int lt = 9973, rt = -9973, sum = 0;
for (int i = tot, mn = 9973; i >= 1; i--)
{
if (r[o[i]] < mn) st[++w] = 1 << o[i] - 1;
else st[w] |= 1 << o[i] - 1;
mn = Min(mn, l[o[i]]);
lt = Min(lt, l[o[i]]); rt = Max(rt, r[o[i]]);
sum += sze[o[i]];
}
h[S] = a * (rt - lt + 1) <= sum * b; fl[0] = 1;
for (int i = 1; i <= w; i++)
{
fl[i] = 0;
for (int j = i, t = st[i]; j >= 1; j--, t |= st[j])
if (fl[j - 1] && f[t] && h[t])
{fl[i] = 1; break;}
}
g[S] = fl[w];
}
for (int c = 1; c <= m; c++) if (g[(1 << m) - 1 ^ (1 << c - 1)]) cnt++;
std::cout << cnt << " ";
for (int c = 1; c <= m; c++)
if (g[(1 << m) - 1 ^ (1 << c - 1)])
putchar(ch[c]), putchar(' ');
return puts(""), 0;
}
1450H1 1450H2
题意
有一个长度为 \(n\)（偶数）的环，环上每个点可以为黑色或白色，黑色和白色的点个数都是偶数。
同色的点之间可以连边，边的颜色和这两个点的颜色相同。你需要找到一组匹配，使得异色且相交的边的对数尽可能少。
你有一个长度为 \(n\) 的字符串 \(s\)，包含 b（黑色）、w（白色），?（未知）来描述这个环，且至少有一个 ?。你需要求出在 ? 的颜色任意为黑色和白色（需要满足黑色和白色的点数都为偶数）的情况下，异色且相交的边的对数最小值的期望。
除此之外，有 \(m\) 次修改，每次会修改 \(s\) 的一个下标，然后需要再次回答。
\(2\le n\le2\times10^5\)，\(0\le m\le2\times10^5\)，对于简单版 \(m=0\)。
Solution
结论 \(1\)：相邻的两个同色点直接消除掉一定是最优方案。
证明：设 \(i\) 原来连了 \(j\)，\(i+1\) 原来连了 \(k\)，那么 \((i,i+1)\) 和 \(j\) 和 \(k\) 把环上剩下的点划分成了三个部分，画个图讨论一下可以发现无论另一条边的起点和终点分别在哪个部分内，把 \((i,j)(i+1,k)\) 换成 \((i,i+1)(j,k)\) 都不会让那条边与 \(i,i+1,j,k\) 相交的次数变多，得证。
由这个结论可以推出，如果断环为链，维护一个栈，依次把颜色加入栈中，判断如果与栈顶相同就弹栈，否则进栈，最后栈中会剩下 \(k\) 个点，它们的颜色黑白交错排列，不难得出最小相交次数即为 \(\frac k4\)。
结论 \(2\)：设 \(even_b\)、\(even_w\)、\(odd_b\)，\(odd_w\) 分别表示偶位和奇位上黑色和白色点的个数，则最终栈中剩下的点数为 \(|even_b+odd_w-even_w-odd_b|\)。
证明：考虑强行钦定每种颜色是进栈还是出栈，注意到如果 \(even_b+odd_w\ge even_w+odd_b\)，我们可以把偶位上的黑点和奇位上的白点视为进栈（\(1\)），其他视为退栈（\(-1\)），这时候只要满足任何时候栈容量（前缀和）不为负数即可。而一个 \(1\) 不比 \(-1\) 少的数列一定存在一个循环位移满足任意前缀和不为负，所以这时候一定能找到一个合适的位置断环，然后依次对栈进行操作，不难发现栈底的颜色是不变的，并且栈大小一定与当前已操作个数拥有相同的奇偶性，就证明了这么钦定进出栈的正确性，\(even_b+odd_w<even_w+odd_b\) 也一样。
进一步地，\(|even_b+odd_w-even_w-odd_b|\) 可以写成 \(|2odd_w+2even_b-n|\)，枚举 \(i=odd_w+even_b\) 满足 \(2odd_w+2even_b-n\equiv0(\bmod 4)\)，显然满足 \(odd_w+even_b=i\) 的方案数是一个组合数，可以直接计算，这样可过简单版。
对于复杂版，考虑这个组合数和式的通式：
\[\sum_{i=0}^z\binom zi|i-x|[i\bmod 2=y] \]考虑大力分 \(i\le x\) 和 \(i>x\) 把 \(\binom zi\) 和 \(i\binom zi\) 的和分开维护，\([i\bmod 2=y]\) 可用单位根反演等技巧搞掉。
注意到一次修改只会让 \(z\) 和 \(x\) 加 \(1\) 或减 \(1\)，对于 \(z\) 加一之后组合数前缀和的变化，我们根据组合数递推公式有：
\[\sum_{i=0}^x\binom {z+1}i=2\sum_{i=0}^x\binom zi-\binom zx \]这样就实现了组合数前缀和在 \(z\) 加一的过程中的变化，要维护的其他值推导方式类似。
\(O(n+m)\)。
Code
#include <bits/stdc++.h>
template <class T>
inline void read(T &res)
{
res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
res = (res << 3) + (res << 1) + (c - 48);
if (bo) res = ~res + 1;
}
const int N = 2e5 + 5, EI = 998244353, I2 = 499122177;
int n, m, fac[N], inv[N], ans, cnt, cnt0, cnt1, cnt_0, cnt_1, p2[N], i2[N],
posC, posCi, negC, negCi;
char s[N];
int C(int n, int m)
{
if (m < 0 || m > n) return 0;
return 1ll * fac[n] * inv[m] % EI * inv[n - m] % EI;
}
int main()
{
int pos; char c; read(n); read(m);
fac[0] = inv[0] = inv[1] = p2[0] = i2[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % EI,
p2[i] = 2ll * p2[i - 1] % EI, i2[i] = 1ll * I2 * i2[i - 1] % EI;
for (int i = 2; i <= n; i++) inv[i] = 1ll * (EI - EI / i) * inv[EI % i] % EI;
for (int i = 2; i <= n; i++) inv[i] = 1ll * inv[i] * inv[i - 1] % EI;
scanf("%s", s + 1);
for (int i = 1; i <= n; i++)
{
if (s[i] == '?') cnt++;
if ((i & 1) && s[i] == 'w') cnt0++;
if ((i & 1) && s[i] != 'b') cnt_0++;
if (!(i & 1) && s[i] == 'b') cnt1++;
if (!(i & 1) && s[i] != 'w') cnt_1++;
}
for (int i = 0; i <= n; i++) if ((2 * i - n) % 4 == 0)
{
if (cnt0 + cnt1 > i || i > cnt_0 + cnt_1) continue;
ans = (1ll * abs(2 * i - n) / 4 * C(cnt_0 + cnt_1
- cnt0 - cnt1, i - cnt0 - cnt1) + ans) % EI;
}
std::cout << 1ll * ans * i2[cnt - 1] % EI << std::endl;
for (int i = 0; i <= cnt_0 + cnt_1 - cnt0 - cnt1 &&
i <= n / 2 - cnt0 - cnt1; i++)
{
int d = C(cnt_0 + cnt_1 - cnt0 - cnt1, i),
di = 1ll * d * i % EI;
posC = (posC + d) % EI; posCi = (posCi + di) % EI;
if (i & 1) d = EI - d, di = EI - di;
negC = (negC + d) % EI; negCi = (negCi + di) % EI;
}
while (m--)
{
read(pos);
while ((c = getchar()) != 'w' && c != 'b' && c != '?');
int mp = cnt_0 + cnt_1 - cnt0 - cnt1, mq = n / 2 - cnt0 - cnt1;
if (pos & 1) cnt0 -= s[pos] == 'w', cnt0 += c == 'w',
cnt_0 -= s[pos] != 'b', cnt_0 += c != 'b';
else cnt1 -= s[pos] == 'b', cnt1 += c == 'b',
cnt_1 -= s[pos] != 'w', cnt_1 += c != 'w';
cnt -= s[pos] == '?'; cnt += c == '?';
s[pos] = c;
int np = cnt_0 + cnt_1 - cnt0 - cnt1, nq = n / 2 - cnt0 - cnt1;
if (mp < np)
{
int t = C(mp, mq), u = mq & 1 ? EI - t : t;
posCi = (2ll * posCi - 1ll * (mq + 1) * t % EI
+ EI + posC) % EI;
posC = (2ll * posC - t + EI) % EI;
negCi = (1ll * (mq + 1) * u - negC + EI) % EI;
negC = u;
}
else if (mp > np)
{
posC = 1ll * I2 * (C(np, mq) + posC) % EI;
posCi = (1ll * (mq + 1) * C(np, mq) + posCi - posC + EI)
% EI * I2 % EI;
if (np)
{
int u = mq & 1 ? EI - C(np - 1, mq) : C(np - 1, mq);
negC = u;
negCi = (1ll * (mq + 1) * u - (np > 1 ? (mq & 1 ?
EI - C(np - 2, mq) : C(np - 2, mq))
: (mq >= 0)) + EI) % EI;
}
else negC = mq >= 0, negCi = 0;
}
if (mq < nq)
{
int d = C(np, nq), di = 1ll * d * nq % EI;
posC = (posC + d) % EI; posCi = (posCi + di) % EI;
if (nq & 1) d = EI - d, di = EI - di;
negC = (negC + d) % EI; negCi = (negCi + di) % EI;
}
else if (mq > nq)
{
int d = C(np, mq), di = 1ll * d * mq % EI;
posC = (posC - d + EI) % EI; posCi = (posCi - di + EI) % EI;
if (mq & 1) d = EI - d, di = EI - di;
negC = (negC - d + EI) % EI; negCi = (negCi - di + EI) % EI;
}
int resP = (1ll * nq * posC + (np ? 1ll * np * p2[np - 1] : 0)
- posCi + EI) % EI,
resN = (1ll * nq * negC + EI - (np == 1) - negCi + EI) % EI;
resP = (1ll * resP - 1ll * nq * (p2[np] - posC + EI)
% EI - posCi + EI + EI) % EI;
resN = (1ll * resN - 1ll * nq * ((!np) - negC + EI)
% EI - negCi + EI + EI) % EI;
int res = nq & 1 ? 1ll * (resP - resN + EI) * I2 % EI
: 1ll * (resP + resN) * I2 % EI;
printf("%d\n", 1ll * i2[cnt] * res % EI);
}
return 0;
}
1458D
题意
给定一个 \(01\) 串 \(s\)，每次可以选一个 \(0\) 和 \(1\) 个数相等的子串，将这个子串 \(01\) 取反之后再翻转。
求使用这种操作能得到的最小字典序串。
多测，数据组数和每组数据的串长之和都不超过 \(5\times10^5\)。
Solution
下面 \(n\) 为 \(|s|\)。
把 \(0\) 视为 \(-1\)，前缀和为 \(sum_i\)（下标范围 \(0\sim n\)），可以发现这个操作相当于选一个 \(i<j\) 使得 \(sum_i=sum_j\)，对 \(sum\) 数组翻转区间 \([i,j]\)。
考虑一个 \(ans\) 数组合法的条件：
结论：为一个数组 \(a\) 整出一个无序二元组集合 \(\{(a_i,a_{i+1}),0\le i<n\}\)，则 \(ans\) 合法当且仅当 \(ans_0=sum_0\)，\(ans_n=sum_n\)，且 \(ans\) 的二元组集合和 \(sum\) 的二元组集合相等。
证明：
必要性：由于翻转区间的两端点 \(sum\) 相等，所以翻转操作不会改变相邻数对集合。
充分性：假如当前串的前 \(i\) 位已经等于 \(ans\)，要整第 \(i+1\) 位，可以发现只要当前串第 \(i\) 位之后有一个和 \((ans_i,ans_{i+1})\) 相等的相邻数对，我们一定可以把 \(ans_{i+1}\) 搬过来，这样第 \(i+1\) 位就符合 \(ans_{i+1}\) 了。
考虑将 \(sum_i\) 和 \(sum_{i+1}\) 连无向边，要求的就是从 \(0\) 到 \(sum_n\) 的一条字典序最小的欧拉路径。
按字典序从左往右贪心，任何时候保证没走过的边构成的图连通即可。
由于一条边连接的两个点编号差为 \(1\)，可以方便地维护当前图的连通性，总复杂度 \(O(\sum n)\)。
Code
#include <bits/stdc++.h>
template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}
template <class T>
inline T Max(const T &a, const T &b) {return a > b ? a : b;}
const int N = 5e5 + 5, E = 5e5, M = N << 1;
int n, sum[N], cnt[M];
char s[N];
void work()
{
scanf("%s", s + 1); n = strlen(s + 1);
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1]
+ (s[i] == '1' ? 1 : -1);
for (int i = -n; i <= n; i++) cnt[i + E] = 0;
for (int i = 1; i <= n; i++)
cnt[(s[i] == '1' ? sum[i - 1] : sum[i]) + E]++;
int L = 0, R = 0, cur = E;
for (int i = 1; i <= n; i++) L = Min(L, sum[i]),
R = Max(R, sum[i]);
L += E; R += E;
for (int i = 1; i <= n; i++)
if (cur == L) putchar('1'),
cnt[L]--, L += !cnt[L], cur++;
else if (cur == R) putchar('0'),
cnt[R - 1]--, R -= !cnt[R - 1], cur--;
else if (cnt[cur - 1] > 1) cur--, cnt[cur]--, putchar('0');
else cnt[cur]--, cur++, putchar('1');
puts("");
}
int main()
{
int T; std::cin >> T;
while (T--) work();
return 0;
}