(模板)SG函数小结

说是小结,其实我并没有怎么弄懂QAQ,简单写写概念跟板子吧…

Sprague-Grundy函数

给定一个有向无环图和一个起始顶点上的一枚棋子,两名选手交替的将这枚棋子沿有向边进行移动,无法移动者判负。事实上,这个游戏可以认为是所有Impartial Combinatorial Games的抽象模型。也就是说,任何一个ICG都可以通过把每个局面看成一个顶点,对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。

基本概念

下面我们就在有向无环图的顶点上定义Sprague-Garundy函数。 首先定义$mex$(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如$mex[0,1,2,4]=3,mex[2,3,5]=0,mex[]=0$。 对于一个给定的有向无环图,定义关于图的每个顶点的Sprague-Garundy函数$g$如下:$g(x)=mex[ g(y) | y是x的后继 ]$。

SG函数的性质

首先,所有的terminal position所对应的顶点,也就是没有出边的顶点,其SG值为0,因为它的后继集合是空集。 对于一个g(x)=0的顶点x,它的所有后继y都满足g(y)!=0。 对于一个g(x)!=0的顶点,必定存在一个后继y满足g(y)=0。 P 以上这三句话表明,顶点x所代表的postion是P-position当且仅当g(x)=0(跟P-positioin/N-position的定义的那三句话是完全对应的)。我们通过计算有向无环图的每个顶点的SG值,就可以对每种局面找到必胜策略了。 我们可以定义有向图游戏的和(Sum of Graph Games):设G1、G2、……、Gn是n个有向图游戏,定义游戏G是G1、G2、……、Gn的和(Sum),游戏G的移动规则是:任选一个子游戏Gi并移动上面的棋子。Sprague-Grundy Theorem就是:g(G)=g(G1)^g(G2)^…^g(Gn)。也就是说,游戏的和的SG函数值是它的所有子游戏的SG函数值的异或。 再考虑一个性质:任何一个ICG都可以抽象成一个有向图游戏。所以“SG函数”和“游戏的和”的概念就不是局限于有向图游戏。我们给每个ICG的每个position定义SG值,也可以定义n个ICG的和。所以说当我们面对由n个游戏组合成的一个游戏时,只需对于每个游戏找出求它的每个局面的SG值的方法,就可以把这些SG值全部看成Nim的石子堆,然后依照找Nim的必胜策略的方法来找这个游戏的必胜策略了!(Nim其实就是n个从一堆中拿石子的游戏求SG的变型,总SG=n个sg的异或)。

模板

1.把原游戏分解成多个独立的子游戏,则原游戏的SG函数值是它的所有子游戏的SG函数值的异或。

即$sg(G)=sg(G1)\oplus sg(G2)\oplus …\oplus sg(Gn)$。

2.分别考虑没一个子游戏,计算其SG值。

1.可选步数为1~m的连续整数,直接取模即可,$SG(x) = x \ mod\ (m+1)$; 2.可选步数为任意步,$SG(x) = x$; 3.可选步数为一系列不连续的数,用模板计算。 模板1:打表

#include<bits/stdc++.h>
using namespace std;
//f[]:可以取走的石子个数
//sg[]:0~n的SG函数值
//Mex[]:mex{}
int f[N],sg[N],Mex[N];
void getSG(int n) 
{
    int i, j;
    memset(sg, 0, sizeof(sg));
    for (i = 1; i <= n; i++) {
        memset(Mex, 0, sizeof(Mex));
        for (j = 1; f[j] <= i; j++)
            Mex[sg[i - f[j]]] = 1;
        for (j = 0; j <= n; j++)    //求mes{}中未出现的最小的非负整数
        {
            if (Mex[j] == 0) {
                sg[i] = j;
                break;
            }
        }
    }
}

模板2:dfs

//注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍
//n是集合s的大小 S[i]是定义的特殊取法规则的数组
int s[110],sg[10010],n;
int SG_dfs(int x)
{
    int i;
    if(sg[x]!=-1)
        return sg[x];
    bool vis[110];//bool数组一定要放在里面
    memset(vis,0,sizeof(vis));
    for(i=0;i<n;i++)
    {
        if(x>=s[i])
        {
            SG_dfs(x-s[i]);
            vis[sg[x-s[i]]]=1;
        }
    }
    int e;
    for(i=0;;i++)
        if(!vis[i])
        {
            e=i;
            break;
        }
    return sg[x]=e;
}

一般DFS只在打表解决不了的情况下用,首选打表预处理。 还有一种dfs,题目给出的不是移动次数,而是可以移动的操作,类似于给定一幅有向图,知道下一步有哪些操作是可选的(参见HDU1524)

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
vector<int>G[1005];
int sg[1005];
int dfs(int x)
{
    if(sg[x]!=-1)
        return sg[x];
    bool vis[1005]={false};
    for(int i=0;i<G[x].size();i++){
        vis[dfs(G[x][i])]=true;
    }
    for(int i=0;;i++)
        if(!vis[i])
            return sg[x]=i;
}
int main()
{
    int n,i,j,k,x,m;
    while(cin>>n){
        for(i=0;i<=1000;i++)G[i].clear();
        memset(sg,-1,sizeof(sg));
        for(i=0;i<n;i++){
            scanf("%d",&x);
            while(x--){
                scanf("%d",&j);
                G[i].push_back(j);//加边,下一步可以做的操作
            }
        }
        while(scanf("%d",&m)&&m){
            int ans=0;
            for(i=0;i<m;i++){
                scanf("%d",&j);
                if(sg[j]!=-1)
                    ans^=sg[j];
                else ans^=dfs(j);
            }
            if(ans)puts("WIN");
            else puts("LOSE");
        }
    }

    return 0;
}

3.计算$sg(G)=sg(G1)\oplus sg(G2)\oplus …\oplus sg(Gn)$,若$sg(G)=0$,即P-Position,即先手比败。