题解：P11629 [WC2025] Nim 游戏（暂无数据）

w4p3r · 2025-01-30 21:11:20 · 题解

已经倒闭了，本题出的锅包括但不限于：

第一问是 Topcoder 原题。
chk.cpp 会错误地返回 fail（输出 k =0 ,m' = 0 会让 chk.cpp 错误地认为 std.cpp 错误导致返回 fail）。

幽默的是，CTS 期间没有选手对此提出异议。因为在比赛 OJ fail 的返回也是 WA。

数据水，导致原本应该 TLE/WA 的代码能够通过题目。
赛后被发现出题人的 std.cpp 是错误的！

需要说明的是，只是我唐氏写错了，并不代表题目和赛时数据有任何问题（参见上一条）。验题人的 std.cpp 是至始至终完全正确的。

题解中时间复杂度分析写错了。

本人对以上错误负有 100% 的责任，在这里向所有受到影响的选手致歉。

不过至少题目和赛时数据都是完全正确的。虽然存在原题和数据水的问题，但是考虑到极低的 AC 率（WC 2 人，CTS 0 人），基本上也可以将这两个问题忽略不计。

总体来说题目还是达到了比赛内一个正常题目的最低要求，再次对命题过程中出现的问题向各位致歉，也希望大家可以以此警戒。

本题解主要是对官方题解没有提及的严谨证明作一个补充。

思考思路

从高位到低位考虑。考虑到某位 i 时，选择若干个位置 i_{1}, i_{2}, \ldots,i_{len_i}，满足这些位置的 a_{i_x} 的第 i 位为 0 （(a[i[x]] & (1 << i)) == 0），并将这些位置的 a_{i_x} 加至第 i 位为 1（a[i[x]] += (1 << i) - (a[i[x]] & ((1 << i) - 1))）。

如果第 i 位 1的数量为奇数，则 len_i 应该为奇数，否则 len_i 应该为偶数。如果该位全为 1 且 n 是奇数返回 +\infin。

贪心思路 I

若存在 x 使得 a_x 在 i 及更低位为 0（(a[x] & ((1 << i + 1) - 1)) == 0），则有 len_i \le 1 （取值取决于该位 1 的数量奇偶性）。

证明：

我们证明当前位 1 数量为偶数时一定有 len_i=0，其他情况实际等价。

反证法，不妨假设 len_i=2，我们选择了低位值分别为 p 和 q 将它们第 i 位变成了 1。花费为 2^{i+1}-p-q。

这个操作对于低位的异或和影响至多为 p \oplus q，而由于 a_x = 0 的存在，我们可以花费 p \oplus q 的代价将异或和的影响消除，且存在 x 满足 a_x 在低位全为 0 的条件依旧存在（在对 p,q 执行操作时会将低位清空）。

由于 p + q + (p \oplus q) \le 2 \times (2^i - 1) < 2^{i+1}，所以这个操作一定更劣。对于 len_i 更大的情况可以递归证明，不再赘述。

而如果更高位都满足 $len_i = 0$，则必须选择某一位使其 $len_i=2$。具体哪一位可以暴力枚举选择。 ## 贪心思路 II 对于 $len_i > 1$ 的情况，选择 $a_x$ 在更低位的值 (```(a[x] & ((1 << i) - 1))```) 越大越优。证明：这个很简单，如果我们选择了一个更小的值 $p$ 而没有选择更大的值 $q$ 时得到了一个合法的方案，则可以交换 $p,q$ 在较低 $i$ 位的取值可以得到 $k$ 相同的方案。一个类似的问题：问：给定序列 $a_{1},a_{2},\ldots,a_{n}$ 和序列 $b_{1},b_{2}, \ldots,b_{n}$，是否能够重排 $a,b$ 使得 $\forall 1 \le i \le n, a_i \le b_i$。答：把 $a,b$ 从小到大排序，让小的 $a_i$ 去匹配小的 $b_i$，大的 $a_i$ 去匹配大的 $b_i$ 即可。 --- 具体做法参考 UOJ 群里面的官方题解吧。我懒得写了，本来我也只是来放个证明的。最后正确的总时间复杂度应该为 $O(n\log n \log V + m \log ^3 V)$。