lp2197 NIM游戏

图文无关,因为空和白玩的游戏中没有一个是ICG类的。

NIM游戏是一类经典的博弈论题目。
众所周知,NIM游戏的结果就是把所有的答案异或起来即可。为什么可以这么做呢?
我们定义,对于一个「均衡组合博弈(ICG)」 ,我们定义两种局面状态:P(先手必败)和N(先手必胜)。
首先我们可以知道,在ICG中,博弈是一定会终止的;同时,终止局面是P局面。如果说一个局面的所有子局面都是N局面或者P局面,那么这个局面也一定是N局面或者P局面:这是因为N局面和P局面存在性质:
一个局面是P局面,当且仅当它的所有子局面都是N局面;一个局面是N局面,当且仅当它的所有子局面中存在一个是P局面。
这也就意味着,对于任何一种状态,我们都可以判定它是N状态还是P状态。
那么,初始状态的N-P性是可以判断的。
如何计算一个局面的N-P性呢?
我们定义一种运算,使得:
P局面经过这种运算只能变成N局面;
N局面经过这种运算可以变成P局面。
当我们用一个数列描述一个局面后,我们惊讶地发现:异或——这里指的是将局面中的每一个子部分异或起来——是满足这个性质的。
我们定义,异或值为零的局面是必败局面;异或值非0的局面是必胜局面。
我们将描述这个局面的数列异或起来,如果它等于零,那么任意一种「减少」操作——导致它的一个值减少的,一定会导向一种P局面;
而对于一种P局面,依据按位异或的特性,一定可以通过减少最大的数,来变更想变更的任意一位。
故而,我们发现,对于任意一种局面,我们可以用异或运算来判断它的N-P性。
事实上,两者之间并不存在那么直接的数学上的对应关系。可以将NIM游戏理解为一个数学模型。
这是一种指代关系。换句话说,为了更方便地处理它,
我们可以将这个局面转化为数学模型,而异或运算刚好满足其性质——这并不是说异或运算本身就是这个局面的变化。
当理解这一点之后,异或的意义就很显然了。

#include<iostream>
#include<cstdio>
using namespace std;
int n,a[10005];
void init(){
    scanf("%d",&n);
    int x=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        x^=a[i];
    }
    if(x){
        puts("Yes");
    }else{
        puts("No");
    }
    return;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

发表评论

您的电子邮箱地址不会被公开。