Nim博弈（简单）

Nim博弈（简单）

• 1.Mex函数
• 2.SG函数
• 3.解法
• 4.板子

1.Mex函数

设S表示一个非负整数集合.定义mex(S)为求出不属于集合S的最小非负整数运算,即:
mes(S)=min{x};
例如:S={0,1,2,4},那么mes(S)=3;

2.SG函数

所有x后继状态的mex
SG(x)=mex({SG(y1),SG(y2)····SG(yk)})

存在定理：
sg(x,y)=sg(x)^sg(y)
即：
一个局面拆分成了两个局面，由SG函数理论，多个独立局面的SG值，等于这些局面SG值的异或和。

3.解法

多个DAG图，对他们的初始状态求SG，连续^;
非零先手必胜，为零先手必败。

代码如下（示例）：

4.板子

#include
#include
#include
using namespace std;
const int N=2010,M=6010;
int h[N],e[M],ne[M],idx;
int n,m,k;
int f[N];
void add(int a,int b){
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}

int sg(int x){
    if(f[x]!=-1) return f[x];//记忆化
    unordered_set s;//哈希表，复杂度O(1)；用set复杂度O(log)
    for(int i=h[x];~i;i=ne[i]){//所有后继状态放入set
        s.insert(sg(e[i]));
    }
    //mex *** 作
    for(int i=0;;i++)//目标值不一定比N小，所以不加上限
    if(!s.count(i)) return f[x]=i;//找到第一个不存在的最小值
}
int main(){
    memset(h,-1,sizeof(h));
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    int ans=0;
    memset(f,-1,sizeof(f));//初始化为-1，方便记忆化搜索
    for(int i=1;i<=k;i++){//每堆石子的状态取^操作
        int x;
        cin>>x;
        ans^=sg(x);
    }
    if(ans)puts("win");
    else puts("lose");
}