博弈论可以到学校好好给学弟们讲讲hh.
sg函数是博弈解题的一个工具,就拿今天这个题目当例子来说吧.
题目描述:给定一张NM的矩形网格纸，两名玩家轮流行动。在每一次行动中，可以任选一张矩形网格纸，沿着某一行或某一列的格线，把它剪成两部分。首先剪出1*1的格纸的玩家获胜。两名玩家都采取最优策略行动，求先手是否能获胜。
就是这样的,怎么做呢?首先我们很容易知道(2,2),(2,3),(3,2)这三个点先手必败.
然后我们根据博弈可以转化到路径的形式,sg[n][m]为0代表先手必输,对于每个点,其实都已经确定了必赢还是必输,这个题的图只有一幅,sg[x][y]=0的点一定是必输点.其他点一定是必胜点.
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=205;
int sg[N][N];

inline int SG(int n,int m)
{
    int f[N];
    memset(f,0,sizeof f);
    if(sg[n][m]!=-1)    return sg[n][m];
    for(int i=2;i<=n-2;i++) f[SG(i,m)^SG(n-i,m)]=1;
    for(int i=2;i<=m-2;i++) f[SG(n,i)^SG(n,m-i)]=1;
    int p=0;
    while(f[p]) p++;
    return sg[n][m]=p;
}

int main()
{
    int n,m;
    for(int i=1;i<=N-1;i++)
    {
        for(int j=1;j<=N-1;j++)
        {
            sg[i][j]=-1;
        }
    }
    sg[2][2]=0; sg[2][3]=0; sg[3][2]=0; 
    while(cin>>n>>m)
    {
        SG(n,m)?puts("WIN"):puts("LOSE");    
    }
    return 0;
}