AcWing 893. 集合-Nim游戏
原题链接
简单
作者:
Value
,
2020-05-24 19:26:54
,
所有人可见
,
阅读 509
#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;
const int N = 110;
int s[N], f[10010];
int k;
int sg(int t){
if(f[t] != -1) return f[t];
unordered_set<int> Set;
for(int i = 0; i < k; i ++ ){
if(s[i] <= t) Set.insert(sg(t - s[i]));
}
for(int i = 0; ; i ++ ){
if(!Set.count(i)){
return f[t] = i;
}
}
}
int main(){
memset(f, -1, sizeof f);
cin >> k;
for(int i = 0; i < k; i ++ ){
cin >> s[i];
}
int n;
cin >> n;
int res = 0;
int num;
for(int i = 0; i < n; i ++ ){
cin >> num;
res ^= sg(num);
}
if(res) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}