题解 P2197 【nim游戏】

Playnext · 2018-02-16 17:19:51 · 题解

模板题。

Nim游戏基本模型：

有任意堆物品，每堆物品个数任意，双方轮流从中取物品，一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜。

结论：

如果物品数全部异或起来的值为0，那么先手必败，否则先手必胜。

在此不做证明。

代码：

#include <bits/stdc++.h>
using namespace std;    //BY Playnext
#define REG register
#define IN inline
#define AN __inline__ __attribute__ ((always_inline))
#define For(X,Y,Z) for (REG int X=Y; X<=Z; X++)
#define FOR(X,Y,Z) for (REG int X=Y; X<Z; X++)
#define Space()   putchar (32)
#define Enter()   putchar (10)
const int MAXN=1e4+1, INF=2147483647, MOD=1000000007;

#define FileSize 1<<15
char Buffer[FileSize], *Cur, *End;  
#define NextChar() (Cur == End && (End = (Cur = Buffer) + fread (Buffer, 1, FileSize, stdin), Cur == End) ? EOF : *Cur ++)

AN void Read (REG int &Temp) {
    REG int Negative = 1;       Temp = 0;
    REG char Next = NextChar ();

    while (!isdigit (Next)) {
        if (Next == '-')    Negative = -1;
        Next = NextChar ();
    }   

    while (isdigit (Next)) {
        Temp = Temp *10 + Next - 48;
        Next = NextChar ();
    }

    Temp*= Negative;
}

IN void Write (REG int Temp) {
    if (Temp < 0)   Temp = -Temp, putchar('-');
    if (Temp > 9)   Write (Temp /10);
    putchar (Temp %10 + '0');
}

int main () {
//  freopen ("Input.txt", "r", stdin);
//  freopen ("Output.txt", "w",stdout);
    REG int n, m;   Read (n);
    FOR (i,0,n) {
        Read (m);   REG int Ans, Num;
        Read (Ans);
        FOR (h,1,m)
            Read (Num), Ans ^= Num;
        printf (Ans ? "Yes\n" : "No\n");
    }
    return 0;
}