1.题目基本信息
1.1.题目描述
Alice 和 Bob 交替进行一个游戏，由 Alice 先手。
在游戏中，共有 n 堆石头。在每个玩家的回合中，玩家需要 选择 任一非空石头堆，从中移除任意 非零 数量的石头。如果不能移除任意的石头，就输掉游戏，同时另一人获胜。
给定一个整数数组 piles ，piles[i] 为 第 i 堆石头的数量，如果 Alice 能获胜返回 true ，反之返回 false 。
Alice 和 Bob 都会采取 最优策略 。
1.2.题目地址
https://leetcode.cn/problems/game-of-nim/description/
2.解题方法
2.1.解题思路
SG函数 / 记忆化搜索 / 公式
2.2.解题步骤
公式证明：
命题：如果nim游戏先手选择时的石子堆数为[a1,a2,...,an]，如果x=a1^a2^...^an=0，则先手必败，如果x!=0，则必胜
证明1（x!=0，则先手必胜）：
- 假设当前的状态x=a1^a2^...^an，设x的二进制最高位为k，那么一定存在一个ai，其二进制的第k位为1，由异或的运算规律可知，ai^x<ai（ai^x的最高位被异或没了，但是ai二进制最高位还在），现在从ai中挑选出若干个，使ai变成ai^x，此时的x=a1^a2^...^ai^x^...^an=0（异或的交换律），所以一定存在一个选择方式，使后手处于必败态（即x==0）
证明2：（x==0，则后手必败）（反证）
- 假设当前的状态x=a1^a2^...^an=0，假设存在一个选择方法，使ai变成bi（ai>bi），且x2=a1^a2^...^bi^...^an=0；则x^x2=ai^bi=0，即ai==bi，这和ai>bi假设冲突，所以推翻假设，即不存在一个选择方法，使选择后的x!=0，得证
3.解题代码
python代码
# 功能：求集合st第一个不存在的自然数
def mex(st:set) -> int:
i = 0
while i in st:
i += 1
return i
# 功能：记忆化搜索计算sg值
memo = {}
def sg(x:int) -> int:
if x not in memo:
# 1.子游戏中递归出口
if x == 0:
return 0
# 2.子游戏中x状态的下一个状态的sg值集合
st = set()
for i in range(x):
st.add(sg(i))
memo[x] = mex(st)
return memo[x]
class Solution:
def nimGame(self, piles: List[int]) -> bool:
# 思路：SG函数
result = 0
for pile in piles:
result ^= sg(pile)
return result != 0
def nimGame1(self, piles: List[int]) -> bool:
# 思路：公式
ans = 0
for num in piles:
ans ^= num
return ans != 0
4.执行结果
