[数据结构与算法]【算法小结】Mex，SG，集合-Nim游戏模型

“ Ctrl AC！一起 AC！”

Mex运算：

定义Mex(S)表示不属于集合S的最小非负整数。

SG函数：

在有向图游戏（先手从起点出发，到达某点，接力给后手操作，轮流进行，谁操作后到达终点谁赢）中，对于每个结点x出发共有k条有向边，分别到达结点y1，y2 ... yk，

定义SG(x)表示y1到yk的SG值构成的集合进行Mex运算后的结果：

SG(x)=mex{SG(y1),...,SG(yk)}

特别地

· 整个有向图(G)游戏的SG值定义为有向图起点s的SG值：

SG(G)=SG(s)

· 终点的SG值定义为零。

定理：

有向图游戏的某个局面先手必胜，当且仅当SG(起点)不等于零。

若有多个图：

则当 SG(起点1) ^ SG(起点2) ^ ... ^ SG(起点n) ！= 0 时，先手必胜

集合-Nim游戏模型：

#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 10010;
int n, m;
int s[N], f[M];
int sg(int x)
{
    if(f[x] != -1)  return f[x];
    
    unordered_set<int> st;
    for(int i = 0; i < m; ++i)
    {
        int t = s[i];
        if(x >= t)  st.insert(sg(x - t));
    }
    
    for(int i = 0; ; ++i)
        if(!st.count(i))
            return f[x] = i;
}

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

感谢阅读！！！

“ Ctrl AC！一起 AC！”