拆分-Nim游戏

题意一定要读懂😭

题目是说把这堆石子全部拿走后再另外放两堆石子进来，而不是说把这堆全部拿走然后分成两堆放入已有的石子中

关键：

• 把每一种划分情况看成一个整体，比如ai拆成bi和bj,那么这种情况就只有一个sg值，sg值就是sg(bi)^sg(bj)
• 遍历所有划分情况可以用下面的代码，为了避免重复规定bi>=bj,那么有ai>bi>=bj

for (int i = 0; i < x; i ++){
    for (int j = 0; j <= i; j ++){

#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;

int n, num, res;
int f[110];

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

int main(){
    memset(f, -1, sizeof(f));
    cin >> n;
    while (n --){
        cin >> num;
        res ^= sg(num);
    }
    puts(res ? "Yes" : "No");

    return 0;
}