Cogs 763. [USACO Open09] 数字的游戏(博弈)

[USACO Open09] 数字的游戏

★☆ 输入文件：cdgame.in 输出文件：cdgame.out 简单对比

时间限制：1 s 内存限制：128 MB

Bessie正跟FJ玩一个数字游戏，她想让你帮她赢。

游戏的第i局由一个整数N_i(1 <= N_i <= 1,000,000)开始，Bessie先手，接下来两个人交替进行，轮到谁时，她（他）可以在当前整数中挑一个最大的或最小的非零数字，并减去该数字，所得的差成为新的游戏数。比如若当前整数为3014，我们可以从中减去最大数字4或最小非零数字1，得数为3010或3013。每一局游戏以得到数0为结束，而得0的选手为胜利一方。

Bessie与FJ一共要玩G(1 <= G <= 100)局，请确定每局游戏的胜者，假定他们两个都玩得很好（这意味着每轮到一方执手，他都会怎么能赢就怎么做）。

举个例子：起初N_i=13,Bessie先手，她选了数字3，减去后得10，FJ只能选数字1，减去后得9，Bessie选数字9，减去后得到0，Bessie赢。

输入格式：

第1行：一个整数G；

第2～G+1行:第i+1行包含一个整数N_i;

输出格式：

共G行，如果第i局Bessie赢则在第i行输出”YES”，如果Bessie不能赢则第i行的输出为”NO”。

输入输出样例：

cdgame.in

2

9

10

cdgame.out

YES

NO

输出样例解释：

第一局，Bessie只需选9减去即赢；第二局，Bessie只能选1（不能选0），然后FJ选9减去即赢。

/*

博弈.

递推sg函数.

显然1~9都是必胜态.

显然操作后数都会变小.

如果一个状态的后继状态有必败态,

那么它就是必胜态.

否则就是必败态.

*/

#include<iostream>

#include<cstdio>

#define MAXN 1000001

using namespace std;

int n,max1,min1,sg[MAXN];

void pre()

{

    for(int i=1;i<=9;i++) sg[i]=1;

    for(int i=10;i<=MAXN-1;i++)

    {

        int x=i;

        min1=10,max1=0;

        while(x)

        {

            int xx=x%10;

            x/=10;

            if(xx) min1=min(xx,min1);

            if(xx) max1=max(max1,xx);

        }

        if(!sg[i-min1]||!sg[i-max1]) sg[i]=1;

        else sg[i]=0;

    }

}

int main()

{

    freopen("cdgame.in","r",stdin);

    freopen("cdgame.out","w",stdout);

    int x;

    pre();scanf("%d",&n);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&x);

        if(sg[x]) printf("YES\n");

        else printf("NO\n");

    }

    return 0;

}

秒客网

Cogs 763. [USACO Open09] 数字的游戏(博弈)

相关文章