AcWing 893. 集合-Nim游戏
原题链接
简单
作者:
Drifter
,
2021-01-22 00:25:54
,
所有人可见
,
阅读 336
进阶 Day 6
#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
using namespace std;
const int N = 110, M = 10010;
int n, k;
int s[N], f[M];
int sg(int x)
{
if (f[x] != -1) return f[x];
unordered_set<int> S;
for (int i = 0; i < k; 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;
} //sg
int main(void)
{
scanf("%d", &k);
for (int i = 0; i < k; i++) scanf("%d", &s[i]);
scanf("%d", &n);
memset(f, -1, sizeof f);
int res = 0;
for (int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
res ^= sg(x);
}
if (res) puts("Yes");
else puts("No");
return 0;
}