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?'
':' ');
        }
    }return 0;
}