AcWing 893. 集合-Nim游戏(Python)
原题链接
简单
作者:
习学学
,
2021-01-17 18:22:22
,
所有人可见
,
阅读 317
Python 代码
k = int(input())
takes = list(map(int, input().split()))
n = int(input())
stones = list(map(int, input().split()))
labels = [-1] * (10010) # 用于标记当前节点的sg值
def sg(x):
if labels[x] != -1: return labels[x]
connect = set() # 用于记录连接的sg值
for t in takes:
if x - t >= 0: connect.add(sg(x - t))
i = 0
while True:
if i not in connect:
labels[x] = i
break
i += 1
return labels[x]
res = 0
for s in stones:
res ^= sg(s)
if res == 0: print('No')
else: print('Yes')