奥迪汽车制造总厂董事
给定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";
}
MEX，SG与胜败补充
SG入门介绍
