题目描述

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.

解答

分析题目，我们发现，对于当前的一个数字，必然是从之前的一些数字得到的。
比如我们举 2017 为例，
2017 // 第一层 ： A 玩家 将数字减到了 2017
2016 2010 // 第二层 ： B 玩家 可以将数字减到 这两个新数字
2015 2010 2009 2008 // 第三层 ： A 玩家 可以将数字减到 这四个可能的值
我们发现了一个结论， 如果在 2016 转移出得两个数，和 2010 转移出的两个数，其中都至少有一个是我必胜的，那么 2017 这个数字，
无论对手选择 到 2016 还是 到 2010 我都有必胜的做法，这是 2017 是我的必胜数字的充要条件。
Code 
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for (int i=(a);i<(b);++i)
bool f[1000005];
int n;
int max_dig(int x)
{
    int ret = 0;
    while(x){
        ret = max(ret, x % 10);
        x /= 10;
    }
    return ret;
}
int min_dig(int x)
{
    int ret = 9999;
    while(x){
        if (x % 10 != 0) ret = min(ret, x % 10);
        x /= 10;
    }
    return ret;
}
int main()
{
    f[0] = true, f[10] = true;
    REP(i,1,10) f[i] = false;
    REP(i,10,1000005)
    {
        bool f1 = false, f2 = false, g1 = false, g2 = false;
        int a = i - min_dig(i),b = i - max_dig(i);
        if (f[a - min_dig(a)]) f1 = true;
        if (f[a - max_dig(a)]) f2 = true;
        if (f[b - min_dig(b)]) g1 = true;
        if (f[b - max_dig(b)]) g2 = true;
        if ((f1 && g1) || (f1 && g2) || (f2 && g1) || (f2 && g2)) f[i] = true;
    }
    scanf("%d",&n);
    while(scanf("%d",&n) != EOF)
    {
        if (f[n]) cout << "NO" << endl;
        else cout << "YES" << endl;
    }
    return 0;
}


来源：何卓然