Codeforces Global Round 28 官方题解

· · 题解

A. 凯文和湖景村

当我们将 \overline{x33y} 变成 \overline{xy} 时（x,y 均为十进制数），真实值从 10^{p+2}\cdot x+33\cdot 10^p+y 变成了 10^p\cdot x+y，实际减少了 99\cdot 10^p\cdot x+33\cdot 10^p，容易发现 33\mid 99\cdot 10^p\cdot x+33\cdot 10^p，因此我们可以用若干次 -33 操作来代替删除连续两个 3 这种操作。

所以我们只需要判断 x 能否通过若干次 -33 操作变为 0 即可，即判断 x\bmod 33 是否为零。

B. 凯文和不归林

整个排列中，最多只有 k 个区间能包含 1，同理，最多只有 k 个区间包含 2,3,\dots，我们希望最小值尽可能小的子区间数量尽可能多，因此采用如下构造：

p_k=1,p_{2k}=2,\dots,p_{\lfloor{\frac{n}{k}}\rfloor\cdot k}=\left\lfloor\frac{n}{k}\right\rfloor

对于剩余的位置，可以用 \lfloor\frac{n}{k}\rfloor+1\sim n 的所有值任意填写。容易证明这种构造的答案最小。

C. 凯文和月亮河公园

为了最大化两个串的异或和，肯定想要最大化异或和的二进制位数，为了最大化这个位数，[1,n] 必然被选择。假设我们选择的另一个串的首位为 1，若不为 1 可以把前导零全部删去。

找到整个串从前往后的第一个 0 的位置，我们必然想让这个位置变为 1，而且不让更前面的 1 改变为 0。因此，设第一个 0 的位置为 p，则另一个串长度为 n-p+1，枚举另一个串的开始位置，线性计算两个串的异或和，取最大值即可。复杂度 O(n^2)。

若整个串全部是 1，则选择一个 [1,n]，一个 [1,1] 可以被证明是所有选择中最大的。

有趣的事实：这个题可以做到 O(n) 复杂度。具体来说，观察到另一个串需要满足：长度为 n-p+1，第一个字符为 1，所以左端点必须 <p，也就是说，另一个串的前缀 1 长度可以在 [1,p-1] 之间任意选择。我们希望原串的第一段 0 尽可能被赋值为 1，且第一段 0 后面的那个 1 不会被修改成 0，假设原串第一段 0 的长度是 q，则选择的另一个串的前缀 1 的长度必然为 \min(p-1,q)，容易快速定位到起始位置。

在筹备比赛确定题目过程中，我们认为 O(n) 做法对于 C 题难度来说过高，因此使用了 O(n^2) 的数据范围作为使用的题目。

D. 凯文和里奥的回忆

阅读所有提示。先删除所有 rating 低于你的参赛者，这样你就成了 rating 最低的参赛者。此时你能解决的问题所有人都能解决，不影响你的排名，可以将这些问题的难度看作 +\infty。

此时，你不能解决任何问题，因此你在一场比赛中的排名是 (1+ 在这张比赛中解决至少一个问题的参赛者数量 )，即我们只需要关注每场比赛中的最简单的问题。

预处理出对于每个问题，有多少参赛者能够解决，设为 c_i。可以通过将参赛者 rating 和题目难度排序后使用双指针或二分算法求出 c_i。

接下来的问题是，给定 c_i，你需要将所有 c_i 分为 \lfloor\frac{n}{k}\rfloor 组，每组 k 个，最小化每组 c_i 最大值之和。可以使用贪心算法解决，将 c_i 从小到大排序，对于一个 k，答案就是 (c_k+1)+(c_{2k}+1)+\dots，暴力计算复杂度是调和级数，算上排序后即为 O(n\log n+m\log m)。

E. 凯文和军工厂

图总共有 2nm 条边，而每种颜色构成一个森林，因此对于一种颜色最多存在 2n+m-1 条边，那么总边数一定不超过 (2n+m-1)n。于是得到条件：(2n+m-1)n\ge 2nm，化简得 m\le 2n-1。

接下来我们只需构造出 m=2n-1 的情况即可解决本题。

事实上容易构造，由于每个右部点的度数为 2n，且颜色总数为 n，令每种颜色的边恰好 2 条。则对于每个颜色而言，相当于选择两个左部点使其联通（我们忽略右部点的存在），最后经过 2n-1 次连接，左部点需要形成树。可以发现只需要将左部点连成链即可，构造时只需要循环移动第一个右部点的颜色。例如对 n=4,m=7 的情况，形如：

1 4 4 3 3 2 2
1 1 4 4 3 3 2
2 1 1 4 4 3 3
2 2 1 1 4 4 3
3 2 2 1 1 4 4
3 3 2 2 1 1 4
4 3 3 2 2 1 1
4 4 3 3 2 2 1

因此一种简单的构造方法是对于左部点 i 和右部点 j，其连边的颜色为：

\left\lfloor\dfrac{(i+j)\bmod 2n}2\right\rfloor+1

F. 凯文和永眠镇

对于 b 序列建出小根笛卡尔树，容易发现，我们只会操作这棵笛卡尔树上的区间。

考虑在笛卡尔树上进行 dp，令 f_{u,i} 表示只考虑 u 子树内的所有位置，进行 i 次操作之后，区间内 a_x 的最大值最小是多少。合并时，首先需要对他的两棵子树进行合并，设为 ls,rs，则有转移：

f_{u,k}=\min_{i+j=k}\left(\max(f_{ls,i},f_{rs,j},a_u)\right)

然后再考虑在 b_u 这个位置的除法操作，即：

f_{u,k+1}\leftarrow\left\lceil\frac{f_{u,k}}{b_u}\right\rceil

由于一直操作整个序列可以做到 \log_2\max(a_i)\le 63 次操作，因此 dp 状态的第二维只需要定义 0\sim 63，这样做的复杂度是 O(n\log^2 a)。

这种做法的瓶颈在于对于两棵子树 dp 状态的合并。观察发现 f_{u,i} 是单调不增的，因此对于 f_{ls,i} 和 f_{rs,i} 做 \min-\max 卷积等价于对于两个序列做归并排序，可以将合并做到 O(\log a) 的复杂度，最终得到一个 O(n\log a) 的解法。

G. 凯文和圣心医院

我们假设左式中取到最值的位置为 L，右式中为 R。

任意找出一个 L,R，记和 L 同行和 R 同列的位置为 P，则有 a_L\ge a_P\ge a_R 即 a_L\ge a_R。于是只要考虑 a_L=a_R 的情况。

考虑两边同时取到最值的位置，记作 S，那么 S 中的位置既是这一列的 \max，也是这一行的 \min。于是对于两个 S 中非同行同列的位置 P,Q，容易得出和 P 同行和 Q 同列，与和 P 同列和 Q 同行的两个点也都能取到最值。归纳可以得到 S 构成了一个子矩形。

不妨枚举最值 k 和 S 的大小 i\times j，限制是 S 的所有行剩下的元素 \le k，所有列剩下的元素 \ge k。使用容斥原理，不难得到：

ans=\sum_{k=1}^v\sum_{i=1}^n\sum_{j=1}^m(-1)^{i+j}\binom ni\binom mjk^{i(m-j)}(v-k+1)^{(n-i)j}v^{(n-i)(m-j)}

朴素计算是 O(nmv) 的，无法通过。考虑化简：

=\sum_{k=1}^v\sum_{i=1}^n(-1)^i\binom ni\sum_{j=1}^m(-1)^{j}\binom mj\left(k^i\right)^{m-j}\left((v-k+1)^{n-i}\right)^j\left(v^{n-i}\right)^{m-j}\\ =\sum_{k=1}^v\sum_{i=1}^n(-1)^i\binom ni\sum_{j=1}^m\binom mj\left(-(v-k+1)^{n-i}\right)^j\left(k^iv^{n-i}\right)^{m-j}

求和符号中很像二项式定理，考虑加上 j=0 的项再减掉：

=\sum_{k=1}^v\sum_{i=1}^n(-1)^i\binom ni\left(\sum_{j=0}^m\binom mj\left(-(v-k+1)^{n-i}\right)^j\left(k^iv^{n-i}\right)^{m-j}-\left(k^iv^{n-i}\right)^m\right)\\ =\sum_{k=1}^v\sum_{i=1}^n(-1)^i\binom ni\left(\left(-(v-k+1)^{n-i}+k^iv^{n-i}\right)^m-\left(k^iv^{n-i}\right)^m\right)

于是我们在 O(nv\log m) 的时间内解决了该题。

H. 凯文和唐人街

假设对 01 串 s 执行若干次操作后得到 01 串 t，不难发现 t 中每个元素一定对应 s 中一个子集的元素的 \max。进一步观察可以发现这个子集一定构成一段区间，不妨写下 t_i 对应 \max\limits_{k=l_i}^{r_i} s_k。

初始的串 t=s，因而所有 l_i=r_i=i。假设当前的串 t 长度为 m，对应 l,r 两个序列，考虑如果在 1 \le p \le m 的位置 p 执行了一次操作，得到的新序列 t' 对应的 l',r' 两个序列。那么由于 \forall 1 \le i < p,t'_i=\max(t_i,t_{i+1})，\forall p \le i < m,t'_i=t_{i+1}，可以发现 \forall 1 \le i < p,l'_i=l_i,r'_i=r_{i+1}，\forall p \le i < m,l'_i=l_{i+1},r'_i=r_{i+1}。如果只关注 l,r 两个序列到 l',r' 两个序列的变化，相当于删去了 l_p 和 r_1 两个值。

因此从 s 序列出发做 k 次操作，能生成的序列 t 对应的 l,r 序列，一定 l 序列是从 1 \sim n 任意删去 k 个值，r 序列是 k+1 \sim n。

现在，不妨考虑如何判定 01 串 t 能否被生成，将 t 反转得到 t' 后，相当于目标是寻找 n \ge p_1 > p_2 > ... > p_k \ge 1 使得 \forall 1 \le i \le k,t'_i=\max\limits_{k=p_i}^{n-i+1}s_k。一个显然正确的贪心策略是按照 i=1 \sim k 的顺序选择 p_i，每次都选择最大的可行值。

现在考虑进行 DP，设 dp_{i,j} 为有多少长度为 i 的 01 串 t，使得运行上述贪心算法后 p_i 恰好取到 j。可以认为必定 p_0=n+1，边界情况是 dp_{0,n+1}=1。考虑从 dp_{i-1,j} \to dp_{i,*} 的转移：

两类转移可以看作是无论如何将 dp_{i,j-1} 加上 dp_{i-1,j}。然后找到最大的 pos \le n-i+1 使得 s_{pos} 为 1，对所有 j-1>pos 即 j \ge pos+2 的 dp_{i,pos} 加上 dp_{i,j}。

可以将第一种转移视作对 DP 数组进行了整体平移，然后第二种转移是求 DP 数组一段后缀和再执行一次单点加，记录偏移量后容易使用线段树在 O(n \log n) 执行所有转移。

答案即是所有 1 \le i \le n,1 \le j \le n 的 dp_{i,j} 之和，使用线段树维护时当然也可以 O(1) 求出当前的 dp_i 的每一项之和（需要将 dp_{i-1,1} 这一项平移后下标不在范围内的置零）。

由于转移有着更好的性质，实际上可以不用数据结构仅仅更巧妙地使用前缀和 O(n) 解决该问题，但这不是必要的。

I1. 凯文和红教堂（简单版本）

引理：假设最后填出来最大值是 mx，不同的数的个数是 c，记 d=c-mx。那么 d=0 或 d=1。

证明：首先显然有 c\le mx+1。假设 c<mx，观察填 mx 的位置则容易发现矛盾。

考虑序列 s 中最左边和最右边的字符是什么：

我们把原字符串每次取出首尾字符后递归构造。

分析 d 的变化，对于 LR 情况 d 不变，对于 LL 或 RR 要求内部 d=1，对于 RL 会使整个区间 d 变为 0。

因此，考虑最外层的 RL，其外层若包含 LL 或 RR，则无解。

否则一定有解，且容易根据上述过程构造。

复杂度 O(n)。

I2. 凯文和红教堂（困难版本）

根据简单版本，可以发现大部分情况解的个数并不多，因为对于 LR，LL 和 RR，对于里面的部分填完后，外层只有唯一的填法。因此如果没有一层是 RL，那么答案必然是 1。

接下来考虑有 RL 的情况，不妨假设 RL 是最外部的两个字符。

可以证明的是：这个 RL 中 R 位置和 L 位置填的数是相同的。具体证明在此省略，读者自证不难。

不妨设这个相同的值为 m。接下来，枚举最右侧填 m 的 R 位置 x，和最左侧填 m 的 L 位置 y。讨论一下 x,y 的关系：

最后仅需要对上述情况分别计数即可。x>y 的情况容易 O(n) 统计，对于 x<y 的情况，不妨 a\ge b，可以枚举 y，计算出 y 前面连续的极长 R 的个数 cnt，那么对 a 的限制变成了 b\le a\le b+cnt。

通过上述观察，我们总共只需要枚举 O(n) 组 x,y 并判断其是否会对答案增加 1。也就是说，答案是 O(n) 级别的。

最后的问题是：每次给定一组区间 [l,r]，问这个字符串每次取出首尾字符时，是否存在 RL 的情况。

一种简单的解决方法是，使用 bitset 维护，例如从小到大扫描 r，以 bitset 维护对于每个 l+r，是否存在 RL 的情况。该做法的时间复杂度为 O(\dfrac {n^2}{\omega})，可以通过本题。

如果使用分块卷积，可以做到更优的复杂度。事实上，如果继续深挖性质，可以做到 O(n\log ^2n) 的时间复杂度（需要使用卷积），如果你对此感兴趣可以自行研究。