Codeforces Global Round 18 A~F 题解

比赛链接

A

容易发现总和不会变。

那么如果总和是 \(n\) 的倍数就输出 \(0\)，否则输出 \(1\)。

Code：https://paste.ubuntu.com/p/gZZnwtB3VS/。

B

对于二进制每一位都记录一下前缀和，删除最少 \(\Lrarr\) 保留最多，对每一位取 \(\max\) 即可。

Code：https://paste.ubuntu.com/p/44pb5QMm5N/。

C

模拟几次操作后可以看出，连续两次操作其实就相当于交换原序列的两个数。

那么如果操作偶数次，相当于交换一些 \(01\) 对，最小次数就是 \(a\) 和 \(b\) 不同的位数，当然要保证 \((a_i=0,b_i=1)\) 和 \((a_i=1,b_i=0)\) 的数量一样。

如果操作奇数次，最后一次肯定剩下一个位置 \((a_i=1,b_i=1)\)，其他位置全都不同。那么要保证原串中 \((a_i=1,b_i=1)\) 的数量要恰好等于 \((a_i=0,b_i=0)\) 的数量 \(+1\)。

Code：https://paste.ubuntu.com/p/YtnHS9rj2T/。

D

一个小结论：\(\text{popcount}(x\oplus y)\mod 2=(\text{popcount}(x)\mod2)\oplus(\text{popcount}(y)\mod 2)\)。

证明考虑异或的本质是不进位加法，每次只会消掉偶数个 \(1\)。

所以每条边的权值都可以换成 \(0/1\)。

比较显然的结论：\(u_i\) 到 \(v_i\) 路径上的权值异或和 \(=\) 根到 \(u_i\) 路径上的权值异或和 \(\oplus\) 根到 \(v_i\) 路径上的权值异或和。

设 \(a_i\) 表示根到 \(i\) 路径上的权值异或和。显然 \(a_i\in\{0,1\}\)。

那么给出若干个限制其实就是说 \(a_{u_i}\oplus a_{v_i}=0/1\)，每条已给定边权的边同样给出了一个限制。

不难想到 可以用扩展域并查集做。每个点开两个节点 \(b_{i,0/1}\)，如果有一个限制就将对应的节点所在集合合并。无解的情况就是有限制不能满足或者 \(b_{i,0}\) 和 \(b_{i,1}\) 在同一个集合里。

实现的时候可以强制将小的点向大的点合并，这样求出 \(a_i\) 的时候就可以知道 \(i\) 与 \(root\) 是否选的是同一个数。肯定有一堆其他写法，毕竟这是扩展域并查集板子……

Code：https://paste.ubuntu.com/p/D5V2KXCFGC/。

E

发现三个变量不好整，于是把 \(w\) 换成 \(n-r-b\)，原式变为 \((n-r-b)(r-b)=r(n-r)-b(n-b)\)。

那么第二个人肯定会最大化 \(b(n-b)\)，这是一个关于 \(b\) 的二次函数，在 \(b=\frac{n}{2}\) 的时候最大。

不难发现如果第二个人能选 \(x\) 个点，那么肯定能选 \(x-1\) 个点。把选择的子树的根去掉，把它所有儿子的子树都选掉即可。因此第二个人会选的节点一定是 \(\min(\frac{n}{2},y)\)，其中 \(y\) 是第二个人能选择的染蓝的最大节点数。所以第一个人的目的肯定就是最小化第二个人选的染蓝的节点数。如果有所保留，那么第二个人选掉就肯定不优。

考虑第一个人操作的实质，其实就是把一个点到根的路径上的所有点设成第二个人不能选。

不难发现选叶子节点一定比选它的祖先更优。那么问题就变成选一些叶子节点，使它们到根的路径的并的大小最大。这个可以长链剖分后贪心做。

Code：https://paste.ubuntu.com/p/WnnhM2NjZY/。

F

也是一道神仙题。

看到两个相邻的 \(0/1\) 不好处理，于是考虑一个套路：将所有奇数位上的 \(0\to1\)，\(1\to0\)，这样每次操作也就是交换相邻的两个 \(01/10\)。

首先有解的充要条件就是 \(s\) 和 \(t\) 在转化后 \(1\) 的数量相同。

实际上，\(s\) 和 \(t\) 的距离就是 \(\sum\limits_i\) 两个串中第 \(i\) 个 \(1\) 的位置差。这样还是不好计数，考虑转化一下：设 \(x_i=\sum\limits_{j=1}^i[s_j=1]\)，\(y_i=\sum\limits_{j=1}^i[t_j=1]\)，那么 \(s\) 和 \(t\) 的距离就是 \(\sum\limits_{i=1}^n|x_i-y_i|\)。意思就是说每一个 \(s\) 中的第 \(i\) 个 \(1\) 对 \(t\) 中第 \(i\) 个 \(1\) 的贡献是二者的位置差。

这种方法成功将每一位的贡献拆开，那么根据这个就可以 DP 了。设 \(pre_{i,j}\) 表示考虑到前 \(i\) 位，\(x_i-y_i=i\) 的方案数，\(suf_{i,j}\) 表示考虑后 \(i\) 位，后 \(i\) 位中 \(s\) 中 \(1\) 的数量与 \(t\) 中 \(1\) 的数量的差。

转移的时候枚举这一位填 \(1/0\)，最终答案就是 \(\sum\limits_{i=1}^n\sum\limits_{j=-n}^n pre_{i,j}\times suf_{i,-j}\times|j|\)。

Code：https://paste.ubuntu.com/p/WrbFFZyCR2/。