题解：P1839 Play with Power

我的思路和大佬差不多，也是记忆化搜索。

ans_{i,j}

数组用来存储当初始

a

，

b

为

i

，

j

时，先手的人的胜负情况，

1

表示先手的人赢，

2

表示先手输，

3

表示平局。

f(a + 1,b)

和

f(a,b + 1)

表示下一个人胜负情况，若两个均胜，则本次先手的人必输，若有至少一个为负，因为是最优策略，则本次必胜。

当

a = 1

时，因为

a

的任何次幂都为

1

，所以两个人会无限的执行

b + 1

，只能平局。

当

a = 2

时，如果

b > 27,a^b

超过

n

最大值，也要判断一下。

希望上述内容可以帮助大家理解。

最后，献上蒟蒻的代码：

CPP

#include<bits/stdc++.h>
using namespace std;
string s;
int n,t,a,b;
int ans[114514][30];
int dfs(int x,int y){
	if(x==1&&y>27){
		return 3;// 当b>27时，2^27>1e8，所以只能加b，但是1的任何次幂都是1，所以只能平局 
	}
	if(y==1&&x>n/x){
		return ((n-x)&1)?1:2;//当b=1时，若a^2>n，则只能a+1，若n-a为偶数，则 S胜，反之M胜 。
	}
	if(ans[x][y]){
		return ans[x][y];//已经有了这个状态，直接返回即可 。
	}
	if(n<pow(x,y)){
		return 1;
	}
	int xx=dfs(x+1,y),yy=dfs(x,y+1);  //题解里面已经说了。
	if(xx==1&&yy==1){
		return	ans[x][y]=2;
	}else if(xx==2||yy==2){
		return ans[x][y]=1;
	}else{
		return ans[x][y]=3;
	}
}
signed main(){
	cin>>n>>t;
	ans[1][27]=3;
	for(int i=1;i<=t;i++){
		scanf("%d%d",&a,&b);
		int temp=dfs(a,b);
		if(temp==1){
			printf("Masha\n");
		}else if(temp==2){
			printf("Stas\n");
		}else if(temp==3){
			printf("Missing\n");
		}
	}
	
	return 0;
}

题解：P1839 Play with Power

文章操作

相关推荐

评论

题解：P1839 Play with Power