摘要
Title: 891. Nim游戏
Tag: 博弈论
Memory Limit: 64 MB
Time Limit: 1000 ms

891. Nim游戏

题意

给定 n堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
思路
1. 终止状态，也就是必败态，是 $a_1 \oplus a_2 ...\oplus a_n= 0$
2. 如果当前异或值不是0，那么一定可以通过某种方式，使得拿完之后的异或值变成0
  1. 即拿 $a_i-(x \oplus a_i)$ 个， $x = a_1 \oplus a_2 ... \oplus a_n$ ，这样那一堆石子就剩 $x \oplus a_i$ 个，这样所有的异或值就为0了
  2. 为什么 $x \oplus a_i$ $x \oplus a_{i}$ 一定小于x呢?
    1. 一定存在一个 $a_i$ 使得满足 $x \oplus a_i$ 小于 $a_i$
    2. 假设：x（用二进制表示）最高位是第 $k$ 位，此时只需要找一个第 $k$ 位同样为 $1$ 的 $a_i$ 即可，这样他俩异或后，第 $k$ 位一定变成0，一定会比 $a_i$ 小，这样找到的 $a_i$ 一定满足上述条件
3. 如果当前的异或值是0，那么不管怎么拿，拿完之后的异或值一定不是0

代码

'''
Author: NEFU AB-IN
Date: 2023-03-21 10:19:25
FilePath: \Acwing\891\891.py
LastEditTime: 2023-03-21 10:22:32
'''
read = lambda: map(int, input().split())
from collections import Counter, deque
from heapq import heappop, heappush
from itertools import permutations

N = int(1e3 + 10)
INF = int(2e9)

n = int(input())
lst = list(read())

res = 0
for i in lst:
    res ^= i

print("Yes" if res != 0 else "No")

891. Nim游戏

题意

思路

代码