某島

… : "…アッカリ~ン . .. . " .. .
December 17, 2010

Nim Game

Nim Game問題是博弈問題中的重頭戲,也是現在信息學競賽中考察最多的。Nim Game往往與xor運算相聯繫,同時又引出了很多的分支,最經典的是Nim-k、anti-Nim、Staircase Nim、take&break四個拓展問題。此外還有Misère Nim,概率問題。



1.傳統的Nim Game

問題描述:
有若干堆石子,兩個遊戲玩家輪流取,每次可以在一堆中取若干個,至少取一個,可以一次取完,問是否有必勝策略。

問題分析:
對於一個局面,令S = P1 ^ P2 ^ P3 ^ …^ Pn。若S = 0則為先手必敗局面,否則為先手必勝局面。

證明:
若當P1 = P2 = …. = Pn = 0 時,S = 0 ,滿足終狀態是先手必敗局面。
若S = 0 ,即P1 ^ P2 ^ P3 ^ …^ Pn = 0,若取堆i中的石子,Pi – > Pi 』,S -> S』 ,Pi > Pi』 ,則Pi ^ Pi』 != 0 。所以S』 ^ Pi^ Pi』 = S = 0 ,即S』 = Pi ^ Pi』 != 0 。滿足先手必敗局面的所有子局面都是N局面。
若S != 0 ,設S的二進位位是A1…An ,考慮第一位是1的。在P中取出該位同是1的,不妨設為P1 。可知P1 ^ S < P1 ,令P1』 = P1 ^ S 。可知P1』 ^ P2』 ^ … ^ Pn = 0 。即先手必勝局面存在至少一個子局面是先手必敗局面。(證完) Program:

#include 
using namespace std ;

int main(){
    int s=0 , n, x;
    cin >> n;
    for (int i=1;i<=n;i++)
        cin >> x, s ^= x;
    cout << (s!=0 ? "win":"lose") << endl;
}


.




2.Nim-k Game

問題描述:
兩人輪流對N堆石子進行操作,每堆分別有Pi顆。每人每次可以從最多K堆中取走任意多顆石子,但至少要取走一顆石子。誰取到最後一顆誰勝利。什麼情況下先手必勝,什麼情況下後手必勝

問題分析:
這個題目是Nim Game的拓展問題。與Nim Game不同點在於這次可以在k堆中取。
首先,我們要來分析一下異或運算,二進位的異或運算我們可以看作是數字的不進位加法mod 2。那麼我們同樣定義k進位異或運算為數字的不進位加法mod k。那麼,從Nim Game推廣,Nim-k Game能不能利用 (k+1) 進位異或來解決呢?不難證明,這個方法是成立的。我們可以看一個例子:
K=2
3—————— 1 1
5—————— 1 0 1
10—————— 1 0 1 0
15————— 1 1 1 1
2 2 0 0 (mod 3)
所以這是先手必勝局面,第一步取10->6 15->7可以到達一個先手必敗局面。
3—————— 1 1
5—————— 1 0 1
6—————— 0 1 1 0
7—————— 0 1 1 1
0 0 0 0 (mod 3)
這樣,我們就可以利用類似Nim Game的方法解決Nim-k Game了。

#include 
using namespace std ;
int n , k , x ;
int Ans[32] ;
int main() {
    cin >> n >> k ;
    for (int i=0;i<32;i++) Ans[i] = 0 ;
    for (int i=1;i<=n;i++){
        cin >> x ;
        for (int j=0;j<32;j++) Ans[j] += ( x >> j ) & 1 ;
    }
	
    int i;
    for (i=0;i<32;i++) if (Ans[i] % (k+1) != 0) break ;
	cout << (i<32 ? "win" : "lose") << endl;
}

...