HDU 1907 John (ANTI-SG)

在贾志豪的论文中有提到这种游戏：组合游戏略述——浅谈SG游戏的若干拓展及变形
以下直接引用定理及证明
[定理]（SJ定理）对于任意一个Anti-SG游戏，如果我们规定当局面中所有的单一游戏的SG值为0时，游戏结束，则先手必胜当且仅当：（1）游戏的SG函数不为0且游戏中某个单一游戏的SG函数大于1；（2）游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1。
[证明] 我们只需要证明：
（1）所有的终止局面为先手必胜局。（这一点显然，证明中略去）
（2）游戏中的任何一个先手必败局一定只能够转移到先手必胜局；
（3）游戏中的任何一个先手必胜局一定能够转移到至少一个先手必败局。
情况一：局面的SG函数为0且游戏中某个单一游戏的SG函数大于1。 ∵当前局面的SG函数值为0 又∵SG函数性质（1） ∴它所能转移到的任何一个局面的SG函数值不为0 ① ∵当前局面的SG函数值为0且游戏中某个单一游戏的SG函数大于1。
∴当前局面中必定至少有2个单一游戏的SG函数大于1。又∵每次至多只能更改一个单一游戏的SG值 ∴它所能转移到的任何一个局面都至少有一个单一游戏的SG值大于1。 ② 由①②得，情况一所能转移到的任何一个局面都为先手必胜局。
情况二：局面的SG函数不为0且游戏中没有单一游戏的SG函数大于1。显然，当前局面一定有奇数个游戏的SG函数值为1，其余游戏的SG函数值为0。
（1）将某个单一游戏的SG值更改为大于1的数。
∵转移前没有单一游戏的SG值大与1，转移将某个单一游戏的SG值更改为大于1的数。 ∴转移后的局面一定有且只有一个单一游戏的SG值大于1。 ③ ∴后继局面的SG值一定不为0。 ④ 由③④得，后继局面一定为先手必胜局。
（2）将某个单一游戏的SG值更改为0或1。
∵转移是将某个SG值为0的单一游戏改成SG值为1的单一游戏，或将某个SG值为1的单一游戏改成SG值为0的单一游戏。 ∴转移后的局面一定有偶数个SG值为1的单一局面且不含有SG值大于1的局面。
∴后继局面一定为先手必胜局。情况三：局面的SG函数不为0且游戏中某个单一游戏的SG函数大于1。（1）局面中只有1个单一游戏的SG值大于1。我们选择更改SG值最大的单一游戏，我们可以选择将其更改成0或1来保证转移后的局面有且只有奇数个SG值为1的单一游戏。
则通过这种方式转以后的局面为先手必败局。（2）局面中有至少两个单一游戏的SG值大于1。根据SG函数性质（2），总存在一种决策可以将后继局面的SG函数值变为0 ⑤ ∵局面中有至少两个单一游戏的SG值大于1 又∵每次最多只能更改一个单一游戏的SG值 ∴后继局面中至少有一个游戏的SG值大于1 ⑥ 由⑤⑥得，后继局面为先手必败局。情况四：局面的SG函数为0且游戏中没有单一游戏的SG函数大于1。
当局面中所有单一游戏的SG值为0时，游戏结束，先手必胜。否则，局面有且仅有偶数个SG值为1的单一游戏，其余游戏的SG值为0。我们只需将其中的某一个SG值为1的单一游戏的SG值变为0，游戏中即可出现奇数个SG值为1的单一游戏，到达先手必败局。综上，证明完毕！

拷贝过来有点乱，直接去看原文吧
总之就是结论（1）游戏的SG函数不为0且游戏中某个单一游戏的SG函数大于1；（2）游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1。
在这个NIM游戏中，SG值便是石子数量
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 10005
#define LL long long
#define inf 1<<29
#define eps 1e-7
using namespace std;
int main(){
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int k,cnt=0,ans=0;
        while(n--){
            scanf("%d",&k);
            if(k>1)
                cnt++;
            ans^=k;
        }
        if(cnt){
            if(ans==0)
                puts("Brother");
            else
                puts("John");
        }
        else{
            if(ans==0)
                puts("John");
            else
                puts("Brother");
        } www.zzzyk.com
    }
    return 0;
}

作者：ACM_cxlove

补充：软件开发 , C++ ,