专栏文章

WC2025 Nim 游戏 题解

IIvanZhang2009
P11629题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqe9idm
此快照首次捕获于
2025/12/04 03:22
3 个月前
此快照最后确认于
2025/12/04 03:22
3 个月前
查看原文

题意

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

算法 0

我会猜猜猜！第一问直接输出全局异或和，看看能不能通过特殊性质 B！
其实这是场上第一想法。
期望得分 00。

算法 1

我会 n=2n=2！
显然要求两个数相等。如果两个数本来就相等就结束了，否则只能给较小数加一点。方案数都是 11。
期望得分 44。

算法 2

我会爆搜！
你可以直接爆搜 aa 的取值求最小值，然后接着爆搜构造方案。但是显然这么搜得到的重复状态有点太多了，只能通过 n≤5,V=24n\le 5,V=2^4。时间复杂度是 O(Vnpoly(n))O(V^n\rm{poly}(n))。结合算法 11 期望得分 1616。
实际上我们可以基于改变后的 aa 不会超过 2V2V 的性质设计一个 dp：fi,jf_{i,j} 表示前 ii 个数加完之后异或和为 jj 的最小加的数的和，然后仍然搜索出方案。这里倒着搜即可确保每个决策都会得出一个方案，于是时间复杂度是正确的。暴力实现 dp 时间复杂度 O(nV2+mlog⁡V)O(nV^2+m\log V)。结合算法一期望得分 2828。
实际上我场上特判这个点的时候没有发现改变后的 aa 可以超过 VV 但是也通过了，怎么回事呢？哦原来是有 B 性质啊那我不会卡了。实际上根据后面的分析，有 B 性质的情况下值域就是 VV。

算法 3

我会 A 性质！
首先我们把出现 22 次以上的数的出现次数都削成 <2<2，即出现或不出现。特判一下已经结束了的情况。可以发现此时除非只剩下一种数的情况，和原来的时候的第一问答案是一样的。我们特判原来就所有数都相等的情况即可。手玩发现此时需要把两个 xx 分别变成 2x2x 和 3x3x，且没别的等价的方案了，方案数 n(n−1)n(n-1)。
考虑剩下的东西，排序后得到序列 b1…lb_{1\dots l} 满足 bi=2kb_i=2^k，且 bi>bi−1b_i>b_{i-1}。我们需要最小化修改后的 ∑b\sum b。此时最优方案之一大概就是把所有东西两两匹配，把小的变成大的，所以此时贪心地把 b2b_2 变成 b1b_1，b4b_4 变成 b3b_3……即把 b2xb_{2x} 变成 b2x−1b_{2x-1} 即可。有一个问题是如果 bb 的长度是奇数该怎么办，即最后剩了一项消不掉，记为 tt。此时我们可以借助其它的不与 tt 相同的数，直接给它加上 tt 即可，相当于给它二进制上的这一位赋值成 11，所以不会有问题。最小代价即为 ∑i=1l(−1)i+1bi\sum^l_{i=1}(-1)^{i+1}b_i。
至于构造方案，我似乎没有一个特殊的好写的做法专门做这一档。场上写这一档写了一个小时破防了，后来发现直接按上面的匹配写搜索会漏很多东西，所以我改进后的做法的这个搜子不太像人写的。所以结合前面的算法期望得分只有 3434。
所以开头应当改成我不会 A 性质。

算法 4

我会按位贪心！
场上我根据手玩 A 性质的构造方案得出了一个有意思的结论：对于排序后的序列 aa 上的一个修改操作，如果有一种方案是把 aia_i 改成一个 (ax,ax+1](a_x,a_{x+1}] 之间的数，这相当于一次对于每个 i≤j<xi\le j<x，都先把一个值等于 aja_j 的数改成 aj+1a_{j+1}，然后再做后面的操作。这会产生大量的方案。这也告诉我们，我们可以倒着做这些操作。如果需要一个 (ax,ax+1](a_x,a_{x+1}] 的数，而需要把一个 ai<xa_{i<x} 变成这个，则我们先把 axa_x 变过来也是等价的。
这就引出一个贪心。我们按位决策，如果某一位上的异或和是 11，我们把一个 00 变成 11。变哪个好呢？由上述思考，如果抛弃了更高的所有位（可以发现确实可以这样做），我们取这一位是 00 的所有数里最大的一个来改。因为如果要改能小的，其实也可以用改最大的这一步来替代。
只需要注意我们要求存在一个这一位是 00 的。如果这一位全是 11 就不对了。这正好符合我们的 B 性质！如下参考代码可以通过 B 性质的第一问，时间复杂度 O(nlog⁡V)O(n\log V)，随手实现排序可以多一个 log⁡n\log n。结合前面的算法可以获得 5656 分。
CPP
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=1m=1 的构造方案。结合前面的算法可以获得 6262 分。这大概也就是包含笔者的 31\sout{31} 个 262\sout{262} 的由来。

算法 5

我会爆搜性质 B！
我们需要技巧性的快速爆搜。注意到上面用过的一个性质：我们处理完每一位之后可以直接扔掉这一位！这也就是说一个合理的方案最多只会用到 log⁡V\log V 个操作。
考虑刚才分析“只操作最大的那个数”的结论，如果我们操作了一个更小的数，然后把它拆成了若干个步骤：ai→ax1,ax1→ax2,…,axp→target(ai)a_i\rightarrow a_{x_1},a_{x_1}\rightarrow a_{x_2},\dots,a_{x_p}\rightarrow \rm{target}(a_i)。此时对当前这一位有影响的实际上只有最后一个改变 axpa_{x_p} 的操作是把这一位的 00 变成 11 的。于是确实可以看成，每一位只做一个操作，而且是把后 i−1i-1 位清空，把第 ii 位置成 11。
我们基于这个结论搜索，并基本确保当前搜索到的序列 aa 是有最小代价解的。注意到如果某一位选择的是操作后 ii 位是 xx 的，有解，则选择操作后 ii 位比 xx 更大的一定也有解。于是可以得到如果 xx 无解，则比 xx 小的也无解。我们按所有数的后 ii 位排序，然后依次尝试修改这一位，然后搜索函数反悔“当前状态搜下去是否有解”，如果遇到无解了就直接退出即可。
考虑排序的次数，我不太会证明，也不太会感性理解根据题解时间复杂度也许是 O(nlog⁡nlog⁡V+mlog⁡V)O(n\log n\log V+m\log V)？这个太神秘了，但是确实跑得很快。结合前面的算法期望得分 8484。
注意如果某一位是不需要操作的我们就不能去遍历每一位了，否则会在 #18 获得 TLE 的好成绩。所以尽量实时维护异或和。
这个问题是我写完无特殊性质之后才发现的，所以只能提供一个 TLE on #18 的代码。
注意你需要提前把最小代价求出来。然后其实特殊性质 A 大部分时候是被 B 包含的，这个代码理应也可以通过，但是仍然要特判 nn 是奇数且所有数相等，具体见算法 33 的第一部分。但是我很懒没写这个部分。

算法 6

我会正解！
考虑没有特殊性质 B 的情况。根据上面的分析，这个做法只会在 nn 为奇数且某一位全都是 11 的时候会寄。
这个东西还有一个特性：之前的每一位异或和都是 00。否则一次操作一定会清空某个数的后 i−1i-1 位，然后这种情况就不存在了。
这个时候我们显然至少要把一个 11 改成 00，而我们只能用加法，所以麻烦的是这会影响更高位（而把 00 变成 11 不会这么麻烦，感性理解这当然是严格更优的，所以我们非必须不把 11 改成 00）。
我们声称在最终方案中，第一个有过修改的位一定是有两个 00 变成了 11。首先必须得有修改的，其次不能影响个数的奇偶性。所以只需要考虑是为什么不是把 11 变成 00。其实很好理解，如果这样了就一定有了进位，那后面总有位变大了。即使上面每一位都只有 11 个 00，我们也可以取值域外的 2602^{60} 这一位，所以肯定是有 2V2V 内的解的。
然后做法就很直接了，直接枚举是哪一位操作了两次，然后由于这里直接会有一步清空，下面就不会再出现这种情况了。在求最优解的时候，直接取后 ii 位最大的两个数操作，原理是同理的。在爆搜方案的时候，我们先从大到小枚举第一个操作的数。对于第一个数确定的情况，我们按上面的策略，第二个数从大到小，到无解为止。到第一个数对应的所有第二个数都无解的时候就退出。
时间复杂度也很神秘，据说是只需要多乘一个 log⁡V\log V，也就是 O(nlog⁡nlog⁡V+mlog⁡2V)O(n\log n\log V+m\log^2V)。官方题解是这么写的，但是我也不知道为什么 nn 那项没多乘一个 log⁡V\log V，反正它还是跑得很快。期望得分 100100 分。
参考代码。一个调了很久的锅是 inf⁡\inf 开小了，只开了 101810^{18}，警钟长鸣。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...