2023-9-11 拆分-Nim游戏

题目链接：拆分-Nim游戏

#include 
#include 
#include 
#include 

using namespace std;

const int N = 110;

int f[N];

int sg(int x)
{
    if(f[x] != -1) return f[x];
    
    unordered_set S;
    for(int i = 0; i < x; i ++)
        for(int j = 0; j <= i; j ++)
            S.insert(sg(i) ^ sg(j));
        
        for(int i = 0; ; i ++)
            if(!S.count(i))
                return f[x] = i;
}   

int main()
{
    int n;
    int res = 0;
    cin >> n;
    memset(f, -1, sizeof f);
    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