Codeforces Global Round 31 (Div. 1 + Div. 2) (#2180) 全解

Codeforces Global Round 31 (Div. 1 + Div. 2) (#2180) 全解

今天早上 VP 这场比赛，过了 ABCE。

A. Carnival Wheel

由于数据范围是 \(5000\)，我们暴力模拟即可。

开一个值域大小的标记数组，如果找到了环就直接退出，记录途中最大值即可。

Submission #356326001 - Codeforces。

B. Ashmal

容易发现如果当前得到了字符串 \(S\)，我们现在要加入字符串 \(A\)，那么无论 \(A\) 接在前面还是后面，都要求 \(S\) 最小即可。

于是我们按顺序插入 \(A\)，在两种方案里选字典序最小的即可。由于数据范围较小，可以用 std::string 快速实现。

Submission #356326086 - Codeforces

C. XOR-factorization

首先 \(K\) 为奇数时，就全部填 \(n\)。

考虑 \(K\) 为偶数时怎么做，一种天真的想法如下：

• 首先填 \(K-2\) 个 \(n\)，接下来只需考虑两个数 \(x,y\)，我们按位考虑。从高位到低位，如果 \(n\) 这一位为 \(1\)，那么可以让 \(x\) 赋 \(1\)，\(y\) 赋 \(0\)。而如果 \(n\) 这一位为 \(0\)，为了使和尽可能大，我们希望 \(x,y\) 都填 \(1\)，但前提是不超过 \(n\)。于是如果先后遇到两个 \(1\)，第一次就让 \(x\) 填 \(1\)，\(y\) 填 \(0\)，而第二次就让 \(x\) 填 \(0\)，\(y\) 填 \(1\)，这样之后 \(x,y\) 都必小于 \(n\) 了。

然而上面的做法会 WA。考虑为什么，因为前面的那 \(K-2\) 个数之中也有可能出现对于 \(n\) 为 \(0\) 的位，两个数填 \(1\)。

考虑扩展上面的做法，维护一个计数器 \(cnt\)，表示当前前 \(cnt\) 个数都必小于 \(n\)。遇到一个 \(1\)，我们就尝试让第 \(cnt+1\) 个数赋为 \(0\)，其他都赋为 \(1\)。而遇到 \(0\) 时，我们就取出前 \(cnt-(cnt\bmod 2)\) 个数填 \(1\)。

这样就通过了。复杂度 \(O(K+\log V)\)。

Submission #356327292 - Codeforces

D. Insolvable Disks

赛时没过，原因是不敢写贪心，以为不对。

考虑每次贪心选择一个尽量长的前缀，设 \(d_i=a_{i+1}-a_i\)，加入 \(r_1=x\)，则有 \(r_2=d_1-x\)，\(r3=d_2-d_1+x\)，\(r_4=d_3-d_2+d_1-x\dots\)。

那么前缀 \(i\) 合法的充要就是 \(\forall 1\le j\le i,0<r_i<d_i\)。

我们把上述每个点的 \(r_i\) 带入到 \(0<r_i<d_i\)，再移项，就可以得到每个点的 \(x\) 的区间限制。每次对区间取交，直到区间为空，此时 \(i-1\) 就是最长前缀。

关于贪心正确性证明：

考虑每个点开始往右最远扩展到的位置 \(f_i\)，由上述区间取交的过程可以知道，\(f_i\) 是单调的，于是我们就相当于选取最少的 \([i,f_i]\) 的区间使得不交，所以贪心是正确的。

复杂度 \(O(n)\)。

Submission #356330957 - Codeforces

E. No Effect XOR

赛时过了这道题。题意就是问有多少个 \(x\) 满足 \([l,r]\oplus x\to [l,r]\)。

考虑找到 \(l,r\) 最高不同的位 \(i\)，分裂成左半边这一位为 \(0\) 的区间 \([l,mid),[mid,r]\)，其中 \(mid=2^i\)。

• 如果这一位填 \(1\)，首先要求 \(0\) 的数量与 \(1\) 的数量相同，然后考虑到此时左半边和右半边分别是值域的后缀和前缀，它们是对称的，因此只要求出 \([mid,r]\to [mid,r]\) 的答案再对 \(2^{i}-1\) 取反即可，于是此时的答案就是 \([mid,r]\) 的答案个数。
• 如果这一位填 \(0\)，那么就是左边的答案与右边的答案取交，右边是值域的前缀，而左边是值域的后缀，它的一个方案也是对应前缀的一个方案，于是转化成了两个前缀的答案取交。
• 问题是求一个前缀的方案，设 \(f(r)\) 表示 \([0,r]\) 的答案，如果 \(r\) 是二的幂，那么答案就是 \(r\)。否则依旧找到 \(r\) 的最高位 \(i\)，最高位只能填 \(0\)，左半边可以随便填，所以递归右半边 \(f(r)\gets f(r-2^i)\)。
• 所以一个前缀的答案是二的幂，于是上述两个前缀的答案取交其实就是取最小值。

那么这个问题就解决了，复杂度 \(O(\log V)\)。

Submission #356328859 - Codeforces

F1 と F2. Control Car

F1：

考虑方案数转概率，这样可以在 DP 时排除无关信息，设 \(f_{i,j}\) 表示初始 \(n=i,m=j\) 最终走到 \((n,m)\) 的方案数。

我们还需要记录从哪个方向走过来，且还要记录一些点的信息。我们如下设状态：

• \(f_{i,j,0,0}\)，从上面走过来，且左上角的点挡住了右边。
• \(f_{i,j,0,1}\)，从上面走过来，且左上角的点没有挡住右边。
• \(f_{i,j,1,0}\)，从左边走过来，且左下角的点挡住了下面。
• \(f_{i,j,1,1}\)，从左边走过来，且左下角的点没有挡住下面。

转移同题解。

边界条件是 \(f_{1,1,0/1,0}=7/16,f_{1,1,0/1,1}={1/16}\)。

我们再对 \(f\) 求前缀和即可得到答案，注意我们指定 \((1,1)\) 是从上面走过来，且 \(f_{1,1,0,0}\) 和 \(f_{1,1,0,1}\) 要乘上对应系数。

复杂度 \(O(nm)\)。

Submission #356333212 - Codeforces

F2：

把每列的转移写成矩阵的形式，矩阵快速幂即可。

复杂度 \(O(n^3\log m)\)。

依旧使用 F1 中的方程求出转移系数，首先把第一列的一个位置赋为 \(1\)，其他赋为 \(0\)，然后转移第二列，即可得到这个位置对下一列每个位置的系数。

注意我们要先求出第一列的所有位置。

矩阵中还有一个位置要记录前缀和。

矩阵乘法时要扔掉为 \(0\) 的位置从而减小常数，具体见代码。

Submission #356343250 - Codeforces

G. Balance

首先研究 Balance 怎么求，肯定要化成简便的形式。转次数，设 \(f_{i,m,k}\) 表示 \(a_i\) 在长为 \(m\) 的子序列中作为第 \(k\) 个出现的子序列个数。Balance 即：

\[\sum _{i,m,k} a_i\times f_{i,m,k}\times \frac km \]

显然 \(a\) 是回文的，则 \(f_{i,m,k}=f_{n-i+1,m,m-k+1},a_i=a_{n-i+1}\)。则

\[2\times Balance=\sum _{i,m,k} a_i\times f_{i,m,k}\times \frac km+\sum _{i,m,k} a_{n-i+1}\times f_{n-i+1,m,m-k+1}\times \frac {m-k+1}m =\sum _{i,m,k} a_i\times (1+\frac 1m) \]

所以求出所有子序列下 \(a\) 的总和以及所有子序列下 \(a\) 的平均值的总和即可。

前者是 \(2^{n-1}\sum a_i\)。

后者即

\[\sum _{i=1}^n\sum _{k=1}^n a_i\times \frac {\binom {n-1}{k-1}} {k} \]

化简后面的式子

\[\sum _{k=1}^{n} \frac {\binom{n-1}{k-1}} k=\sum _{k=1}^n \frac {(n-1)!} {k!(n-k)!}=\frac 1n\sum _{k=1}^n\binom nk=\frac {2^n-1}n \]

所以最终 Balance 为（设 \(S=\sum a_i\)）：

\[2^{n-1}S+\frac {2^{n}-1} n\times S \]

我们只需快速维护 \(S\bmod(10^9+7),n\bmod (10^9+7),n\bmod (10^9+6)\) 即可。

问题在于快速知道删除操作时删掉的数。

考虑加入一个数 \(x\) 后进行的删除操作：

• 若原来 \(len=2n+1\) 为奇数，则序列变成 \([x,a_1,x,...,x,a_{n+1},x,...,x,a_{2n+1},x]\)，发现先删除 \(a\) 的中位数，然后删除两个 \(x\) 与删除两个 \(a\) 的中位数交替进行。
• 若原来 \(len=2n\) 为偶数，则序列变成 \([x,a_1,x,...x,a_n,x,a_{n+1},x,...x,a_{2n},x]\)，发现先删除 \(x\)，然后删除两个 \(a\) 中的中位数与删除两个 \(x\) 交替进行。

有一个神奇的方法。我们可以维护一个包含 \(0,1,2,3\) 的队列。每次加入 \(x\) 时，若长度为偶数，则往队尾加入 \(1\)，否则加入 \(3\)。

我们删除一个数时，从队尾开始遍历，直到遍历到一个 \(0\) 或 \(1\)，它的值就是我们要删的数，同时将遍历过程中所有遇到的数 \(x\gets (x+1)\bmod 4\)。

这个方法复杂度是每次均摊 \(O(1)\)。复杂度 \(O(q\log V)\)，瓶颈在于快速幂。

Submission #356356669 - Codeforces

H1. Bug Is Feature (Unconditional Version)

设 \(f_{i,j}\) 为 \(c-b=i,x-c=j\) 的 SG 值，可以打表发现，每行从下标 \(0\) 开始，第 \(i\) 行每 \(2i\) 个是循环的：

0 1 
1 0 2 2 
0 0 0 1 1 1 
0 1 0 0 2 2 1 1 
0 0 0 0 0 1 1 1 1 1 
1 1 1 0 0 0 2 2 2 2 2 2 
0 0 0 0 0 0 0 1 1 1 1 1 1 1 
1 0 1 1 0 0 0 0 2 2 2 2 1 1 2 2 
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 
0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 
0 0 0 1 1 1 0 0 0 0 0 0 2 2 2 2 2 2 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 2 2 2 2 2 2 2 2 1 1 1 1 2 2 1 1 

发现对于 \(i\) 为奇数，就是 \(01\) 各占一半。

对于 \(i\) 为偶数，前 \(i/2\) 个是第 \(i/2\) 行的前 \(i/2\) 个 \(01\) 取反，然后是 \(i/2\) 个 \(0\) 与 \(i/2\) 个 \(1\)，后 \(i/2\) 个是第 \(i/2\) 行的后 \(i/2\) 个 \(12\) 取反。

直接递归实现即可，注意需要记忆化，而且需要使用哈希表才能通过，使用 map 会 TLE。

复杂度单 $\log $。

Submission #356380285 - Codeforces

H2. Bug Is Feature (Conditional Version)

不妨令 \(c-b\gets 1,x-c\gets\lfloor\frac {x-c}{c-b}\rfloor\)，即转化为公差为 \(1\) 的问题。

设 \(f_i\) 表示公差为 \(1\)，\(x-c=i\) 的答案，有 \(f_0=0,f_i=\text{mex}(f_{i-1},f_{\lfloor\frac i 2\rfloor}-1)\)。

由于后面多带一个减 \(1\)，性质不好，不妨把 \(f_{i+2}\gets f_{i}\)，即右移两个单位。

此时可以打出表，从 \(f_1\) 开始，我们指定 \(f_{1}=f_2=0\)。

0 0 1 2 1 0 2 0 1 0 2 1 2 0 1 2 1 0 2 1 2 0 1 0 2 0 1 2 1 0 2 0 1 0 2 1 2 0 1 0 2 0 1 

发现非 \(0\) 位是 \(12\) 交替的，进一步发现 \(f_i=0\) 当且仅当 \(i\) 的二进制下后缀一的个数为奇数。

我们只需求出一个前缀的 \(f_{i}=0\) 的个数即可求出这个前缀的异或和，复杂度单 $\log $。

Submission #356387263 - Codeforces