模拟赛 【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;
}