Cutting Game

POJ

题意:给定一张\(N*M\)的矩形网格纸,两名玩家轮流行动.在每一次行动中,可以任选一张矩形网格纸,沿着某一行或者某一列的格线,把它剪成两部分.首先剪出\(1*1\)的玩家获胜.两名玩家都采取最优策略行动,求先手是否必胜?

分析:一般的博弈论问题都是"不能再动就输了",而本题却相反,先剪出\(1*1\)的玩家获胜.所以我们需要转化一下.注意到,要剪出\(1*1\),必然要先剪出\(2*2,2*3,3*2\)三种局面之一,如果碰到了这种局面无论怎么剪都是对方获胜,所以这是必败局面.把这个作为必败局面,这样就可以用\(SG\)函数来做了.

对于一张网格纸,枚举如何剪,则剪成的两个部分都是子游戏,两个子游戏的\(SG\)函数值的异或值,就是该局面的\(SG\)函数异或值.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int SG[205][205],mex[205];
inline int get_SG(int n,int m){
    if(SG[n][m]!=-1)return SG[n][m];
    memset(mex,0,sizeof(mex));
    for(int i=2;i<=n-i;i++)mex[get_SG(n-i,m)^get_SG(i,m)]=1;
    for(int i=2;i<=m-i;i++)mex[get_SG(n,m-i)^get_SG(n,i)]=1;
    for(int i=0;;i++)if(!mex[i])return SG[n][m]=i;
}
int main(){
    int n,m;memset(SG,-1,sizeof(SG));
    SG[3][2]=SG[2][3]=SG[2][2]=0;
    while(~(scanf("%d%d",&n,&m)))
        puts(get_SG(n,m)?"WIN":"LOSE");
    return 0;
}

Cutting Game

原文：https://www.cnblogs.com/PPXppx/p/10882991.html