某岛

… : "…アッカリ~ン . .. . " .. .
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;
}

...