题意分析

这道题目是一个博弈论问题，涉及到经典的Nim游戏变种。题目大意是：John和他的弟弟玩一个游戏，有一个装满不同颜色M&M豆的盒子。游戏规则如下：

• 两人轮流取同一颜色的M&M豆，每次至少取1颗
• 吃掉盒子里最后一颗M&M豆的人输
• John总是先取，两人都采取最优策略
• 需要根据不同颜色M&M豆的数量，判断谁会赢

解题思路

通过分析代码和题目描述，可以得出以下解题思路：

1. Nim游戏基础：标准Nim游戏中，玩家从若干堆物品中取物，取最后一个物品的人赢。而本题是Nim游戏的变种（取最后一个的人输）。

2. 关键观察：

   • 当所有堆的石子数都是1时，游戏结果只与堆数的奇偶性有关
   • 当存在至少一个堆的石子数大于1时，需要用Nim游戏的异或规则判断

3. 判断条件：

   • 如果所有堆的石子数都是1：
     • 堆数为奇数时，John输（因为最后一颗由John取）
     • 堆数为偶数时，John赢
   • 如果存在至少一个堆的石子数大于1：
     • 计算所有堆石子数的异或和
     • 异或和不为0时，John赢（Nim游戏中先手必胜态）
     • 异或和为0时，John输（Nim游戏中先手必败态）

标程

#include<cstdio>
#include<cstring> 
#include<iostream>
using namespace std;
 
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        int res=0,Max=0;
        for(int i=1,x;i<=n;i++){
            scanf("%d",&x);
            res^=x;  // 计算异或和
            Max=max(Max,x);  // 记录最大堆的石子数
        }    
        // 判断胜负
        if(res&&Max>1|| res==0&&Max<=1) puts("John");
        else puts("Brother");
    }
}

代码的核心逻辑是：

1. 读取测试用例数T
2. 对于每个测试用例：
   • 读取颜色数n和各颜色的M&M豆数量
   • 计算所有数量的异或和res，并记录最大数量Max
   • 根据异或和res和最大数量Max判断胜负：
     • 当res≠0且Max>1，或者res=0且Max≤1时，John赢
     • 否则弟弟赢

胜负判断逻辑详解

1. 情况一：存在至少一个堆的石子数大于1（Max>1）

   • 这是标准Nim游戏的变种，使用异或和判断：
     • 异或和res≠0：John可以采取最优策略让弟弟进入必败态，John赢
     • 异或和res=0：无论John怎么取，弟弟都能让John进入必败态，弟弟赢

2. 情况二：所有堆的石子数都是1（Max≤1）

   • 此时游戏变为取石子数为1的堆，每次必须取一个堆的全部（因为只有1颗）
   • 堆数n为奇数时：总共有奇数个1，John取第1、3、5...个，最后一个由John取，John输
   • 堆数n为偶数时：John取第1、3、5...个，最后一个由弟弟取，John赢
   • 对应代码中的条件：res=0（所有1的异或和为0）且Max≤1时，John赢当且仅当n为偶数

算法正确性证明

• 当Max>1时：符合Nim游戏的胜负规则，异或和非零则先手必胜
• 当Max=1时：所有堆都是1个石子，游戏等价于取石子次数的奇偶性判断：
  • 堆数n为偶数：John取n/2次，弟弟取n/2次，最后由弟弟取最后一个，John赢
  • 堆数n为奇数：John取(n+1)/2次，弟弟取(n-1)/2次，最后由John取最后一个，John输

该算法通过简洁的条件判断，正确融合了两种情况的胜负规则，能够在O(n)时间内解决每个测试用例。