目录

1.小明的游戏1（尼姆博弈）

2.小明的游戏5（ 威佐夫游戏）

3.巴什游戏

4.石子游戏

1.小明的游戏1（尼姆博弈）

题目描述

蓝桥公司给他们的员工准备了丰厚的奖金，公司主管小明并不希望发太多的奖金，他想把奖金留给智慧的人，于是他决定跟每一个员工玩一个游戏，规则如下：

• 桌面上一共有 n 堆一元钱。
• 双方轮流行动，由小明先行动，每次行动从某一堆钱中拿走若干元（至少一元钱），取走最后一元钱的人获胜。

请问员工们能拿到奖金吗？

输入描述

第一行为一个整数 T，表示测试数据数量。

每个测试用例包含俩行。第一行为一个整数 n ， 第二行包括 n 个整数 a1​,a2​...an​ 表示第 i 堆有 ai​ 元。

1≤T,n≤10^5,1≤ai​≤10^9 。

保证所有测试用例的 n 的和不超过 2×10^5。

输出描述

如果员工能拿到奖金输出 YES​ ， 否则输出 NO。

输入输出样例

示例 1

输入

321 11132 2 1

输出

YESNONO

定理：

• 若 a1​⊕a2​⊕⋯⊕an​!=0，先手必胜，记此时的状态为N-position
• 若 a1​⊕a2​⊕⋯⊕an​=0，先手必败，记此时的状态为P-position

（⊕ 表示异或运算）

T = int(input())while T > 0:    n = int(input())    ans = 0    a = list(map(int, input().split()))    for i in range(n): ans ^= a[i]    if ans!=0:print('NO')    else:print('Yes')    print()    T-=1

2.小明的游戏5（ 威佐夫游戏）

 题目描述

蓝桥公司给他们的员工准备了丰厚的奖金，公司主管小明并不希望发太多的奖金，他想把奖金留给智慧的人，于是他决定跟每一个员工玩一个游戏，规则如下：

• 桌面上一共俩堆钱分别为 a 元和 b 元。

• 双方轮流行动，由小明先行动，每次行动可以从任意一堆拿任意元，或者从俩堆拿相同的任意元。取走最后一元钱的人获胜。

请问员工们能拿到奖金吗？

输入描述

第一行为一个整数 T，表示测试数据数量。 (1≤T≤105)

每个测试用例包含一行。每行为俩个整数 a 和 b 。（1≤a,b≤10^18）分析两堆石子的数量(a,b)，使先手必输的局势有：(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9, 15)等等，称这些局势为“奇异局势”。通过观察不难发现，奇异局势有两个特征：

1. 差值是递增的，分别是 0, 1, 2, 3, 4, ；
2. 每个局势的第一个值是未在前面出现过的最小的自然数。
3. 推导奇异局势时，用到的黄金分割数需要较高的精度，直接用 1.618 这个估值是不行的。在代码中用公式计算高精度黄金分割数

：double gold = (1 + sqrt(5))/2;

输出描述

如果员工能拿到奖金输出 YES ， 否则输出 NO。

输入输出样例

示例 1

输入

32 18 44 7

输出

YESNOYES

知识点总结

威佐夫博弈是指的这样一个问题：有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。

假设两堆石子为(x,y)（其中x<y）

那么先手必败，当且仅当（y-x）*(1 + sqrt(5))/2=x

t = int(input())for i in range(1 , t + 1):  a,b = map(int,input().split())  c = ((5(0.5)) + 1) / 2  if a > b:      a,b = b,a  if int((b-a)*c) == a:      print("YES")  else:      print("NO")

3.巴什游戏

• 题目描述：有 n 颗石子，甲先取，乙后取，每次可以拿 1∼m 颗石子，轮流拿下去，拿最后一颗的获胜。
• 输入：n和 m，1≤n,m≤1000。
• 输出：如果先拿的甲赢了，输出“first”，否则输出“second”。 

1. n≤m 时，由于一次最少拿 1 个，最多拿 m 个，甲可以一次拿完，先手赢。
2. n = m+1 时，无论甲拿走多少个（1∼m 个），剩下的都多于 1 个、少于等于 m 个，乙都能一次拿走剩余的石子，后手取胜。
3. 如果 n % (m+1) = 0，即 n是 m+1 的整数倍，那么不管甲拿多少，例如 k 个，乙都拿 m+1-k 个，使得剩下的永远是 m+1 的整数倍，直到最后的 m+1 个，所以后拿的乙一定赢。
4. 如果 n % (m+1) != 0，即 n 不是 m+1 的整数倍，还有余数 r，那么甲拿走 r 个，剩下的是 m+1 的倍数，相当于甲、乙互换，结果是甲赢。

n,m=map(int,input().split())if n%(m+1)==0:     print('second')else:     print('first')

4.石子游戏

题目描述

两人玩游戏，游戏内容为下：

有 n 个石头，两人每次可以从这 n 个石头中取 p^k 个（p 是任意质数，k 是任意自然数，p^k 要求不大于当前剩余石头数），谁能取走最后石头，谁就获胜了。

问先手取石头的人，有没有必胜的策略。如果先手有，则输出 first，否则输出 second。

输入描述

输入第一行包含一个正整数 T，表示测试数量。

接下来后面T 行，每行包含一个正整数 n，表示石头个数。

1≤T≤10^5,1≤n≤10^6。

输出描述

输出共 T 行，每行分别为 first 或 second。

样例输入

3369

样例输出

firstsecondfirst

• 如果 n是 6 的倍数，第二人赢。
• 如果 n 不是 6 的倍数，第一人拿走 1∼5 个石头后，使得剩下数量的是 6 的倍数，那么第 1 人就赢了。

T=int(input())while T>0:    n=int(input())    if n%6 : print("first")    else: print("second")    T-=1