题目描述

Bessie is playing a number game against Farmer John, and she wants you to help her achieve victory.
Game i starts with an integer . Bessie goes first, and then the two players alternate turns. On each turn, a player can subtract either the largest digit or the smallest non-zero digit from the current number to obtain a new number. For example, from 3014 we may subtract either 1 or 4 to obtain either 3013 or 3010, respectively. The game continues until the number becomes 0, at which point the last player to have taken a turn is the winner.
Bessie and FJ play games. Determine, for each game, whether Bessie or FJ will win, assuming that both play perfectly (that is, on each turn, if the current player has a move that will guarantee his or her win, he or she will take it).
Consider a sample game where . Bessie goes first and takes 3, leaving 10. FJ is forced to take 1, leaving 9. Bessie takes the remainder and wins the game.

输入描述:

* Line 1: A single integer: G
* Lines 2..G+1: Line i+1 contains the single integer:

输出描述:

* Lines 1..G: Line i contains 'YES' if Bessie can win game i, and 'NO' otherwise.

示例1

输入
2 
9 
10 
输出
YES
NO
说明
For the first game, Bessie simply takes the number 9 and wins. For the second game, Bessie must take 1 (since she cannot take 0), and then FJ can win by taking 9.

解答

大致题意
有一个正整数，两个人轮流操作，轮到你时你可以将这个数减去它每个数位上的数中最小或最大的数，最后谁使得这个数变为 则为胜利。比如说现在轮到你操作，有一个三位数 ，那么，你可以选择将这个数减去  或 ，但不可以减去  。两个人都足够聪明，都会按照最优的决策操作。
思路
有多组数据，读一个计算一个可能会比较慢。我们考虑预处理出对于每个数字 是否能赢。当然，你也可以用记忆化搜索 ,而且记搜跑起来会更快。
我们不难想到，一个数只可能从 中的数字得到。用  表示对于  这个数字  能否赢，一开始  。从到  循环，循环到  时  能否由 这个数得到  ，如果能，那么就有 。
具体请见代码 ↓↓
代码 
#include<bits/stdc++.h>
using namespace std;
int f[1000005],n,x;
int Max(int x,int y){return x>y?x:y;}
int Min(int x,int y){return x<y?x:y;}
bool check(int x,int in){
    if(x>1000000)return 0;//防止越界
    register int Min=10,Max=0;
    while(x){
        if(x%10)Min=min(Min,x%10),Max=max(Max,x%10);//更新最大值和最小值
        x/=10;
    }
    return (Min==in||Max==in);//最大或最小的数等于add
}
int main(){
    for(int i=0;i<=1000000;++i){
        if(f[i])continue;//如果当前f[i]=1，那么!f[i+add]=0，就算check后能通过i得到i+add，但是f[i+add]=!f[i]=0，所以没有继续算下去的意义
        for(int add=1;add<=9;++add){//枚举
            if(check(i+add,add))f[i+add]=1;//如果可以由i得到i+add，就可以更新f[i+add]
        }
    }
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&x);
        if(f[x])puts("YES");else puts("NO");//之前已经预处理好了，直接输出就行了
    }
    return 0;
}


来源： Aryzec