Summary

P2953 [USACO09OPEN]牛的数字游戏 Cow Digit Game 的题解,
算法为 博弈论 .

Link

题目链接

Text

每种状态可以转移出两个新状态. 博弈论的结论:

当某种状态的后继状态 都是必败状态 时, 该状态为必胜状态;

当某种状态的后继状态 有一种是必胜状态 时, 该状态为必败状态.

所以先将 0 标记为必败,1- 9 标记为必胜 (显然), 从 10-1000000 遍历一遍, 用 f 数组存必败或必胜, 然后输出就可以了. 在求 f[i] 的时候只会用到 f[i-max/min], 而 max/min 必然大于 0, 所以顺序遍历即可.

Code

#include <cstdio>
using namespace std;

int q,n;
bool f[1000020];

inline int fmax(int x)
{
    int m=0;
    while (x) {if (x%10>m) m=x%10; x/=10;}
    return m;
}

inline int fmin(int x)
{
    int m=10;
    while (x) {if (x%10<m&&x%10) m=x%10; x/=10;}
    return m;
}

int main()
{
    //f[0]=false 不做处理（因为f默认为false）
    for (int i=1;i<10;i++) f[i]=true;
    for (int i=10;i<1000001;i++)
    {
        if (f[i-fmax(i)]&&f[i-fmin(i)]);//不做处理（因为f默认为false）
        else f[i]=true;
    }
    scanf ("%d",&q);
    for (int i=0;i<q;i++)
    {
        scanf ("%d",&n);
        if (f[n]) printf ("YES\n");
        else printf ("NO\n");
    }
    return 0;
}

然而还有更快的方法:

#include <cstdio>
using namespace std;

bool f[1000020];

inline int fmax(int x)
{
    int m=0;
    while (x) {if (x%10>m) m=x%10; x/=10;}
    return m;
}

inline int fmin(int x)
{
    int m=10;
    while (x) {if (x%10<m&&x%10) m=x%10; x/=10;}
    return m;
}

int main()
{
    freopen (".txt","w",stdout);
    for (int i=1;i<10;i++) f[i]=true;
    printf ("f[1000020]={0,1,1,1,1,1,1,1,1,1");
    for (int i=10;i<1000001;i++)
    {
        if (f[i-fmax(i)]&&f[i-fmin(i)]) f[i]=false;
        else f[i]=true; printf (",%d",f[i]);
    }
    printf ("};"); return 0;
}

配合

#include <cstdio>
using namespace std;

int g,n;
bool //将上一个程序运行后的文件内容粘贴在这里

int main()
{
    scanf ("%d",&g);
    for (int i=0;i<g;i++)
    {
        scanf ("%d",&n);
        if (f[n]) printf ("YES\n");
        else printf ("NO\n");
    }
    return 0;
}

只是洛谷不让交.