AcWing 894. 拆分-Nim游戏
原题链接
简单
作者:
renyajie
,
2021-01-21 12:35:39
,
所有人可见
,
阅读 326
- 首先知道NIM游戏,先手的必胜态为异或和不为0,总能将异或和为0的局面给后手
- SG(i)相当于在有规则条件下,对于NIM游戏中每堆石子个数的抽象,先手必胜态转化为SG(i)的异或和不为0
- 在拆分条件下,每个局面变成多个子局面,难点在于如何整合子局面的SG值,由SG函数理论,多个独立局面的SG值,等于这些局面SG值的异或和
#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
const int N = 110;
int n;
int f[N];
int sg(int x)
{
if(f[x] != -1) return f[x];
unordered_set<int> num;
for(int i = 0; i < x; i++) // 根据题意计算SG值即可
{
for(int j = 0; j <= i; j++)
{
num.insert(sg(i) ^ sg(j)); // 多个独立局面的总SG=各独立的SG异或和
}
}
int res;
for(int i = 0;;i++)
{
if(!num.count(i))
{
res = i;
break;
}
}
return f[x] = res;
}
int main()
{
scanf("%d", &n);
memset(f, -1, sizeof f);
int res = 0;
for(int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
res ^= sg(x); // 计算每个局面的SG值
}
if(res) puts("Yes"); // 若异或结果不为0,先手总能将异或0的局面给后手,转化为NIM游戏,先手必胜
else puts("No");
return 0;
}