nim游戏 题解

· · 题解

给定一个石子堆序列，你可以向第 i 个石子堆添加 x_i 个石子使得 \oplus_{i=1}^n(a_i+x_i)=0，求出 \sum x 的最小值，并求出至多 m 种好的方案。

第一问的分数占 50\%。

题目保证了总是存在输出量不大的输出方式，这立刻给我们一个提示：许多好的方案中，只有 \mathcal O(\log V) 个位置有值。

先来思考特殊性质 B：a_1=0，这占了 68 分。

我们有两种转述题意的方式：

第一种转述方式看上去十分简洁，但本题的关键性质是 更改量 相比之前不大，所以我们采用第二种理解方式。

有性质：在 a_i=0 时，每位至多选择一个数。

我们来证明这个结论。

假设我们在第 i 位更改了 \ge 2 个数，随便挑选其中的两个数，令它们的低位是 x,y，则代价是 2^i-x+2^i-y，对总异或和的影响是 x\oplus y。

考虑低位的合法方案，我们可以花费至多 x\oplus y 的代价（在 a_1 上）构造一个新的合法方案。

这个方案和原方案的代价差小于 x\oplus y-(2^i-x+2^i-y)，显然 x\oplus y+x+y<2^{i+1}（x,y,x\oplus y 三个数中每位至多两个 1）。

所以我们证明了原方案不优。

并且新方案的低位多了 x,y 可以选择，若选择它们还可以减少代价。

然后我们可以继续猜结论：选择低位更大的数，总是不劣于低位更小的数。

这个好证，假设我们有两个选项其低位是 x,y,x>y，假设我们选了 y，贡献是 2^i-y，若后面 x 都没有被选，则显然换成 x 更优。

若之后 x 又被选了，找出 x 被选的最高位 j，若 j\ge x,y 的 \rm lcp，显然 x,y 选哪个是一样优的，若 j<\text{lcp}，则 y+(x\bmod 2^j)\le x，这意味着我们直接高位选 x，然后在 x 空出来的第 j 位上选一个都不劣。

这样我们就会了第一问，如果要选的话，我们直接选择低位最大的数即可，提前把 \bmod \ 2^x 的结果排好序，直接搜即可，每个被选中的节点至多会被所有低位遍历一次，复杂度 \log^2n。

需要注意的是，我们的爆搜过程只会向一个地方递归，即选 0 个数时直接递归，选 1 个数时枚举最大的可选数递归，没有就递归 0。

如果你把每位按照 \bmod \ 2^x 的结果排好序，复杂度 n\log n\log V+\log^2V，否则暴力实现也可以做到 n\log V。

有了第二个结论，第二问也是简单的，每位从高往低顺着搜，不合法了立刻停止即可，每次不合法最多拉出一条 \log V 的链，所以是 m\log V+\log^2V 的。

在没了特殊性质 B 的情况下，我们发现当我们没 0 可用时，我们有可能执行“选两个数”，这样复杂度就是一条长为 \log V 的链上每个点”分化“出一条选两个数的情况，复杂度比原来多一个 \log V。

需要注意的是，在搜索第二问的过程中，使用不同的 0 视为不同的方案，所以我们把所有 0 记下来一起搜。