codeforces 786A Berzerk

（ACM）数学----博弈论 （ACM）BFS

题意

题解

• 博弈论
• 能到达必败点的是必胜点
• 只能到达必胜点的是必败点
• bfs做，没有访问到的是loop

代码

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define mp make_pair
const int N=7005;
queue<pair<int,int> > q;
int k[2],a[2][N],f[2][N],deg[2][N];
void print(int x) {
    if(x==1) printf("Win ");
    else if(x==0) printf("Lose ");
    else printf("Loop ");
}
int main() {
    int n;
    while(~scanf("%d",&n)) {
        ///init
        memset(f,-1,sizeof(f));
        int tt=q.size();
        while(tt--) q.pop();
        ///read
        scanf("%d",&k[0]);
        for(int i=1;i<=k[0];++i) scanf("%d",&a[0][i]);
        scanf("%d",&k[1]);
        for(int i=1;i<=k[1];++i) scanf("%d",&a[1][i]);
        ///get deg
        for(int i=0;i<n;++i) deg[0][i]=k[0];
        for(int i=0;i<n;++i) deg[1][i]=k[1];
        ///bfs
        f[0][n-1]=f[1][n-1]=0;
        q.push(mp(0,n-1));
        q.push(mp(1,n-1));
        while(!q.empty()) {
            int now=q.front().first;
            int pos=q.front().second;
            q.pop();
            int prn=1-now;
            for(int i=1;i<=k[prn];++i) {
                int prp=(pos-a[prn][i]+n)%n;
                if(f[prn][prp]!=-1) continue;
                if(f[now][pos]) {
                    --deg[prn][prp];
                    if(deg[prn][prp]==0) {
                        f[prn][prp]=0;
                        q.push(mp(prn,prp));
                    }
                } else {
                    f[prn][prp]=1;
                    q.push(mp(prn,prp));
                }
            }
        }
        ///print
        for(int i=0;i<=1;++i) {
            for(int j=0;j<n-1;++j) {
                print(f[i][j]);
            }
            puts("");
        }
    } 
    return 0;
}