给定 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
输入样例：
1. 2 2. 2 5 3. 3 4. 2 4 7
输出样例：
Yes
补充：
mex运算
这是一个施加于集合的运算，表示求出这个集合中最小的没有出现过的非负整数，比如 m e x { 0 , 2 , 3 } = 1 , m e x { 1 , 2 } = 0 , m e x { } = 0 mex\{0,2,3\}=1,mex\{1,2\}=0,mex\{\}=0mex{0,2,3}=1,mex{1,2}=0,mex{}=0。
SG函数和定理
SG定理
你可能会问了，那么这些问题不是只需要一个bool数组来记录必胜或必败就可以了吗，为什么需要 SG 函数这么麻烦呢？
这时，我们就要请出SG 定理了：
一个游戏的SG 函数值等于各个游戏的 SG 函数值的Nim 和
其中，各个游戏指的是那个大的游戏中的子游戏，而Nim 和，其实也就是异或和。
思路：
计算每一堆石头的SG函数值，然后对循环res^=SG(i)，res=1必胜，否则必败
int sg(int x){ if(f[x]!=-1)return 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)); } for(int i=0;;i++) if(!S.count(i)) return f[x]=i; }
完整代码：
#include <iostream> using namespace std; #include <cstring> #include <unordered_set> #include <algorithm> const int N=110,M=10010; 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<m;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>>m; memset(f,-1,sizeof(f)); for(int i=0;i<m;i++)cin>>s[i]; int res=0; cin>>n; for(int i=0;i<n;i++) { int x; cin>>x; res^=sg(x); } if(res)cout<<"Yes"; else cout<<"No"; return 0; }
