poj2311

　　博弈论——sg，mex

sg性质：1.在末态的状态点为N态。

　　　　 2.P态的下一步有一个是N态

　　　　 3.N态的下一步全部是P态。

当然这是对于单点一个游戏的情形，也相当于NIM只有一堆石子。

 

mex(minimal excludant)，很俗地可以解释为：mex{S}表示S集合中从0开始，最小未出现的数字。

 

关于sg与mex的关系，可以引用这里http://www.cnblogs.com/Knuth/archive/2009/09/05/1561007.html的一段话：

对于一个给定的有向无环图，定义关于图的每个顶点的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。

以上这三句话表明，顶点x所代表的postion是P-position当且仅当g(x)=0（跟P-positioin/N-position的定义的那三句话是完全对应的）。

 

关于sg叠加的效果，很神奇发现它们满足sg(G) = sg(G1)^sg(G2)^……^sg(Gn)。对于与博弈有关的核心就是这些了。多刷刷题，自然心里就明了了。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int sg[210][210];
int stamp[210*210]={0},stamps=1;
int sgx(int r,int c){
    stamps++;
    for(int i=2;i<=r-i;i++)  // 1 c（只有一行）【r-1 c】 不能被继续，故需要从2开始。
        stamp[sg[i][c]^sg[r-i][c]] = stamps;
    for(int i=2;i<=c-i;i++)
        stamp[sg[r][i]^sg[r][c-i]] = stamps;
    for(int i=0;;i++)
    if(stamp[i] < stamps)
    {
        sg[r][c] = i;
        break;
    }
    return sg[r][c];
}
int main()
{
    for(int i=1;i<210;i++)
        sg[1][i] = sg[i][1] = 1;

    for(int i=2;i<210;i++)
      for(int j=i;j<210;j++)
        sg[i][j] = sg[j][i] = sgx(i,j);
    int n,m;
    while(scanf("%d%d",&n,&m) != EOF){
        if(sg[n][m]) printf("WIN\n");
        else printf("LOSE\n");
    }
    return 0;
}