nim 游戏

XChara · 2025-02-05 22:24:20 · 个人记录

把我击杀了。日。

考场上前 2.5h 获得了 50pts，又做了 2.5h，没有获得更多的分数。

但是我真的觉得这题好难啊。你们这些人怎么一个个分都比我高。

题意：

给定长为 n 的序列 a_1,a_2,\cdots,a_n，求最小的 \sum x_i 使得 \forall x_i\ge 0 且 \bigoplus (a_i+x_i)=0

并且要求输出 m 组不同的取到最小 \sum x 的 x 的方案

itst：去掉最后一句话就很是题对吧。

对啊。简直太对了。

是题到都已经被人出过了。

这是一道异或题。并且还要最优化一个东西，因此我们可以先按位考虑入手，但是光按位考虑也没有什么入手点，因此我们需要找一些最优解的性质：

每个数都有一个最高改变的位 h_i，这个位一定是 0\rightarrow1，那么可以认为就是我们加了若干次，改变了这一位的值

一个大致的想法就是我们把一个位来回变不是很优，经过一些尝试（如果联系了题目的 B 性质可能可以更容易想到），我们可以得到如下结论：如果此时有一个 a_i=0，那么我们一定不会存在两个其他位置 i,j，满足它们改动的最高位 h_i,h_j 是相同的

证明：设最优解中包含 h_i=h_j，那么我们只考虑所有数的 h_i 及以下的位，设 a_i 由 \overline{0x}\rightarrow\overline{1p}，a_j 为 \overline{0y}\rightarrow\overline{1q}，并且原来 a_i=0 的位置最后变为了 b

那么我们需要付出的代价为 2^{h_i}-x+2^{h_i}-y+p+q+b=\overline{x}+\overline{y}+2+p+q+b

而我们如果直接将 0 变成 b\oplus x\oplus y\oplus p\oplus q，花费的代价一定严格小于上面的方案，也就是说任意最优解一定不存在上述情况

这个有一个推论：任意最优解中不存在三个数 i,j,k 使得 h_i=h_j=h_k，证明就是 i 加到进位之后就相当于一个 0

那么现在我们的方案就比较确定了，如果存在一个 0，我们从高到底考虑到每一位 i，如果当前异或和为 1，我们需要选择恰好一个数加到进位，然后递归到 i-1 位的子问题

容易发现此时我们选择一个最大值一定不劣，因为否则我们可以交换一下选上来的值和最大值的决策，使得这时候换上来的一定是最大值

那么直接模拟即可解决 B 性质的问题。

而对于没有 B 性质的情况，容易发现我们操作完最高的一位之后就出现了一个 0，那么我们直接枚举最高的一位是在哪位，枚举完这一位之后决策也是唯一的，如果当前异或和为 1，那么我们就选择最大值，否则选择最大值和次大值

至此，我们在 O(n\log^2 V) 的复杂度内解决了第一问。

考虑第二问。如何搜方案。

注意到我们第一个分析是严格更优的，所以我们依然只要考虑拎上来一个的方案。

只不过现在拎上来的这一个不一定是最大值（最大值和次大值的第一步同理）

但我们可以再发现一个性质：如果此时我们按照值从大到小排序，那么拎上来可能成为最优解的数一定是一个前缀

这个的证明可以通过类似的调整（交换两个数的决策）得到。

因此我们搜索的时候只需要从大到小枚举，依次进入判断搜出来的是不是最优解即可。

但是此时如果我们单次算答案还是 O(n\log V) 就会出一些问题

注意到我们需要的其实是将最高位为 0 的值从大到小枚举，并且会有 \log V 次置 0 操作，那么我们提前对每个 i，维护出所有数按照最低 i 位排序后的结果，然后维护一个标记表示这个数是否被置 0，那么我们一位上复杂度是 O(\log V) 的，单次算答案是 O(\log^2V) 的

而我们算出来 m 个方案最多会访问到 O(m\log V) 个状态，每个状态我们最多浪费 O(\log^2V) 的时间去计算一个不是最优解的答案，因此总复杂度 O(n\log V+m\log^3V)（如果前面排序预处理使用基数排序的话）

fin.