sg函数的应用

　　刚刚接触到sg函数突然感觉到原来可以这么好用，sg函数应该算是博弈论中比较经典的东西了。下面来说说sg函数：

　　从网上搜集资料终于能看懂了下面解释来自http://www.cnblogs.com/cj695/archive/2012/07/31/2617378.html，自己写不出来收藏了大神的思想。

　　 他几乎可以解决博弈论中的所有问题。你可以将sg函数看作是一个深搜的的过程。而每一堆的石子就相当于图中间的节点。所以说整个sg函数的过程就是在对一个有向无环图进行dfs的过程。

sg函数的具体内容可以用一个公式来表示（虽然我最不喜欢公式，不过我还是得写。不然这没法说清楚）：

sg(x) =mex{sg(y) : y ∈ F(x)}。其中｛｝内的是一个集合（只要上过高中都应该知道吧），在：右边的是该集合元素所满足的条件。sg（y）为该元素的值（其实就是一个递归的过程），F（x）貌似是该状态可以达到的状态。重点来了。。mex（）函数表示是不在该集合中的最小的非负整数的值。比如mex({1,2,3})=0...mex({0,2,4})=1...mex({})=0..最后得出来的结果中。为0为必败点，不为零必胜点。。

接下来才是sg函数精妙之处了。假如说是在一个游戏中有多个石子堆该怎么办了。我们只需要把对每个石子堆进行sg函数的调用，将得到的所有的值进行异或。得出来的结果为0则该情形为必败态。否则为必胜态。。

此处贴上sg的一个模板：

int sg[N];

bool hash[N];

void sg_solve(int *s,int t,int N)   //N求解范围代表一堆石子中的个数 S[]数组是可以每次取的值，t是s的长度。

{

    int i,j;

    memset(sg,,sizeof(sg));

    for(i=;i<=N;i++)               //枚举石子的个数

    {

        memset(hash,,sizeof(hash));

        for(j=;j<t;j++)

            if(i - s[j] >= )      //枚举每次拿走的个数并标记

                hash[sg[i-s[j]]] = ;

        for(j=;j<=N;j++)

            if(!hash[j])

                break;

        sg[i] = j;  　　　　　　　　　//找到这个F[](该状态可以达到的状态)中不存在的最小的数

    }

}  

下面写一个模板的应用：

　题意：
是有１堆石子，两个人轮流从其中一堆拿，每次只能从一堆拿，可以拿任意个（大于０），也可以把一堆石子分成三堆（每堆大于０），问谁先赢。

void st()

{

     int i,j,k;

     sg[0]=0;

     for(i=1;i<100;i++)

     {

         memset(vis,0,sizeof(vis));

         for(j=0;j<i;j++)

             vis[sg[i-j]]=1;

         if(i>=3)

         {

             for(j=1;j<i-2;j++)

               for(k=1;k<i-2;k++)

                     if(j+k<i)

                        vis[sg[j]^sg[k]^sg[i-k-j]]=1;

         }

         j=0;

         while(vis[j]) j++;

         sg[i]=j;

         printf("%d\n",sg[i]);

     }

}