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則後手勝，否則先手勝。