AtCoder Grand Contest 045 题解
A - Xor Battle
题意
有 Person 0 和 Person 1 两个人玩游戏，有一个长度为 \(n\) 的 01 字符串 \(S\)、一个长度为 \(n\) 的序列 \(A_1,A_2,\ldots,A_n\) 和一个初始为 \(0\) 的变量 \(x\)。
游戏有 \(n\) 轮。第 \(i\) 轮 Person \(S_i\) 会执行以下两种操作之一：
- \(x\gets x\oplus A_i\)，其中 \(\oplus\) 表示异或运算。
- 不做任何修改。
游戏结束时，若 \(x=0\)，则 Person 0 获胜，否则 Person 1 获胜。
判断两个人都采用最优策略时的胜者。
\(T\) 组数据，\(T\le 200,n\le 200,A_i\le 10^{18}\)。
题解
我们说一个数能被一个集合表示当且仅当这个数可以通过选择这个集合内的若干个数异或得到。
考虑从后往前依次考虑。
若 \(S_i=0\)，则我们将 \(A_i\) 加入到一个初始为空的集合 \(B\) 中。
若 \(S_i=1\)，则又分为两种情况：
- \(A_i\) 能被 \(B\) 表示。此时无论 Person 1 是否选择将 \(x\) 异或上 \(A_i\)，Person 0 都可以通过选择 \(B\) 中的数将这次选择抵消。所以我们直接忽略这一轮即可。
- \(A_i\) 不能被 \(B\) 表示。此时 \(x\) 和 \(x\oplus A_i\) 中一定有一个不能被 \(B\) 表示。那么 Person 1 只要选择那个不能被表示的数，最终 \(x\) 就一定不可能是 \(0\)，所以此时 Person 1 一定获胜。
现在我们只需要能够快速判断一个数能否被一个集合表示即可。使用线性基即可。
时间复杂度 \(O(Tn\log A_i)\)。
B - 01 Unbalanced
题意
给定一个含有 ? 的 01 串 \(S\)。
定义一个 01 串 \(S\) 的不平衡度为所有区间中，0 和 1 数量的差的绝对值的最大值。
求将 \(S\) 中的 ? 替换成 0 或 1（每个 ? 独立选择）的最小不平衡度。
\(|S|\le 10^6\)
题解
对于一个 01 串 \(S\)，如果把 0 看成 \(-1\)，1 看成 \(+1\)，我们可以求出前缀和 \(a_i\)，那么不平衡度即为 \(\max a_i-\min a_i\)。
考虑枚举 \(\min a_i=x\)，那么我们要在满足 \(a_i\ge x\) 的前提下最小化 \(a_i\) 的最大值。
一个做法是，先将所有 ? 替换成 1，这样可以求出 \(\min a_i\) 的最大值 \(M\)。
如果 \(x>M\)，则显然无解。否则我们从前往后依次考虑每一个可以被替换的位置，如果替换 0 后仍然能满足 \(\min a_i\ge x\)，则替换。这样贪心显然是最优的，因为在后面替换一定不如前面替换更优。
根据该贪心算法，可以发现 \(x=k\) 时的答案一定不劣于 \(x=k-2\) 的答案，因为 \(x=k-2\) 时相比于 \(x=k\) 时最多多替换一个 ?，最大值最多减小 \(2\)，所以一定不会更优。
于是只要分别求出 \(x=M\) 和 \(x=M-1\) 时的答案即可。
时间复杂度 \(O(|S|)\)。
C - Range Set
题意
求有多少个不同的 01 串可以通过对长度为 \(N\) 的全 \(0\) 字符串按任意顺序执行任意次以下两种操作得到：
- 选择一个长度为 \(A\) 的子段，将该子段的所有字符替换成 \(0\)。
- 选择一个长度为 \(B\) 的子段，将该子段的所有字符替换成 \(1\)。
答案对 \(10^9+7\) 取模。
\(N\le 5000\)
题解
显然我们交换 \(A,B\) 答案不会变化。所以我们接下来假设有 \(A\le B\)。
一个字符串 \(S\) 可以得到的充要条件是，如果将 \(S\) 中所有长度不小于 \(A\) 的全 \(0\) 极长子段中的所有字符替换为 \(1\)，那么 \(S\) 中需要存在一个长度不小于 \(B\) 的全 \(1\) 子段。
充分性：将所有长度不小于 \(A\) 的全 \(0\) 极长子段中的所有字符替换为 \(1\) 后，把那段长度不小于 \(B\) 的全 \(1\) 子段左右两边的部分全部替换成正确的字符（分别从左往右和从右往左），然后把这个子段替换为 \(1\)，再把开始替换的 \(0\) 重新替换回去。
必要性：考虑倒着还原，把所有长度不小于 \(A\) 的全 \(0\) 极长子段中的所有字符替换为 \(1\) 可以使得 \(1\) 的连续段尽量长。此时如果还是不存在长度不小于 \(B\) 的全 \(1\) 子段，那么我们无论如何都无法将原来的 \(1\) 变成 \(0\)。
接下来我们用总方案数减去不合法的方案数。
下面为了方便，我们将一个只包含长度不小于 \(A\) 的极长全 \(0\) 子段的串称为广义全 \(1\) 串。
首先我们考虑求出 \(f_{i,0/1}\) 表示长度为 \(i\)，以 \(0/1\) 结尾的广义全 \(1\) 串数量。这可以简单地转移。
可以发现不合法的串一定是由长度小于 \(A\) 的全 \(0\) 串和长度小于 \(B\) 且首尾都是 \(1\) 的广义全 \(1\) 串交替拼接而成。但是开头的如果是广义全 \(1\) 串，则开头可以是 \(0\)，结尾同理。
接下来我们考虑求出 \(g_{i,0/1}\) 表示长度为 \(i\)，以长度小于 \(A\) 的全 \(0\) 串结尾或是以长度小于 \(B\) 且首尾都是 \(1\) 的广义全 \(1\) 串结尾的不合法串数量。转移也较为简单，注意开头和结尾需要特殊处理。
时间复杂度 \(O(NB)\)。
D - Lamps and Buttons
题意
A 和 B 玩游戏。有 \(N\) 盏灯，其中 \(1\) 到 \(A\) 是亮的，其他是暗的。灯的状态在游戏过程中对两个人都是公开的。
A 会首先等概率选择一个排列 \(p_1,p_2,\ldots,p_N\)，B 不知道这个排列。这个排列在游戏过程中不会改变。
然后 B 会执行若干次操作，每次操作 B 会选定一盏亮着的灯 \(i\)，如果没有则 A 获胜。接着 A 会把灯 \(p_i\) 的状态改变，注意灯 \(i\) 的状态不会改变。
如果某一时刻灯全部亮着，则 B 获胜。另外，如果过程中某一时刻灯的状态不可能通过有限次操作变成全部亮着，那么 A 获胜。
B 会有一个最优的策略使得自己胜率最大。求在最优策略下可以使 B 获胜的排列数量。
\(N\le 10^7,A\le 5000\)
题解
对于一个大小不小于 \(2\) 的置换环，如果 B 某次选到了该置换环上一个亮着的灯，那么 B 就可以将整个环都点亮。
对于一个大小为 \(1\) 的置换环，如果 B 某次选到了该置换环上的那个点，那么 B 就不可能再点亮该点，就会输掉游戏。
那么 B 的最优策略是每次随机选择一个点，然后将这个点所在的置换环点亮。
令 \(t\) 为满足 \(1\le t\le A\) 且 \(p_t=t\) 的最小值。若不存在则 \(t=A+1\)。我们可以根据上面的分析得到，排列 \(p\) 合法的充要条件为，对于所有 \(A < i\le n\)，\(i\) 所在的置换环存在一个小于 \(t\) 的元素。
考虑枚举 \(t\)，我们需要额外保证对于所有 \(1\le i < t\) 都有 \(p_i\ne i\)，这个条件可以通过容斥解决，即枚举 \(p_i=i\) 位置数量 \(j\)，那么我们现在可以把所有 \(n\) 个点分成若干类点：
- 限制 \(p_i=i\) 的点。这类点可以直接忽略。下面的几类点都默认去掉这类点。
- \(1\le i < t\) 的点。记为 A 类点，假设有 \(a\) 个。
- \(A < i\le n\) 的点。记为 B 类点，假设有 \(b\) 个。这类点有一个额外的限制为，每个点所在的置换环中都要存在一个 \(1\le i < t\) 的点（即 A 类点）。
- \(t < i\le A\) 的点。记为 C 类点，假设有 \(c\) 个。
考虑依次插入 A 类点、B 类点、C 类点。在插入时既可以在之前某个置换环上的两个相邻点之间插入，也可以单独成点（B 类点除外）。所以方案数为 \[ \begin{aligned} 1^{\overline{a}}\times a^{\overline{b}}\times (a+b+1)^{\overline{c}}&=a!\times \frac{(a+b-1)!}{(a-1)!}\times \frac{(a+b+c)!}{(a+b)!}\\ &=\frac{(a+b+c)!\times a}{a+b} \end{aligned} \]
再乘上选出 \(j\) 个数的方案数 \(\begin{pmatrix}t-1\\j\end{pmatrix}\) 和容斥系数 \((-1)^j\) 加入答案即可。
时间复杂度 \(O(A^2+N)\)。
E - Fragile Balls
题意
有 \(N\) 个盒子和 \(M\) 个球，一开始第 \(i\) 个球在第 \(A_i\) 个盒子。
每次操作可以选择一个至少有两个球的盒子，取出其中一个球放入另一个盒子。
第 \(i\) 个球最多只能被操作 \(C_i\) 次，目标是最终到第 \(B_i\) 个盒子。
求最少需要操作多少次，或输出无解。
\(N,M\le 10^5\)，保证对于每个 \(1\le i\le N\)，都存在 \(1\le j\le M\) 满足 \(B_j=i\)。
题解
考虑建立一个 \(N\) 个点的有向图。对于第 \(i\) 个球，我们连一条 \(A_i\) 到 \(B_i\) 的权值为 \(C_i\) 的边。一次操作相当于改变一条边的起点并将这条边的权值减 \(1\)，需要保证操作前起点的出度大于 \(1\) 且边权大于 \(0\)。
首先我们不考虑边权，假设 \(C_i=1\)。对于图中的一个弱连通分量（即把边看成无向边后的一个连通块），如果是一个环，那么一定无解；否则因为每个点入度大于 \(0\)，那么一定存在一个点出度不小于 \(2\)，一定有解。
注意到我们可以操作一个不是环的弱连通分量中的一条权值不小于 \(2\) 的边（若起点出度不满足限制我们可以先操作若干次使得出度满足限制），将一个环与该弱连通分量合并成一个更大的弱连通分量。
这就意味着，我们只需要不断地选择不是环的弱连通分量中的权值不小于 \(2\) 的边减 \(1\)，就可以将环不断地合并进不是环的弱连通分量。
假若我们忽略 \(A_i=B_i\) 的情况，那么我们只需要把每个弱连通分量的 \(C_i-1\) 求和，将环按 \(C_i-1\) 的和从大到小排序后依次合并进不是环的弱连通分量。
如果存在 \(A_i=B_i\)，这样的边原来没有贡献，所以如果用来合并环则会导致贡献相比于其他边有额外的增加。额外的增加分两种情况：
- 这个自环在一个不是环的弱连通分量里。此时额外的贡献是 \(1\)。
- 这个自环单独成为一个弱连通分量。此时额外的贡献是 \(2\)。
这相当于一个背包，我们可以枚举额外贡献是 \(1\) 的自环数量，用双指针维护额外贡献是 \(2\) 的自环数量即可。
一种合并方案合法的条件是：
- 所有可以用来合并的边 \(C_i-1\) 之和不小于需要合并的环数。
- 初始时不是环的弱连通分量中可用来合并的边 \(C_i-1\) 之和大于 \(0\)。
注意细节较多。
时间复杂度瓶颈在于排序，使用桶排可以做到时间复杂度 \(O(N+M)\)。
F - Division into Multiples
题意
你有 \(X+Y\) 个数字，其中 \(X\) 个数字是 \(A\)，\(Y\) 个数字是 \(B\)，\(A\ne B\)。
你需要将这些数字分成若干组，如果一组中数字的和为 \(C\) 的倍数，则这一组是好的组。
求最多有多少好的组。
\(T\) 组数据，\(T\le 20000,A,B,X,Y,C\le 10^9\)。
题解
首先我们可以通过顺序执行以下几个操作使得 \(A,B,C\) 两两互质：
- 若 \(\gcd(A,B)>1\)，则可以将 \(A,B\) 同时除以 \(\gcd(A,B)\)，并且将 \(C\) 除以 \(\gcd(A,B,C)\)。
- 若 \(\gcd(A,C)>1\)，则可以将 \(A,C\) 同时除以 \(\gcd(A,C)\)，并且将 \(Y\) 除以 \(\gcd(A,C)\) 并下取整。
- 若 \(\gcd(B,C)>1\)，则可以将 \(B,C\) 同时除以 \(\gcd(B,C)\)，并且将 \(X\) 除以 \(\gcd(B,C)\) 并下取整。
考虑求出同余方程 \(Ax+By\equiv 0\pmod{C}\) 的所有最小解 \((x_i,y_i)\)，最小指的是不存在 \(i\ne j\) 使得 \(x_i\le x_j,y_i\le y_j\)。注意不能包含 \(x=y=0\) 这组解。
由于 \(\gcd(B,C)=1\)，我们可以令 \(D=\frac{A}{B}\bmod C\)，那么有 \(y\equiv -xD\pmod{C}\)。
于是我们可以从 \(0\) 到 \(C\) 枚举 \(x\)，若求出的 \(y\) 比之前的都要小，那么加入最小解。考虑如何加速。
考虑这么一个过程，假设有一个 \((0,0)\) 到 \((C,D)\) 的矩形，一个点 \((p,q)\) 从原点出发，沿向量 \((1,1)\) 方向前进，若 \(q=D\) 则将 \(q\) 置为 \(0\)，若 \(p=C\) 则将 \(p\) 置为 \(0\)。\(q=0\) 时，若当前的 \(p\) 比之前的都大，则将 \(x\equiv \frac{p}{D},y\equiv -p\) 加入最小解。
于是我们可以递归，假设当前矩形的宽度为 \(W\)，长度为 \(H\)。当 \(W\ge H\) 时，我们可以去掉 \((0,0)\) 到 \((W,W)\) 这个正方形，可以发现对之后的过程不会有太大影响。\(W<H\) 的情况类似，也可以去掉一个正方形。
可以发现这是一个类似于辗转相减的过程，每次最多会加入一个最小解。辗转相减的复杂度会有问题，我们可以变成辗转相除，将一段等差数列（即 \(x\) 等差，\(y\) 等差）加入最小解。
注意到 \(y\) 之差会随着矩形减小不断减小，\(x\) 之差会随着删除的正方形的增多不断增大，所以我们有 \(x_{i+1}-x_i\ge x_i-x_{i-1},y_{i+1}-y_i\ge y_i-y_{i-1}\)。所以最优解的点组成了一个下凸壳。
接下来我们的问题是我们需要选择一个最大的可重集 \(S\) 使得 \(\sum\limits_{i\in S}x_i\le X,\sum\limits_{i\in S}y_i\le Y\)。
我们只要考虑 \(\max S-\min S\le 1\) 的 \(S\) 即可。证明考虑假设存在 \(i,j\in S,j-i\ge 2\)，那么因为有 \(x_{i+1}-x_i\le x_j-x_{j-1}, y_{i+1}-y_i\le y_j-y_{j-1}\)，我们可以将 \(i,j\) 从 \(S\) 中删去，插入 \(i+1,j-1\)，一定仍然满足条件。
假设一个等差数列为 \((x_l,y_l),(x_l+\Delta x,y_l-\Delta y),(x_l+2\Delta x,y_l-2\Delta y),\ldots,(x_r=x_l+n\Delta x,y_r=y_l-n\Delta y)\)。
考虑如何计算这个等差数列的答案。考虑二分答案 \(m\)，由于等差数列上的一个点可以表示成 \((x_l+k\Delta x,y_r+(n-k)\Delta y)\)，于是我们只需要满足 \(\lfloor\frac{X-m\cdot x_l}{\Delta x}\rfloor+\lfloor\frac{Y-m\cdot y_l}{\Delta y}\rfloor\ge m\cdot n\) 就一定可以构造出合法的可重集合 \(S\)。
时间复杂度 \(O(T\log^2 V)\)，其中 \(V\) 是输入中数字的最大值。
