2023-9-10 集合-Nim游戏

题目链接：集合-Nim游戏

#include 
#include 
#include 
#include 

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 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48