博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
洛谷 P2197 【模板】nim游戏
阅读量:5074 次
发布时间:2019-06-12

本文共 825 字,大约阅读时间需要 2 分钟。

题意:Nim博弈(我明明记得Nim博弈不是这样的,逃)

思路:看了几篇关于sg函数的博客,感觉不错的我已经在博弈整理的博客中整理出来的(还在整理,毕竟快退役狗刚接触),看了洛谷上的几篇题解,可能是我思考的太简单了???? 我们知道通过SG函数的原理,我们可以把一个游戏拆分成x个相互独立的游戏,这些游戏可以互不相同,但最后的结果的SG函数是等于这x个不同子问题的SG函数的异或和,那这样的话我们知道,对于单独的一堆石子,除非等于0的时候,先手必败也就是P位置,其他的情况都是先手必胜,即N位置,那n个棋子时的SG函数就等于n,所以我们直接异或n堆石子就可以了

代码:

#include
using 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;}

 

转载于:https://www.cnblogs.com/lalalatianlalu/p/9857045.html

你可能感兴趣的文章