题解 P2197 【nim游戏】

· · 题解

嗯

怎么说，今天听了tsb大佬的博弈，真是大开眼界。 大佬只用了五分钟入门之后就给我们引出了nim游戏这个东东

很多同学听完之后都比较方，我也不例外，除了机房最强wdy外都静悄 悄的，于是闲着无聊就翻开了nim游戏的题解看了看，想了想那个异或结论的证明，发现tsb和置顶题解的发表者“秋日私语”大佬的证明方法都有一点瑕疵和难以理解之处，便想结合自己的想法来给大家讲讲nim游戏异或的结论到底是怎么来的：

首先还是要盗取一下“秋日私语”大佬的基本图片，身为蒟蒻的我就只能给大佬的证明方法作注了

原文基础如下：

步骤1:将所有终结位置标记为必败点（P点）； 步骤2: 将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点） 步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点） ，则将该点标记为必败点（P点） ； 步骤4: 如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。

注解如下： 1.首先当所有石子的数量为零先手必输：

因为根本就没有能让你取的石子，你也就只能输了

2.第二句话其实有语病，意思通顺后应该是说：

设k（异或和）的最高位1的位置为i（即最高位1的位置为i），那我们找到一堆石子，什么样的石子呢，该堆石子的i位也为1.

这句话中想必大家会提出两个问题；1.为什么要找到最高位1；2.为什么会必定有一堆石子他的i位为1

让我来一一解答：

1.对于第一个问题不理解的同学恐怕是没能理解原作者的基础暴力算法，这个二进制异或的结果是通过异或后最高位1异或1到0来减小这个值最终达到所有石子全是0的目的的，所以要找到最高位1这样就可以将非零数异或成0

2.根据异或运算法则,如果i位全部都是0的话结果的第i为自然也不会出现1

3.第三局话也是对应位运算的法则，就相当于选取出i位为1的石堆后如果该位为1，则相应异或该石堆后就为零，零还是零，这样子通过对异或和的其中一部分取反则可以导致异或和归零，把该结果呈给对手则对手必败

4.如果异或和为0了但堆数却不为零，那么无论你是1变0还是0变1都不能继续保持异或为零，应为你不能改变另外一堆石子的同样二进制位数使操作抵消继续保持零

好啦，其实真正精华的部分在这里

为什么异或和非零的状态呈给我我就可以必赢

我可以通过寻找最高位1取反的方法来使得石头数减小并且异或和保持零，而对手无论如何不能保持异或和为零，就这样循环下去，石子数不断减小，而我可以将对手操纵后的异或和再次改为零

最终我一定可以将石子数为零（石子数在过招过程中不断减小），异或和也为零的结果呈对手，这样我也就必赢了

九九归一到原作者的思想：

步骤1:将所有终结位置标记为必败点（P点）； 步骤2: 将所有一步操作能进入必败点（P点）的位置标记为必胜点（N点） 步骤3:如果从某个点开始的所有一步操作都只能进入必胜点（N点） ，则将该点标记为必败点（P点） ； 步骤4: 如果在步骤3未能找到新的必败（P点），则算法终止；否则，返回到步骤2。

最终必败的结果就是a[]=0,0,0,0,0,0,0,0,0啊

我要做的就是在过招过程中不断保持可以将这个结果最终呈给对手，过程中保持石子数递减并异或和为0（代表情况可以控制）就可以了