SG函数 nim游戏——集合

#include <iostream>
#include <cstring>
#include <algorithm>
#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 = 1; i <= k; i++) {
        if (x >= s[i]) 
            S.insert(sg(x - s[i]));
    }

    for (int i = 0; ; i++)
        if (!S.count(i))
            return f[x] = i;
}

int main() {
    cin >> k;
    for (int i = 1; i <= k; i++) cin >> s[i];
    cin >> n;

    memset(f, -1, sizeof(f));

    int res = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        res ^= sg(x);
    }

    if (res) puts("Yes");
    else puts("No");
    return 0;
}
上一篇:【Python】批量给图片增加水印工具


下一篇:Shell获取某个文件夹下的所有文件名(含文件夹)