题意:Nim博弈(我明明记得Nim博弈不是这样的,逃)
思路:看了几篇关于sg函数的博客,感觉不错的我已经在博弈整理的博客中整理出来的(还在整理,毕竟快退役狗刚接触),看了洛谷上的几篇题解,可能是我思考的太简单了???? 我们知道通过SG函数的原理,我们可以把一个游戏拆分成x个相互独立的游戏,这些游戏可以互不相同,但最后的结果的SG函数是等于这x个不同子问题的SG函数的异或和,那这样的话我们知道,对于单独的一堆石子,除非等于0的时候,先手必败也就是P位置,其他的情况都是先手必胜,即N位置,那n个棋子时的SG函数就等于n,所以我们直接异或n堆石子就可以了
代码:
#includeusing namespace std;typedef long long LL;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int main(){ int T=read(); while(T--){ int n=read(); int ans=0; for(int i=1;i<=n;i++){ int x=read(); ans^=x; } if(ans)puts("Yes"); else puts("No"); } return 0;}