题意:
一张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"); } }