danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

26247

[BZOJ 1022]小约翰的游戏

2016年8月24日 11:02 | Comments(0) | Category:题解 | Tags:

这个题是比较特殊的游戏。因为扩展出最后一个状态的人会输。这种游戏称为Anti-SG游戏。

解决这种题,需要SJ定理:先手必胜当且仅当游戏的SG函数为0而存在一个单一游戏的SG函数大于1,或整个游戏的SG函数不为0且没有任何单一游戏的SG函数大于1。问题迎刃而解。

代码:

/**************************************************************
    Problem: 1022
    User: danihao123
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:820 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
    register int i,last;
    int n,temp,T;
    bool obey_1;
    scanf("%d",&T);
    while(T--){
        obey_1=false;
        last=0;
        scanf("%d",&n);
        for(i=1;i<=n;i++){
            scanf("%d",&temp);
            if(temp>1){
                obey_1=true;
            }
            last=last^temp;
        }
        if((last!=0 && obey_1) || (last==0 && !obey_1)){
            puts("John");
        }else{
            puts("Brother");
        }
    }
    return 0;
}