acwing894. 拆分-Nim游戏

acwing894. 拆分-Nim游戏

原题链接：https://www.acwing.com/problem/content/896/

思路

关于SG函数，mex操作，SG定理的一些知识

取走一堆放入两堆，好像总的堆数一直在增加，但是每次放入的两堆各堆的数量一定小于取走的那一堆的数量，可能到最后每次放入的两堆的数量都是0，所以是有终点的。

此题将每一堆石子看成独立的局面

将每堆石子看做独立的局面，即\(a_1、a_2、a_3...a_n\)个有向图游戏。

然后求每个局面的SG函数，\(SG(a_1)、SG(a_2)、SG(a_3)...SG(a_n)\)，求其异或和

\(SG(a_1)\oplus SG(a_2)\oplus SG(a_3)\oplus ...\oplus SG(a_n)\neq 0\)则先手必胜
\(SG(a_1)\oplus SG(a_2)\oplus SG(a_3)\oplus ...\oplus SG(a_n)= 0\)则先手必败

对于每一个有向图\(a_1、a_2、a_3...a_n\)都存在如下情况：拿走\(a_k\)，增加了\(b_1、b_2\)两堆石子，根据SG定理，\(SG(a_k) = SG(b_1)\oplus SG(b_2)\)

代码

#include<iostream>
#include<cstring>
#include<unordered_set>

using namespace std;

const int N = 110;

int f[N],a[N];
int n;

int SG(int x)
{
    // 如果已经计算过SG函数值的直接返回
    if(f[x] != -1) return f[x];
    
    unordered_set<int> S; // 记录这个图x中的所有SG函数值
    
    // 遍历所有可能
    for(int i = 0; i < x; i ++)
        for(int j = 0; j <= i; j ++) // 这里可以取等，遍历到i就行，因为会有重复
            S.insert(SG(i)^SG(j));
    
    // mex
    for(int i = 0;; i ++)
    {
        if(!S.count(i)) return f[x] = i;
    }
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    
    memset(f,-1,sizeof f);
    
    int res = 0;
    for(int i = 0; i < n; i ++)
        res ^= SG(a[i]);
        
    if(res) puts("Yes");
    else puts("No");
    
    return 0;
}