【BZOJ1022】【SHOI2008】小约翰的游戏

SJ定理：对于任意一个Anti-SG游戏，如果我们规定当局面中所有的单一游戏的SG值为0时，游戏结束，则先手必胜当且仅当：（1）游戏的SG函数不为0且游戏中某个单一游戏的SG函数大于1；（2）游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1。

// <1022.cpp> - 07/02/16 10:49:03
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=100001;
const int INF=1e9;

int main(){
    int T=gi();
    while(T--){
        int n=gi(),ans=0;bool f=1;
        while(n--){
            int x=gi();
            if(x!=1)f=0;
            ans^=x;
        }
        puts(bool(ans)^f?"John":"Brother");
    }
    return 0;
}

// <1022.cpp> - 07/02/16 10:49:03

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=100001;

const int INF=1e9;

int main(){

int T=gi();

while(T--){

int n=gi(),ans=0;bool f=1;

while(n--){

int x=gi();

if(x!=1)f=0;

ans^=x;

}

puts(bool(ans)^f?"John":"Brother");

}

return 0;

}

说点什么