题解 | CowDigitGame-牛客假日团队赛9G题

G-Cow Digit Game_牛客假日团队赛9

https://ac.nowcoder.com/acm/contest/1071/G

题目描述

Bessie is playing a number game against Farmer John, and she wants you to help her achieve victory.
Game i starts with an integer $N_i (1 \leq N_i \leq 1,000,000)$ . 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 $G (1 \leq G \leq 100)$ 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 $N_i = 13$ . 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: $N_i$

输出描述:

* 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.

解答

大致题意

有一个正整数，两个人轮流操作，轮到你时你可以将这个数减去它每个数位上的数中最小或最大的数，最后谁使得这个数变为 $0$ 则为胜利。比如说现在轮到你操作，有一个三位数 $123$ ，那么，你可以选择将这个数减去 $1$ 或 $3$ ，但不可以减去 $2$ 。两个人都足够聪明，都会按照最优的决策操作。

思路

有多组数据，读一个计算一个可能会比较慢。我们考虑预处理出对于每个数字 $Bessie$ 是否能赢。当然，你也可以用记忆化搜索 ,而且记搜跑起来会更快。

我们不难想到，一个数 $x$ 只可能从 $x+1 \sim x+9$ 中的数字得到。用 $f_i$ 表示对于 $i$ 这个数字 $Bessie$ 能否赢，一开始 $f_0=0$ 。从 $0$ 到 $Maxn$ 循环，循环到 $i$ 时 $check$ 能否由 $i+add ( 1\leq add \leq 9 )$ 这个数得到 $i$ ，如果能，那么就有 $f[i+add]=!f[i]$ 。

具体请见代码 ↓↓

代码

#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