[BZOJ1022][SHOI2008][博弈論][Nim遊戲]小約翰的遊戲

[Problem Description] 小約翰經常和他的哥哥玩一個非常有趣的遊戲：桌子上有n堆石子，小約翰和他的哥哥輪流取石子，每個人取的時候，可以随意選擇一堆石子，在這堆石子中取走任意多的石子，但不能一粒石子也不取，我們規定取到最後一粒石子的人算輸。小約翰相當固執，他堅持認為先取的人有很大的優勢，是以他總是先取石子，而他的哥哥就聰明多了，他從來沒有在遊戲中犯過錯誤。小約翰一怒之前請你來做他的參謀。自然，你應該先寫一個程式，預測一下誰将獲得遊戲的勝利。 [Algorithm] 博弈論Nim遊戲 [Analysis] 經典的nim遊戲。稍有不同的是這裡是最後一個取的輸。經典的nim有一個定理，所有石子個數xor起來如果==0，說明brother赢，否則john赢。這裡也是這樣的（因為隻要選的時候少拿一個就能強迫對手拿最後一個），但是當石子全部都是1的時候，情況恰恰相反，特判一下就好了…… [Pay Attention] 不要跟經典模型混了…… [Code]

/**************************************************************
    Problem: 1022
    User: gaotianyu1350
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:1272 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
using namespace std;
 
#define MAXN 600
 
int main()
{
    int testcase, n, ans, x;
    scanf("%d", &testcase);
    while (testcase--)
    {
        scanf("%d", &n);
        ans = 0;
        bool oneonly = true;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &x);
            if (x != 1) oneonly = false;
            ans ^= x;
        }
        if (!oneonly)
        {
            if (ans == 0)
                printf("Brother\n");
            else
                printf("John\n");
        }
        else
        {
            if (ans == 0)
                printf("John\n");
            else
                printf("Brother\n");
        }
    }
}