Split Game 是2020ICPC 江西省大学生程序设计竞赛的题
剪纸游戏是acwing的一个博弈论题
我们对比两个很相似但是不一样的博弈论问题

题意：

Split Game ：一张n * m的纸，两个人轮流操作，可以沿着一条直线切，当有人切出1 * 1的纸时即为输掉比赛，问最后谁赢
剪纸游戏：一张n * m的纸，两个人轮流操作，可以沿着一条直线切，当有人切出1 * 1的纸时即为赢得比赛，问最后谁赢

分析

题目很相似，区别在于先切出1 * 1 的是赢是输
那是不是我们按照第一个题Split game的思路来做第二个题，是不是就能a？
不完全是
第一个题是常规的有向图题
在第二个题中，并不是传统的有向图游戏，传统的有向图游戏定义是：当无路可走时游戏结束，而第二题是达到某种情况时，游戏直接结束
注意下，在第一个题中我们将1 * 1定义为必败状态,也就是当所有人都剪不了纸时游戏结束了
但是第二个题是当有人剪除1 * 1时，游戏立刻终止，无论双方还能否操作，游戏直接结束
也就是说在第一种情况中会尽可能不剪出1 * 1，除非没办法，而在第二种情况中会尽可能剪除1 * 1
在代码中除了剪切部分，其他都一样
split game的剪切是

for(int x=1;x<=n-1;x++){
        if((x==1&&m==1)||(x==n-1&&m==1)) continue;
        ans = dfs(x,m)^dfs(n-x,m);
        vis[ans] = 1;
    }

    for(int y=1;y<=m-1;y++){
        if((y==1&&n==1)||(y==m-1&&n==1)) continue;
        ans = dfs(n,y)^dfs(n,m-y);
        vis[ans] = 1;
    }

你会发现我们我们除了 1 * 1 的不能减，其他都OK
因为剪除1 * 1的边会输，所以我们除了不能让自己直接数（即剪除1 * 1 ），我们可以剪除1的边，来引诱对方输

剪纸游戏是：

for(int x=2;x<n-1;x++){
        //if((x==1&&m==1)||(x==n-1&&m==1)) continue;
        ans = dfs(x,m)^dfs(n-x,m);
        vis[ans] = 1;
    }

    for(int y=2;y<m-1;y++){
        //if((y==1&&n==1)||(y==m-1&&n==1)) continue;
        ans = dfs(n,y)^dfs(n,m-y);
        vis[ans] = 1;
    }

我们从2开始，尽可能避免出现边为1的情况，因为1 * 1 必胜，如果我们剪除一条边是1的情况，那轮到对方操作，对方可以直接剪除1 * 1 （我们贡献了一个1），为了保证我们自己获胜，我们肯定不会允许这种情况发生，所以会避免剪除1的边

所以第二个题
1 * 1 必胜我们可以将其上一个状态变为必败
或者x不从1开始，我们从2开始，直接跳过非法情况(也就是我们不按照第一条减，!=1,也不等于n-1)
有点啰嗦，大致如此
第一题代码：

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define MAXN 205
using namespace std;
typedef long long ll;

int N,M;
int sg[MAXN][MAXN];

int dfs(int n, int m){
    if(n > m) swap(n,m);
    if(sg[n][m]!=-1) return sg[n][m];
    if(n==1 && m==1) return sg[n][m] = 0;
    //cerr<<"dfs: "<<n<<" "<<m<<endl;

    int vis[MAXN];
    memset(vis, 0, sizeof(vis));
    int ans;
    for(int x=1;x<=n-1;x++){
        if((x==1&&m==1)||(x==n-1&&m==1)) continue;
        ans = dfs(x,m)^dfs(n-x,m);
        vis[ans] = 1;
    }

    for(int y=1;y<=m-1;y++){
        if((y==1&&n==1)||(y==m-1&&n==1)) continue;
        ans = dfs(n,y)^dfs(n,m-y);
        vis[ans] = 1;
    }

    for(int i=0;i<=300;i++){
        if(!vis[i]) return sg[n][m] = i;
    }
}

int main(){

    memset(sg, -1, sizeof(sg));

    while(cin>>N>>M){
        if(N > M) swap(N, M);
        //dfs(N,M);
        if(dfs(N,M)) puts("Alice");
        else puts("Bob");
    }
    return 0;
}

第二题代码：

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define MAXN 205
using namespace std;
typedef long long ll;

int N,M;
int sg[MAXN][MAXN];

int dfs(int n, int m){
    if(n > m) swap(n,m);
    if(sg[n][m]!=-1) return sg[n][m];
    if(n==1 && m==1) return sg[n][m] = 0;
    //cerr<<"dfs: "<<n<<" "<<m<<endl;

    int vis[MAXN];
    memset(vis, 0, sizeof(vis));
    int ans;
    for(int x=2;x<n-1;x++){
        //if((x==1&&m==1)||(x==n-1&&m==1)) continue;
        ans = dfs(x,m)^dfs(n-x,m);
        vis[ans] = 1;
    }

    for(int y=2;y<m-1;y++){
        //if((y==1&&n==1)||(y==m-1&&n==1)) continue;
        ans = dfs(n,y)^dfs(n,m-y);
        vis[ans] = 1;
    }

    for(int i=0;i<=300;i++){
        if(!vis[i]) return sg[n][m] = i;
    }
}

int main(){

    memset(sg, -1, sizeof(sg));

    while(cin>>N>>M){
        if(N > M) swap(N, M);
        //dfs(N,M);
        if(dfs(N,M)) puts("WIN");
        else puts("LOSE");
    }
    return 0;
}