博客阅读效果更佳

蒟蒻的第一道博弈论题目大概

游戏开始时，是一个$N*M$的矩形网格纸。但是在游戏过程中会被分割。我们把每一个矩形网格纸都当做一个”游戏“，那么我们求的就是有向图游戏的和

那么现在就有一个问题：

不能行动的局面是$1*1$，此时行动者判负($Update:$应该是判胜，打错了)，这与有向图游戏不符合

我们思考$1*1$局面能够怎么得出，显然势必会经过$1*X，X*1，2*2，2*3，3*2$这几个局面

容易看出：$1*X$和$X*1$是给对手送分的行为

那么得到$1*1$局面就必然经过$2*2，2*3，3*2$这三个局面之一

单独看着三个局面，容易看出先手必败

那么我们可以把这三种状态当做有向图游戏的无法移动状态

接下来的问题就是考虑如何去移动了，我们可以枚举把这张剪枝剪成两部分，这两部分就是两个“子剪纸游戏”，二者的SG值执行$xor$运算，就得到了这个行动之后局面的$SG$值，对所有的合法行动产生的局面构成的集合执行$mex$运算，就得到了这个$N*M$的矩形网格纸的$SG$函数值，从而根据有向图游戏的和的知识

• 如果$SG$函数值大于$0$，必胜
• 如果$SG$函数值等于$0$，必败

/*
@ author:pyyyyyy
-----思路------

-----debug-------

*/
#include<bits/stdc++.h>
using namespace std;
const int N=220;
int sg[N][N];
int n,m;
int SG(int x,int y)
{
    int f[N];
    memset(f,0,sizeof(f));//集合
    if(sg[x][y]!=-1) return sg[x][y];
    for(int i=2;i<=x-2;++i) f[SG(i,y)^SG(x-i,y)]=1;
    for(int i=2;i<=y-2;++i) f[SG(x,i)^SG(x,y-i)]=1;
    int p=0;
    while(f[p]) ++p;//mex运算 
    return sg[x][y]=p;
}
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout)；
    for(int i=1;i<=N;++i)
        for(int j=1;j<=N;++j)
            sg[i][j]=-1;
    sg[2][2]=0,sg[2][3]=0,sg[3][2]=0; 
    while(cin>>n>>m)
    {
        cout<<(SG(n,m)?"WIN":"LOSE");
        cout<<'\n';
    }
    return 0;
}