bzoj 1022 小约翰的游戏John

题目大意：

n堆石子，两个人轮流取石子，每个人取的时候，可以随意选择一堆石子

在这堆石子中取走任意多的石子，但不能一粒石子也不取，取到最后一粒石子的人算输

思路：

首先当每堆石子数都为1时，偶数为先手必胜，奇数为先手必败

当有一堆石子数不为1时，先手可以使堆变为奇数个1的堆，即先手必胜

而如果有很多堆石子数不为1，如果异或和不为0，则先手可以把异或和变为0 变为必胜态

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<cstdlib>

 #include<cstring>

 #include<queue>

 #include<map>

 #include<vector>

 #define ll long long

 #define inf 2147483611

 #define MAXN 1010

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}

     while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int T,n;

 int main()

 {

     T=read();int sum,a;bool f;

     while(T--)

     {

         n=read(),sum=f=;

         for(int i=;i<=n;i++)

         {

             a=read();

             sum^=a;

             if(a!=) f=;

         }

         if((!f&&!sum)||(sum&&f)) puts("John");

         else puts("Brother");

     }

 }

巴特西

bzoj 1022 小约翰的游戏John

最新文章

热门文章