题解 P2197 【nim游戏】

aiyougege · 2018-02-22 15:06:45 · 题解

做法

　　正确做法是将所有石子求异或和, 如果异或和为零则后手必胜.否则后手必胜. 为什么这个结论是正确的呢? 　　

• 如果石子中的异或和不为0, 先手一定可以在一步之内将其变成0. 像如果异或和为0000...1...101011,其中某位为是1的最高位, 那么一定存在一堆石子它在这一位上为1, 通过改变这堆石子可以将异或和变为0. 所以先手必胜.

• 如果异或和为0, 先手无论如何取异或和都会改变, 所以先手必败.

  Code

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;

inline int read(){
    char ch=getchar();int s=0;
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
    return s;
}

int main(){
    int T,n,m,add;
    T=read();
    while(T--){
        add=0;n=read();
        while(n--)add^=read();
        if(!add)printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}