1022: [SHOI2008]小约翰的游戏John

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1022

博弈论。
若石子只有1或0，1为奇数个则为必败态，1为偶数个则为必胜态。

若并不只有1或0，考虑抑或值，为0则必败，否则必胜。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;

int t,n;

int main()
{
    scanf("%d",&t);
    for (int i=0;i<t;i++)
    {
        scanf("%d",&n);
        int ans=0,tot=0;
        bool flag=0;
        for (int j=0;j<n;j++)
        {
            int x;
            scanf("%d",&x);
            ans^=x;
            if (x!=1)
            {
                flag=1;
            }
            if (x==1)
            {
                tot++;
            }
        }
        if (flag==0)
        {
            if (tot%2==1)
            {
                printf("Brother\n");
            }
            else
            {
                printf("John\n");
            }
        }
        else
        {
            if (ans==0)
            {
                printf("Brother\n");
            }
            else
            {
                printf("John\n");
            }
        }
    }
    return 0;
}

posted on 2013-02-08 14:43 Kiro 阅读(94) 评论(0)  编辑 收藏 引用 所属分类: 衡八oj

只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理