题解 P2953 【[USACO09OPEN]牛的数字游戏Cow Digit Game】

· · 题解

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

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

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

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

#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;
}

只是洛谷不让交……