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

题目：传送门

题目大意：

　　一道反nim游戏，即给出n堆石子，每次可以取完任意一堆或一堆中的若干个（至少取1），最后一个取的LOSE

题解：

　　一道很不错的题目啊，感觉可以作为一道很好的入门题

　　读前一戳：博弈论文 && POPQQQ大佬%%%

　　大体要分为三种情况来讨论：

　　 1、全是为1的石子堆，如有偶数堆则先手胜，反之后手胜

　　 2、有两堆相同的石子且都不为1（后手获胜的几率很大）：
　　　　　那么如果先手将其中一堆取剩1，那么后手就可以将另一堆取完，此时后手胜

　　　　　如果先手将其中一堆取完，那么后手就可以将另一堆取剩1，还是后手胜

　　如果先手仅拿走其中一堆的一部分，那么后手可以进行相同的操作，将另一堆也拿走相同的数量（这是情况又回到了上面两种）

　　 3、如果异或和不为0，那么对于一般的nim游戏一定可以将石子堆变成仅剩两堆相同的（平衡状态xor=0），这时又如上面所述了

　　总结：

　　如果全是石子数为1，异或和为0则先手胜，反之后手胜

　　如果有不为1的，异或和不为0则先手胜，反之后手胜

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int T,n;

 int main()

 {

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);int x,ans=;bool flag=true;

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

         {

             scanf("%d",&x);ans^=x;

             if(x!=)flag=false;

         }

         if(flag==true)

         {

             if(ans==)printf("John\n");

             else printf("Brother\n");

         }

         else

         {

             if(ans==)printf("Brother\n");

             else printf("John\n");

         }

     }

     return ;

 }

巴特西

bzoj1022: [SHOI2008]小约翰的游戏John（博弈SG-nim游戏）

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

最新文章

热门文章