题解：P11629 [WC2025] Nim 游戏

前言

太诡异了，遂写题解。

提示：我是听了讲，看了题解，搞了好久才搞明白的。我比较笨，描述不清楚，请多多包涵。

Solution

先考虑第一问。

其实已经是困难的。

尝试使用针对位运算类型问题常见 Trick，从高位到低位贪心处理。

异或值为 0 的位不管，异或值为 1 的位需要处理，如何处理呢？

显然需要将某个数的这一位取反，使得异或值为 0。

考虑两种取反的可能：

1. 将某个数的这一位从 1 变为 0，显然需要将该数加上一坨，然后向上一位进位，低位全为 0。

2. 将某个数的这一位从 0 变为 1，显然需要将该数加上一坨，低位全为 0。

低位全为 0 是显然的，因为这是当前花费最小的方式，且给低位提供了最大的操作空间。

现在考虑我们使用哪种方式操作，发现这个向上进位很混乱邪恶，难以考虑，也不符合我们从高到低处理的顺序。

To be continued…