题解：P10501 Cutting Game

yrteop_maerD · 2024-12-01 18:03:03 · 题解

思路：

显然考虑博弈论。

鉴于每次划分都相当于把原本一个较大的剪纸游戏转变为两个较小的剪纸游戏，我们考虑枚举每一个竖划分线和横划分线，对于每次划分将划分后两部分 SG 函数的异或和标记一下，然后全部处理完之后求 \rm mex 即可。

边界条件为当 n,m 均小于等于 3 时先手必败，大家可以手推一下。

基本原理仅在于本题可以看为有向图游戏，具体原理建议大家自行学习博弈论相关内容。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int sg[255][255];
int n,m;

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

signed main(){
    memset(sg,-1,sizeof(sg));
    SG(200,200);
    while(cin>>n>>m){
        if (sg[n][m]){
            cout<<"WIN\n";
        }
        else{
            cout<<"LOSE\n";
        }
    }
    return 0;
}