题意:

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

题解:

经典博弈论
sg函数
Sprague-Grundy定理:游戏和的SG函数等于各个游戏SG函数的Nim和(异或和)
mex(minimal excludant)运算: 这是一个针对集合的运算;返回这个集合中不包含的最小的非负整数,例如mex({1,2,3})=0,mex({0,2,3})=1,mex({0,1,3})=2
所以对于一张纸,我们可以递归横切 dfs(i,y)^dfs(x-i,y),递归竖切dfs(x,i)^dfs(x,y-i),当然前提是纸的x>1,y>1
set记录集合中出现过的数,最后找不包含的最小的非负整数,即为当前x和y的答案

代码:

#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define me0(a) memset(a,0,sizeof(a))
#define me1(a) memset(a,-1,sizeof(a))
#define op freopen("in.txt", "r", stdin)
#define op1 freopen("C:\\acm\\Cproj\\in.txt","r",stdin);
#define pr freopen("C:\\acm\\Cproj\\out.txt","w",stdout)
#define pr2 freopen("C:\\acm\\Cproj\\std.txt","w",stdout)
#define pii pair<int,int>
#define Please return
#define AC 0
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
template <class T>
void read(T &val) { T x = 0; T bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }
const int mod=998244353;
const int maxn = 2e6+10;

int sg[200][200];

int dfs(int x,int y){
    //横切
    if(sg[x][y]!=-1) return sg[x][y];
//    cout<<x<<" "<<y<<endl;

    set<int>s;
    fo(i,1,x-1){
        int a;
        if((i==1&&y==1)||(i==x-1&&y==1)) continue;
        a = dfs(i,y)^dfs(x-i,y);//横切 
        s.insert(a);
    }

    fo(i,1,y-1){
        if((i==1&&(x==1))||(i==y-1)&&x==1) continue;
        int a = dfs(x,i)^dfs(x,y-i);//竖切 
        s.insert(a);
    }
    fo(i,0,10000){
        if(!s.count(i)){//没有出现过i 
            sg[x][y]=i;
            break;
        }
    }
    return sg[x][y];

}

int main(){
    me1(sg);
    sg[1][1] = sg[1][2] = sg[2][1] = sg[1][3] = sg[3][1] = 0;
    dfs(150,150);
    int x,y;
    while(scanf("%d%d",&x,&y)!=EOF){
        if(sg[x][y]) puts("Alice");
        else puts("Bob");
    }

}