WC2025 Nim 游戏 题解

· · 题解

题意

给非负整数序列的每一项都加上一个非负数使得所有数的异或和为 0，最小化加上的数的总和。构造最多 m 组方案。

算法 0

我会猜猜猜！第一问直接输出全局异或和，看看能不能通过特殊性质 B！

其实这是场上第一想法。

期望得分 0。

算法 1

我会 n=2！

显然要求两个数相等。如果两个数本来就相等就结束了，否则只能给较小数加一点。方案数都是 1。

期望得分 4。

算法 2

我会爆搜！

你可以直接爆搜 a 的取值求最小值，然后接着爆搜构造方案。但是显然这么搜得到的重复状态有点太多了，只能通过 n\le 5,V=2^4。时间复杂度是 O(V^n\rm{poly}(n))。结合算法 1 期望得分 16。

实际上我们可以基于改变后的 a 不会超过 2V 的性质设计一个 dp：f_{i,j} 表示前 i 个数加完之后异或和为 j 的最小加的数的和，然后仍然搜索出方案。这里倒着搜即可确保每个决策都会得出一个方案，于是时间复杂度是正确的。暴力实现 dp 时间复杂度 O(nV^2+m\log V)。结合算法一期望得分 28。

实际上我场上特判这个点的时候没有发现改变后的 a 可以超过 V 但是也通过了，怎么回事呢？哦原来是有 B 性质啊那我不会卡了。实际上根据后面的分析，有 B 性质的情况下值域就是 V。

算法 3

我会 A 性质！

首先我们把出现 2 次以上的数的出现次数都削成 <2，即出现或不出现。特判一下已经结束了的情况。可以发现此时除非只剩下一种数的情况，和原来的时候的第一问答案是一样的。我们特判原来就所有数都相等的情况即可。手玩发现此时需要把两个 x 分别变成 2x 和 3x，且没别的等价的方案了，方案数 n(n-1)。

考虑剩下的东西，排序后得到序列 b_{1\dots l} 满足 b_i=2^k，且 b_i>b_{i-1}。我们需要最小化修改后的 \sum b。此时最优方案之一大概就是把所有东西两两匹配，把小的变成大的，所以此时贪心地把 b_2 变成 b_1，b_4 变成 b_3……即把 b_{2x} 变成 b_{2x-1} 即可。有一个问题是如果 b 的长度是奇数该怎么办，即最后剩了一项消不掉，记为 t。此时我们可以借助其它的不与 t 相同的数，直接给它加上 t 即可，相当于给它二进制上的这一位赋值成 1，所以不会有问题。最小代价即为 \sum^l_{i=1}(-1)^{i+1}b_i。

至于构造方案，我似乎没有一个特殊的好写的做法专门做这一档。场上写这一档写了一个小时破防了，后来发现直接按上面的匹配写搜索会漏很多东西，所以我改进后的做法的这个搜子不太像人写的。所以结合前面的算法期望得分只有 34。

所以开头应当改成我不会 A 性质。

算法 4

我会按位贪心！

场上我根据手玩 A 性质的构造方案得出了一个有意思的结论：对于排序后的序列 a 上的一个修改操作，如果有一种方案是把 a_i 改成一个 (a_x,a_{x+1}] 之间的数，这相当于一次对于每个 i\le j<x，都先把一个值等于 a_j 的数改成 a_{j+1}，然后再做后面的操作。这会产生大量的方案。这也告诉我们，我们可以倒着做这些操作。如果需要一个 (a_x,a_{x+1}] 的数，而需要把一个 a_{i<x} 变成这个，则我们先把 a_x 变过来也是等价的。

这就引出一个贪心。我们按位决策，如果某一位上的异或和是 1，我们把一个 0 变成 1。变哪个好呢？由上述思考，如果抛弃了更高的所有位（可以发现确实可以这样做），我们取这一位是 0 的所有数里最大的一个来改。因为如果要改能小的，其实也可以用改最大的这一步来替代。

只需要注意我们要求存在一个这一位是 0 的。如果这一位全是 1 就不对了。这正好符合我们的 B 性质！如下参考代码可以通过 B 性质的第一问，时间复杂度 O(n\log V)，随手实现排序可以多一个 \log n。结合前面的算法可以获得 56 分。

void Main() {
    cin>>n>>m;
    REP(i,0,n)cin>>a[i];
    vector<int>b;
    REP(i,0,n)b.pb(a[i]);
    c=0;
    for(int i=59;i>=0;--i){
        int f=0;
        for(auto &j:b)if((j>>i)&1)f^=1;
        if(f){
            sort(all(b));
            int x=lbound(b,1ll<<i)-1;
            c+=(1ll<<i)-b[x];b[x]=0;
        }
        for(auto &j:b)if((j>>i)&1)j^=1ll<<i;
    }
    cout<<c<<endl<<0<<endl;
}

这玩意同时直接得到了一组方案，可以通过 m=1 的构造方案。结合前面的算法可以获得 62 分。这大概也就是包含笔者的 \sout{31} 个 \sout{262} 的由来。

算法 5

我会爆搜性质 B！

我们需要技巧性的快速爆搜。注意到上面用过的一个性质：我们处理完每一位之后可以直接扔掉这一位！这也就是说一个合理的方案最多只会用到 \log V 个操作。

考虑刚才分析“只操作最大的那个数”的结论，如果我们操作了一个更小的数，然后把它拆成了若干个步骤：a_i\rightarrow a_{x_1},a_{x_1}\rightarrow a_{x_2},\dots,a_{x_p}\rightarrow \rm{target}(a_i)。此时对当前这一位有影响的实际上只有最后一个改变 a_{x_p} 的操作是把这一位的 0 变成 1 的。于是确实可以看成，每一位只做一个操作，而且是把后 i-1 位清空，把第 i 位置成 1。

我们基于这个结论搜索，并基本确保当前搜索到的序列 a 是有最小代价解的。注意到如果某一位选择的是操作后 i 位是 x 的，有解，则选择操作后 i 位比 x 更大的一定也有解。于是可以得到如果 x 无解，则比 x 小的也无解。我们按所有数的后 i 位排序，然后依次尝试修改这一位，然后搜索函数反悔“当前状态搜下去是否有解”，如果遇到无解了就直接退出即可。

考虑排序的次数，我不太会证明，也不太会感性理解根据题解时间复杂度也许是 O(n\log n\log V+m\log V)？这个太神秘了，但是确实跑得很快。结合前面的算法期望得分 84。

注意如果某一位是不需要操作的我们就不能去遍历每一位了，否则会在 #18 获得 TLE 的好成绩。所以尽量实时维护异或和。

这个问题是我写完无特殊性质之后才发现的，所以只能提供一个 TLE on #18 的代码。

注意你需要提前把最小代价求出来。然后其实特殊性质 A 大部分时候是被 B 包含的，这个代码理应也可以通过，但是仍然要特判 n 是奇数且所有数相等，具体见算法 3 的第一部分。但是我很懒没写这个部分。

算法 6

我会正解！

考虑没有特殊性质 B 的情况。根据上面的分析，这个做法只会在 n 为奇数且某一位全都是 1 的时候会寄。

这个东西还有一个特性：之前的每一位异或和都是 0。否则一次操作一定会清空某个数的后 i-1 位，然后这种情况就不存在了。

这个时候我们显然至少要把一个 1 改成 0，而我们只能用加法，所以麻烦的是这会影响更高位（而把 0 变成 1 不会这么麻烦，感性理解这当然是严格更优的，所以我们非必须不把 1 改成 0）。

我们声称在最终方案中，第一个有过修改的位一定是有两个 0 变成了 1。首先必须得有修改的，其次不能影响个数的奇偶性。所以只需要考虑是为什么不是把 1 变成 0。其实很好理解，如果这样了就一定有了进位，那后面总有位变大了。即使上面每一位都只有 1 个 0，我们也可以取值域外的 2^{60} 这一位，所以肯定是有 2V 内的解的。

然后做法就很直接了，直接枚举是哪一位操作了两次，然后由于这里直接会有一步清空，下面就不会再出现这种情况了。在求最优解的时候，直接取后 i 位最大的两个数操作，原理是同理的。在爆搜方案的时候，我们先从大到小枚举第一个操作的数。对于第一个数确定的情况，我们按上面的策略，第二个数从大到小，到无解为止。到第一个数对应的所有第二个数都无解的时候就退出。

时间复杂度也很神秘，据说是只需要多乘一个 \log V，也就是 O(n\log n\log V+m\log^2V)。官方题解是这么写的，但是我也不知道为什么 n 那项没多乘一个 \log V，反正它还是跑得很快。期望得分 100 分。

参考代码。一个调了很久的锅是 \inf 开小了，只开了 10^{18}，警钟长鸣。