cf787c 博弈论+记忆化搜索

好题，单纯的就是pn状态的推导

/*

把第一个点标为0，剩下的点按1-n-1编号

胜态是1，败态为0,dp[i][j]表示第i个人，怪兽起始位置在j时的胜负态

把0点设置为必败态，然后对于一个人来说，所有能到0点的点都设为必胜态，然后对于另一个人来说，如果他所有选择都会走到对手的必胜态上，那么这个状态就是必败

*/

#include<bits/stdc++.h>

using namespace std;

#define maxn 10000

vector<int>s[];

int n,a,t1,t2,dp[][maxn],chose[][maxn];

void dfs(int k,int i,int v){

    if(dp[k][i]!=-) return;//如果已经有状态

    dp[k][i]=v;

    if(v==){

        for(int it : s[k^]){//所有能到达i点的都是必胜态

            int j=(i+n-it)%n;

            if(j==) continue;

            dfs(k^,j,);

        }

    }

    else {

        for(int it : s[k^]){

            int j=(i+n-it)%n;

            if(j==) continue;

            if(--chose[k^][j]==)//如果这个点能到达的点都是必胜态，那么这个点就是必败态

                dfs(k^,j,);

        }

    }

}

int main(){

    scanf("%d",&n);

    scanf("%d",&t1);

    s[].clear();

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

        scanf("%d",&a);

        s[].push_back(a);

    }

    scanf("%d",&t2);

    s[].clear();

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

        scanf("%d",&a);

        s[].push_back(a);

    }

    for(int i=;i<n;i++) chose[][i]=t1;

    for(int i=;i<n;i++) chose[][i]=t2;

    memset(dp,-,sizeof dp);

    dfs(,,);

    dfs(,,);

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

        if(dp[][i]==-) printf("Loop ");

        else if(dp[][i]==) printf("Win ");

        else printf("Lose ");

    }

    puts("");

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

        if(dp[][i]==-) printf("Loop ");

        else if(dp[][i]==) printf("Win ");

        else printf("Lose ");

    }

    puts("");

}