解题思路
首先很好写出一个\(O(ab)\)的记搜，但发现这样无法处理\(a=1\)和\(b=1\)的情况，这两种情况需要特判。首先\(a=1\)的情况，就是如果当前选手让\(a+1\)必胜，那么他一定会给\(a+1\)，否则会给\(b+1\)，如果到\(2^b>n\)时，说明谁动\(a\)谁输，就是平局了，这样的话可以模拟这个过程不断给\(b+1\)即可。第二种情况是\(b=1\)，这种情况一定没有平局，那么就和刚才一样模拟即可。最后一种情况是\(a=1\)并且\(b=1\)，这样的话把\(a=1,b=2\)和\(a=2,b=1\)的答案都算出来，然后讨论一下。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
const int N=40005;
typedef long long LL;
int n,a,b,ans;
bool f[N][35],vis[N][35];
inline LL fast_pow(LL x,int y){
LL ret=1;
for(;y;y>>=1){
if(y&1) ret=ret*x;
x=x*x;
}
return ret;
}
bool dfs(int x,int y){
if(vis[x][y]) return f[x][y];
vis[x][y]=1; int now;
if(fast_pow(1ll*x,y)>=n) return f[x][y]=1;
now=(dfs(x+1,y)^1)|(dfs(x,y+1)^1);
if(now) return f[x][y]=1;
return f[x][y]=0;
}
int one(int a,int b){
int ret=0,tmp=0;
while(fast_pow(2,b)<n){
if(!dfs(2,b)){
if(!tmp) ret=1;
else ret=2;
break;
}
tmp^=1; b++;
}
return ret;
}
int two(int a,int b){
int tmp=0,ret=0,pre=a;
while(fast_pow(a,2)<n){
if(!dfs(a,2)){
if(!tmp) ret=1;
else ret=2;
break;
}
tmp^=1; a++;
}
if(!ret) {
if((n-1-pre)&1) ret=1;
else ret=2;
}
return ret;
}
int main(){
scanf("%d%d%d",&a,&b,&n);
if(a==1 && b==1){
int now1=one(a,b+1); if(now1!=0) now1=3-now1;
int now2=two(a+1,b); now2=3-now2;
if(now1==1 || now2==1) puts("Masha");
else if(now1==2 && now2==2) puts("Stas");
else puts("Missing");
return 0;
}
else if(a==1){
ans=one(a,b);
if(ans==1) puts("Masha");
else if(ans==2) puts("Stas");
else puts("Missing");
return 0;
}
else if(b==1){
ans=two(a,b);
if(ans==1) puts("Masha");
else if(ans==2) puts("Stas");
return 0;
}
if(dfs(a,b)) puts("Masha");
else puts("Stas");
return 0;
}