【Luogu】P2953牛的数字游戏（博弈论）

　　题目链接

　　自己乱搞……然后一遍AC啦！

　　思路从基本的必胜态和必败态开始分析。我们把减去最大数得到的数叫作Max，减去最小数得到的数叫作Min。

　　那么开始分析。

　　一、0是必败态。

　　　　这个没法解释。题目就这么定义的。

　　二、若一个数的Max和Min都是必胜态，那该数为必败态。

　　　　如果你拿到一个数，结果你发现怎么减都会让对手必胜，那恭喜你，你拿到了一个必败的数。很好理解。

　　三、若一个数的Max和Min有一个是必败态，那该数为必胜态。

　　　　如果你拿到一个数，发现有一种减法让对手从此无法翻盘，那恭喜你，你拿到了一个可以必胜的数。　

　　根据这三条原则就很好设计啦

　　设f[x]判断x是必胜态还是必败态。从小到大枚举，按上面三条原则乱搞搞就可以O1查询啦。

#include<cstdio>

#include<cstdlib>

#include<cctype>

#include<algorithm>

using namespace std;

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

struct Point{

    int maxn,minn;

    Point(){    maxn=-;minn=;    }

};

inline Point getlen(int val){

    Point ans;

    while(val){

        int x=val%;    val/=;

        if(!x)    continue;

        ans.maxn=max(ans.maxn,x);

        ans.minn=min(ans.minn,x);

    }

    return ans;

}

int f[];

bool vis[];

void dfs(int val){

    if(vis[val])    return;

    vis[val]=;

    if(val==)        return;

    Point now=getlen(val);

    if(!vis[val-now.maxn])    dfs(val-now.maxn);

    if(!vis[val-now.minn])    dfs(val-now.minn);

    if((f[val-now.maxn]==)||(f[val-now.minn]==))    f[val]=;

}

int main(){

    int T=read();

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

        if(!vis[i])    dfs(i);

    while(T--){

        int n=read();

        if(f[n])    printf("YES\n");

        else        printf("NO\n");

    }

    return ;

}

巴特西

【Luogu】P2953牛的数字游戏（博弈论）

最新文章

热门文章