给定n堆物品,第i堆物品有A[i]个。两名玩家轮流行动,每次可以任选一堆,取走任意多个物品,可以一堆取完,但不能不取。取走最后一件物品者获胜。两人都采取最优策略,问先手能否必胜。
↑↑↑被称为NIM游戏
NIM博弈定理
NIM博弈先手必胜,当且仅当A1xorA2xor···xorAn不为0。
证明(省略)
代码
#include<cstdio>
using namespace std;
const int sz=1e5+1;
int n,i,a[sz],s;
int main()
{
scanf("%d",&n);
for(i=1;i<=n;++i)scanf("%d",&a[i]),s^=a[i];
printf("%s",s?"Yes":"No");
return 0;
}