Codeforces 786A Berzerk（博弈论）

【题目链接】 http://codeforces.com/problemset/problem/786/A

【题目大意】

　　有两个人，每个人有一个数集，里面有一些数，现在有一个环，有个棋子放在1，
　　有个不确定位置的终点，两个人轮流从自己的数集中选择一个数，作为这个棋子移动的步数
　　问终点在不同位置，不同人先手的时候谁能赢，或者游戏陷入循环

【题解】　

　　我们从st_0_0=st_1_0=0开始倒着推导，
　　如果一个状态是必败态，那么它的前继节点一定是必胜态
　　如果一个点的所有后继都是必胜态，那么这个节点一定是必败态。
　　每当一个点被其必胜后继推导到，那么其度数减一，当度数为0时则表示其为必败态
　　我们根据这些结论倒着推导每个状态的答案并记录，最后按顺序输出即可。

【代码】

#include <cstdio>

#include <vector>

#include <cstring>

#include <string>

using namespace std;

const int N=100010;

int n,sg[2][N],d[2][N],k,x;

vector<int> g[2];

int dfs(int k,int pos,int v){

    int &ret=sg[k][pos];

    if(~ret)return ret;

    ret=v;

    if(v==0){

        for(int i=0;i<g[k^1].size();i++){

            int x=g[k^1][i];

            int j=(pos+n-x)%n;

            if(j==0)continue;

            dfs(k^1,j,1);

        }

    }else{

        for(int i=0;i<g[k^1].size();i++){

            int x=g[k^1][i];

            int j=(pos+n-x)%n;

            if(j==0)continue;

            if(--d[k^1][j]==0)dfs(k^1,j,0);

        }

    }return ret;

}

int main(){

    scanf("%d",&n);

    for(int i=0;i<2;i++){

        scanf("%d",&k);

        g[i].clear();

        while(k--){

            scanf("%d",&x);

            g[i].push_back(x);

        }for(int j=1;j<n;j++)d[i][j]=g[i].size();

    }memset(sg,-1,sizeof(sg));

    dfs(0,0,0);

    dfs(1,0,0);

    string s[3]={"Loop","Lose","Win"};

    for(int k=0;k<2;k++){

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

            printf("%s%c",s[sg[k][i]+1].c_str(),i+1==n?'\n':' ');

        }

    }return 0;

}

巴特西

Codeforces 786A Berzerk（博弈论）

最新文章

热门文章