目录
前置知识尼姆博弈(Nim Game)反尼姆博弈（Anti - Nim）
前置知识
经典博弈论问题——巴什博弈 异或运算的概念 还不了解的小伙伴可以点击进去详细讲解
尼姆博弈(Nim Game)
【模板】Nim 游戏
题目描述
甲，乙两个人玩 nim 取石子游戏。 nim 游戏的规则是这样的：地上有
n
n
n 堆石子（每堆石子数量小于
1
0
4
10^4
104），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这
n
n
n 堆石子的数量，他想知道是否存在先手必胜的策略。
输入格式
本题有多组测试数据。
第一行一个整数
T
T
T （
T
≤
10
T\le10
T≤10），表示有
T
T
T 组数据
接下来每两行是一组数据，第一行一个整数
n
n
n，表示有
n
n
n 堆石子，
n
≤
1
0
4
n\le10^4
n≤104。
第二行有
n
n
n 个数，表示每一堆石子的数量.
输出格式
共
T
T
T 行，每行表示如果对于这组数据存在先手必胜策略则输出 Yes，否则输出 No。
样例输入
2
2
1 1
2
1 0
样例输出
No
Yes
思路分析：
对于尼姆博弈来说，关键在于计算所有堆中石子数目的二进制异或和（XOR）。 如果所有堆的石子数目异或和不为0，则先手玩家处于N态； 如果异或和为0，则先手玩家处于P态。 即当 n 堆石子的数量异或和等于 0 时，先手必败，否则先手必胜
为什么呢？用实际数字模拟来举个例子
通过这两个例子，我们可以直观地理解尼姆博弈中异或和的作用以及它对结果的影响。
附上题解code：
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
xor = 0
for i in range(n):
xor ^= a[i]
if xor == 0:
print("No")
else:
print("Yes")
反尼姆博弈（Anti - Nim）
[SHOI2008] 小约翰的游戏
题目描述
小约翰经常和他的哥哥玩一个非常有趣的游戏：桌子上有
n
n
n 堆石子，小约翰和他的哥哥轮流取石子，每个人取的时候，可以随意选择一堆石子，在这堆石子中取走任意多的石子，但不能一粒石子也不取，我们规定取到最后一粒石子的人算输。
小约翰相当固执，他坚持认为先取的人有很大的优势，所以他总是先取石子，而他的哥哥就聪明多了，他从来没有在游戏中犯过错误。小约翰一怒之前请你来做他的参谋。自然，你应该先写一个程序，预测一下谁将获得游戏的胜利。
输入格式
本题的输入由多组数据组成，第一行包括一个整数
T
T
T（
1
≤
T
≤
500
1 \leq T \leq 500
1≤T≤500），表示输入总共有
T
T
T 组数据。
每组数据的第一行包括一个整数
N
N
N（
1
≤
N
≤
50
1 \leq N \leq 50
1≤N≤50），表示共有
N
N
N 堆石子，接下来有
N
N
N 个不超过
5000
5000
5000 的整数，分别表示每堆石子的数目。
输出格式
对于每组数据，如果约翰能赢得比赛，则输出 John，否则输出 Brother，请注意单词的大小写。
样例输入
2
3
3 5 1
1
1
样例输出
John
Brother
提示
对于
40
%
40\%
40% 的数据，
T
≤
250
T \leq 250
T≤250；对于
100
%
100\%
100% 的数据，
T
≤
500
T \leq 500
T≤500。
和尼姆博弈的题面几乎一样，唯一的区别在于胜利条件： 在反尼姆博弈中，取走最后一个石子的玩家输掉比赛。 让我们从简单的情形入手：只有一堆且为1，无需多言，后手胜利 扩大堆数：但确保每一堆都是1，那么只需要判断奇偶性，奇数则先手败，偶数则后手败 扩大每堆的数量： 只有一堆不是1，其余堆都是1，那么先手可以选择拿完或留一个（给后手奇数个1的局面） 从而后手必败,先手必胜。 一般情况：任意堆石子>1，任意堆石子小于1 有点无从下手了，但我们可以发现： 随着石子数在减少,一定会有人面临只有一堆石子大于1的情况,那么他就必胜。 这就回到了Nim博弈的感觉了
请看code：
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
if sum(a) == n:
print("John") if n % 2 == 0 else print("Brother")
else:
xor = 0
for i in range(n):
xor ^= a[i]
if xor == 0:
print("Brother")
else:
print("John")
END
如果有更多问题或需要进一步的帮助，可以在评论区留言讨论哦！ 如果喜欢的话，请给博主点个关注 谢谢