bzoj1022/洛谷P4279 关于Nim游戏的一点理解

题目分析

https://www.cnblogs.com/Robert-Yuan/p/5282669.html

Nim游戏

马上就要到高考假了，老师给大家发了许多许多卷子作为礼物，小L将各科卷子分类放好之后，小B说了一个提议：

我们来玩一个游戏吧，每次选择一堆卷子，轮流从其中拿走几张，但是不能不拿。谁没有卷子拿了，谁就输了。输了的人要帮赢了的人写一张卷子。

小L觉得海星，反正她也不想写卷子。结果小B赢了无数次，这令小L困惑不已，只见小B露出了一个神秘的微笑。

莫非是有必胜策略？小L仔细思考，发现自己果然被小B坑了：

假设第i堆试卷有 S(i) S ( i ) 张，则S的异或和k为0的为必败状态P,否则为必胜状态N。这是由于：

1.如果当前处于N,则下一步必到P

如果当前取了第i堆的石子，使该堆变为 B(i) B ( i ) 个石子， A(1)xorA(2)xor...B(i)xor...=k2=0 A ( 1 ) x o r A ( 2 ) x o r . . . B ( i ) x o r . . . = k 2 = 0 ，则有 k2xork=0 k 2 x o r k = 0 ，则有 A(i)xorB(i)=0 A ( i ) x o r B ( i ) = 0 即 A(i)=B(i) A ( i ) = B ( i ) ，与不能不取矛盾。

2.如果当前处于P,则下一步可到N

找到所有A中的最大值A(i)，则其二进制下最高为1的位一定是k二进制下最高为1的位，那么A(i)异或k小于A(i)，所以让A(i)异或一下k是一个合法策略，并且这样 k2 k 2 会变为0.

Nim游戏的变形

小B又露出一个神秘的微笑，然后说道：

这样吧，我们再玩一轮。谁拿走最后一张卷子就输了，如果你赢了就不用帮我写卷子了。

小L觉得自己已经学会了Nim游戏，一定不会输的！

……然后就输了。

难道这种游戏还有什么玄机？小L略一思索，忽然恍然大悟。

记老师很仁慈只布置了一张试卷的堆为 K1 K 1 ，有多于1张卷子的堆为 K2 K 2 。

然后记 P P 状态下，无K2K2堆的记做 P0 P 0 ，一个 K2 K 2 堆的记做 P1 P 1 ，否则记做 P2 P 2 。同理定义 N0 N 0 ， N1 N 1 和 N2 N 2 。

那么:

1. N0 N 0 必败。

因为有奇数个 K1 K 1 堆，轮流拿就先手必败了。

2. P0 P 0 必胜。

偶数个 K1 K 1 堆，轮流拿先手必胜。

3. N1 N 1 必胜。

因为如果有奇数个 K1 K 1 堆，就把那个 K2 K 2 堆一窝端了。否则让 K2 K 2 堆留下一张“革命的火种”。

4. P1 P 1 不存在。

因为那些 K1 K 1 堆异或和不是1就是0，显然剩下那个 K2 K 2 堆里面试卷数量是多少都不可能让总异或和为0。

5. N2 N 2 必胜， P2 P 2 必败。

你不可能一口气让两个 K2 K 2 堆消失，所以 P2 P 2 只能转到 N1 N 1 或是 N2 N 2 ，当然 N1 N 1 是必胜的啦，所以要尽量往 N2 N 2 转。

而 N2 N 2 状态下，A最大的那一堆i一定是个 K2 K 2 堆，让其异或k。如果此时它变成了一个 K1 K 1 堆，说明除i堆外的异或和为1。显然其他堆要么全是 K1 K 1 堆（但那就不是 N2 N 2 状态了），要么有两个以上的 K2 K 2 堆，这样操作后的 K2 K 2 堆个数不会少于两个。而如果异或后它还是一个 K2 K 2 堆，那么 K2 K 2 堆个数也不会少于两个，也就是说 N2 N 2 状态绝对可以转化为 P2 P 2 状态。

所以这么转来转去，最后的归宿一定是 N1 N 1 状态了啊……

然后就 N2 N 2 必胜， P2 P 2 必败了。

技不如人，甘拜下风。小L只能帮小B去写卷子了。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int q=;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*+ch-'0',ch=getchar();
    return q;
}
#define RI register int
int T,n,js,kl;
int main()
{
    T=read();
    while(T--) {
        n=read();js=,kl=;
        for(RI i=;i<=n;++i) {
            int x=read();kl^=x;
            if(x>) ++js;
        }
        if((js==&&kl==)||(js>&&kl)) puts("John");
        else puts("Brother");
    }
    return ;
}
           

Nim游戏其他变形

有 n n 堆卷子，每次可以选择一堆，取11到 m m 张，不能取的人输，求先后手谁胜。

将所有堆的卷子数都模上m+1m+1，然后异或起来，为0则后手胜，否则先手胜。

有 n n 堆卷子，每次可以从kk堆中拿卷子，至少拿走一张卷子，不能取的人输，求先后手谁胜

将所有堆卷子数转化为 k+1 k + 1 进制，然后做不进位的加法，为0则后手胜，否则先手胜。

有一个台阶，其中有几阶上放了几堆卷子，每次可以选择一堆，设该堆在第i阶，从其中取至少一张卷子，移到第i-1阶，0阶的卷子不能动，求先后手谁胜。

只看奇数阶上的卷子，异或起来为0则后手胜，否则先手胜。