题目描述
blablabla
算法1
1.SG(x1) ^ SG(x2) ^ … ^ SG(xn) != 0 –> 必胜状态;
2.SG(x1) ^ SG(x2) ^ … ^ SG(xn) == 0 –> 必败状态;
其中SG[xi]是指每一个图的初始状态SG函数值;
可以把每堆石子看成一副图;
求SG(xi)的时候用到了记忆化搜索,搜索的形式加动规的思想:可以保存搜索过的状态,同时还可以剪枝,不必遍历所有的状态;f[N]用来存储某个状态是否已经被计算过,搜索时dfs;
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>
using namespace std;
const int N =110, M = 10010;
int s[N], f[M];//f[M]用来存储已经算过的状态,没算过的为-1;
int k, n;
int sg(int n)
{
if (f[n] != -1) return f[n];
unordered_set<int> S;//对于每一个状态,存储它所能到的下一个状态的sg函数值,S是不断更新的,因为在不停的定义新的S;
for(int i = 0; i < k; i ++)
{
int sum = s[i];
if (sum <= n) S.insert(sg(n - sum));
}
//因为计算sg函数值,要用到子状态的结果,所以先递归,在求当前状态的sg函数值;
for (int i = 0; ; i ++)
{
if (!S.count(i))
return f[n] = i;
}
}
int main()
{
memset(f, -1, sizeof f);
cin >> k;
for (int i = 0; i < k; i ++) cin >> s[i];
cin >> n;
int res = 0;
while(n --)
{
int x;
cin >> x;
res ^= sg(x);//求所有初始状态的异或;
}
if (res) puts("Yes");
else puts("No");
return 0;
}
y总 S.count()那个函数不明白,就是回溯的时候计算sg函数的值