蓝桥杯练习题——博弈论-集合-Nim游戏

思路

如果 SG(x1) ^ SG(x2) ^ SG(x3) ^ … ^ SG(xn) = 0，先手必败

能到 0 那就是 1，能到 1 那就是 0，同时能到 1 和 0，那就是 2

#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
const int N = 110, M = 1e4 + 10;
int a[N], b[M];
int n, m;

int sg(int x){
    if(b[x] != -1) return b[x];
    unordered_set<int> s;
    for(int i = 0; i < n; i++){
        int t = a[i];
        if(x >= t) s.insert(sg(x - t));
    }
    for(int i = 0; ; i++){
        if(!s.count(i)){
            b[x] = i;
            return b[x];
        }
    }
}

int main(){
    memset(b, -1, sizeof(b));
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    int res = 0, x;
    for(int i = 0; i < m; i++){
        scanf("%d", &x);
        res ^= sg(x);
    }
    if(res) printf("Yes\n");
    else printf("No\n");
    return 0;
}