题目
给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。
现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合 S,最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
输入格式
第一行包含整数 k,表示数字集合 S 中数字的个数。
第二行包含 k 个整数,其中第 i 个整数表示数字集合 S 中的第 i 个数 si。
第三行包含整数 n。
第四行包含 n 个整数,其中第 i 个整数表示第 i 堆石子的数量 hi。
输出格式
如果先手方必胜,则输出 Yes
。
否则,输出 No
。
数据范围
1≤n,k≤100,
1≤si,hi≤10000
输入样例:
2
2 5
3
2 4 7
输出样例:
Yes
思想
mex()函数mex({1,2,3})
输出集合中不存在的最小自然数,此时输出0
sg()函数,
最终状态,sg(终点)=0,必败态
下面这个图是一个演示过程,此时只有一堆石子,个数为10,每次只能取2或5,画出状态图
然后红颜色标注的为sg函数值 ,最终得出此时为必胜态
当有多堆石子时,只需求出每堆的sg值,并异或起来就是结果。若为0则为必败态,若为非0则为必胜态,证明与nim游戏相同
算法
#include<iostream>
#include<unordered_set>
#include<cstring>
using namespace std;
const int N = 110, M = 1e4 + 10;
int s[N], f[M]; //每次取石子的个数 石子堆的数量
int n, m;
int sg(int x)
{
if(f[x] != -1) return f[x];
unordered_set<int> S;
for(int i = 0; i < n; i ++)
{
int sum = s[i];
if(x >= sum)S.insert(sg(x - sum));
}
for(int i = 0; ; i ++)
if(!S.count(i))
return f[x] = i;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++)cin >> s[i];
cin >> m;
memset(f, -1, sizeof f);
int res = 0;
for(int i = 0; i < m; i ++)
{
int x;
cin >> x;
res ^= sg(x);
}
if(res)puts("Yes");
else puts("No");
return 0;
}