自助建站系统,七牛云建网站,网站做哪块简单,海南新闻最新消息给定 n 堆石子#xff0c;两位玩家轮流操作#xff0c;每次操作可以取走其中的一堆石子#xff0c;然后放入两堆规模更小的石子#xff08;新堆规模可以为 0 #xff0c;且两个新堆的石子总数可以大于取走的那堆石子数#xff09;#xff0c;最后无法进行操作的人视为失…给定 n 堆石子两位玩家轮流操作每次操作可以取走其中的一堆石子然后放入两堆规模更小的石子新堆规模可以为 0 且两个新堆的石子总数可以大于取走的那堆石子数最后无法进行操作的人视为失败。
问如果两人都采用最优策略先手是否必胜。
输入格式 第一行包含整数 n 。
第二行包含 n 个整数其中第 i 个整数表示第 i 堆石子的数量 ai 。
输出格式 如果先手方必胜则输出 Yes。
否则输出 No。
数据范围 1≤n,ai≤100 输入样例 2 2 3 输出样例 Yes
#include iostream
#include algorithm
#include cstring
#include unordered_setusing namespace std;const int N 110;
int n;
int f[N];//存i个状态的sg值int sg(int x)
{if(f[x] ! -1) return f[x];unordered_setint S; //哈希表存储每个局面可以到的局面//这个地方特别关键在集合的Nim游戏中我们可以明显的知道可以到的下一个状态是什么//比如(x - s[i])这道题里面需要遍历一下所有可能到达的状态并且异或起来for(int i 0; i x; i )for(int j 0; j i; j ) //用i和j表示分成的两个状态S.insert(sg(i) ^ sg(j));for(int i 0; ; i )if(!S.count(i))return f[x] i;
}int main ()
{cinn;memset(f, -1, sizeof f); // 记忆化搜索因为sg值都是自然数所以初始化成-1代表没有求过int res 0;while(n -- ){int x;cinx;res ^ sg(x);}if(res) puts(Yes);else puts(No);return 0;
}
