2023-9-10 集合-Nim游戏

题目链接：集合-Nim游戏

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 110, M = 10010;

int n, m;
int s[N], f[M];

int sg(int x)
{
    if(f[x] != -1) return f[x];
    // 集合S存储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;
    for(int i = 0; i < m; i++) cin >> s[i];
    
    memset(f, -1, sizeof f);
    
    cin >> n;
    int res = 0;
    while(n--)
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }
    if(res) cout << "Yes" << endl;
    else cout << "No" << endl;
    
    return 0;
}