HDU - 1907 John(尼姆博弈变形)

题目链接：点击查看

题目大意：给出 n 堆石子，两个人轮流取，至少取一个，取到最后一个的人输

题目分析：尼姆博弈是取到最后一个的人获胜，这个题正好反着

一个很显然的奇异局势就是，每一堆的石子的个数都为 1 且有偶数堆石子，此时对应着异或和为 0

然后分两种情况讨论：

只有一堆石子的个数大于 1 ：此时先手总是可以通过操作使得石子堆数为奇数且每堆只有一个石子

有超过一堆石子数大于 1 时：可以先手将异或和变为 0

代码：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n;scanf("%d",&n);int _xor=0;bool flag=false;for(int i=1;i<=n;i++){int num;scanf("%d",&num);_xor^=num;if(num>1)flag=true;}if(_xor&&flag||!flag&&!_xor)puts("John");elseputs("Brother");}return 0; }

 

总结

以上是生活随笔为你收集整理的HDU - 1907 John(尼姆博弈变形)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。