AcWing 892. 台阶-Nim游戏
原题链接
简单
作者:
皓首不倦
,
2020-09-05 16:05:40
,
所有人可见
,
阅读 450
'''
把奇数位置台阶的石子堆当做一个经典的Nim游戏
假设计数堆的大小是a1, a3, a5 .... ak
如果a1 ^ a3 ^ a5 ...... ^ ak 是非0值,一定有一种方法,找一个奇数堆,拿掉一部分石子
放到它的下一级偶数台阶,让异或值变成0
同理,如果异或和是0,那不论玩家是从奇数堆拿还是从偶数堆拿,都必然会引起一个奇数堆的石子
数量变化,异或和必然变为非0值
只要奇数堆不是全0,那持有这个状态的玩家就是不败的,因为至少还有一个石子可以拿,根据上面
描述的状态转移方式,持有不败局的玩家一定至少有一种方式保持自己下一次还是获得不败局,因此
这个问题的必胜或者必败性质和奇数堆组成的经典Nim问题是一致的
'''
n = int(input())
arr = list(map(int, input().split()))
xor_val = 0
for i in range(0, n, 2):
xor_val ^= arr[i]
print('Yes' if xor_val != 0 else 'No')