算法博弈论（集合 Nim游戏）

作者: 奥迪汽车制造总厂董事
来源: 51数据库
2021-07-11

给定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

#include<cstring>
#include<algorithm>
#include<unordered_set>
#include<iostream>
using namespace std;
const int N=110,M=10010;

int n,m;
int s[N],f[M];//s储存石子的个数，f储存SG的值

int SG(int x)
{if(f[x]!=-1)
return f[x];//避免f[x]重复计算
unordered_set<int> S;
for(int i=0;i<m;i++)
{
    int sum=s[i];
    if(x>=sum)
    S.insert(SG(x-sum));
    
}
//寻找S集合之外的最小非负整数
for(int i=0;;i++)
if(!S.count(i))
return f[x]=i;
    
}

int main()
{
    cin>>m;
    for(int i=0;i<m;i++)
    cin>>s[i];
    cin>>n;
    int res=0;
    memset(f,-1,sizeof f);//因为SG（X）的值都是>0,可用-1表示这个数没有算过
    while(n--)
    {
        int x;
        cin>>x;
        res^=SG(x);
    }
    if(res)
    printf("Yes");
    else cout<<"No";
}