题解 模拟赛 【game】

模拟赛 【game】

题目大意:

题解 模拟赛 【game】

题解 模拟赛 【game】

solution:

我们发现个位数时小 \(Q\) 是必胜的,那么能到个位数的数小 \(Q\) 是比输的,因为小 \(Q\) 操作后小 \(L\) 就会拿掉个位数,然后赢得游戏。那么我们现在就有了一个递推策略:

设 \(f_i\) 为数字 \(i\) 小 \(Q\) 是否必胜,\(Fx_i\) 为数字 \(i\) 最大数码, \(Fm_i\) 为数字 \(i\) 最小数码(除 \(0\) )。

如果 \(f_{i-Fx_i}\) 和 \(f_{i-Fm_i}\) 都必胜,那么 \(f_i\) 必输,否则 \(f_i\) 必胜。

预处理一下就好了。

细节处理:

  • 最小数码不包括 \(0\) 。
代码
#include<cstdio>
using namespace std;
const int N=1e6+5;
bool f[N];
inline int Fx(int x){//求最大数码
	int res=0;
	while(x){
		if(x%10>res) res=x%10;
		x/=10;
	}
	return res;
}
inline int Fm(int x){//求最小数码不包括0
	int res=10;
	while(x){
		if(x%10<res&&x%10!=0) res=x%10;//!
		x/=10;
	}
	return res;
}
inline void init(){
	for(int i=1;i<10;i++) f[i]=1;//个位数都必胜
	for(int i=10;i<=1000000;i++){//递推
		if(f[i-Fx(i)]&&f[i-Fm(i)]) f[i]=0;
		else					   f[i]=1;
	}
}
int main(){
	init(); 
	int T; scanf("%d",&T);
	while(T--){
		int n; scanf("%d",&n);
		if(f[n]) puts("Yes");
		else	 puts("No");
	}
	return 0;
}

End

上一篇:#交互#CF1375F Integer Game


下一篇:POJ-1753Flip Game 枚举