给定 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<iostream>
#include<algorithm>
#include<unordered_set>
#include<cstring>
using namespace std;const int N = 110, M = 10010;int s[N],f[M]; //s用来存储数字集合,f用来存储各状态的sg
int n,m;int sg(int num)
{//如果当前这个数的sg不为-1,说明已被计算过,则直接返回if(f[num]!=-1) return f[num];//定义哈希表,防止出现重复的数字unordered_set<int> S;//对该堆石子进行判断,是否可以拿取集合内的数量的石子,若可以,则将拿去后的状态进行sg(即剩余石子的数量)for(int i=0;i<n;i++) if(num>=s[i]) S.insert(sg(num-s[i]));//对哈希表进行查找,每次将不存在集合中的最小的自然数赋予f[num](即Mex运算),并返回f[num];for(int i=0; ;i++) if(!S.count(i)) return f[num] = i;
}int main()
{cin>>n;for(int i=0;i<n;i++) cin>>s[i];memset(f,-1,sizeof f); //初始化f数组,每个值均为-1int res = 0;cin>>m;//若起点的sg(即初始石子堆的sg)均不为0,则先手必胜//设终点的sg为0,若起点的sg不为0,则可以进行一系列的操作后到0,在这一系列操作中有到0的,有不到0的,不到0的就是获胜的操作//若起点为0,0是最小的自然数,由Mex运算可知,0无法通过任何操作变成非零数,即这就是先手必败for(int i=0;i<m;i++){int num;cin>>num;res^=sg(num);}if(res) cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}