牛客 - A Simple Game(尼姆博弈变形)

题目链接：点击查看

题目大意：给出 n 个 01 字符串，两个人轮流进行游戏，每次可以选择任意数量的字符串，进行下列操作之一（每个字符串进行的操作可以不同）：

选择一个字符串，使得其中的一个 ' 1 ' 变为 ' 0 ' ， 如 10000 -> 00000

选择一个字符串，使得其中连续的，数量大于 2 的 ' 0 ' 变为一个 ' 1 ' ，如 10000 -> 11

无法操作的一方输

题目分析：需要转换题意，首先仔细观察后可以发现，操作 1 和操作 2 的共同特点是，可以改变 ‘ 1 ’ 数量的奇偶性，因为操作 1 是减少一个 1 ，而操作 2 是增加一个 1 ，最后输的局面是 n 个字符串都是 0 ，这样一来，我们就参照尼姆博弈的思想，不难想到当 n 个字符串中 ' 1 ' 的个数都为偶数时为必败态，因为此时你如何操作，对手只需要模仿你进行相同的操作就行，这样无论你如何操作，对手都会进行最后一次操作，相反，如果不是必败态时，完全可以先手将奇数的字符串都更改为偶数的字符串，从而形成必败态

代码：
 

#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> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;char s[N];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);bool flag=true;while(n--){scanf("%s",s);if(count(s,s+strlen(s),'1')&1)flag=false;}if(flag)puts("kgNB");elseputs("sdzNB");}return 0; }

 

总结

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

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