题目

题目链接：https://codeforces.com/contest/786/problem/A
Rick 和 Morty 在玩一个版本的 Berzerk 游戏。这个游戏需要很大的空间，所以他们使用电脑玩这个游戏。
游戏中有 n) 个标号从 1 sim n) 的物体围成一个圆圈（顺时针标号），物体 1) 表示黑洞，其它物体表示星球，且某一个星球上有一个怪物，Rick 和 Morty 不知道这个怪物在哪个星球上，只知道这个怪物在游戏开始时没有进入黑洞。但就目前而言，他们希望为每种可能的情况做好准备。
Rick 和 Monty 每人有一个数的集合，集合中的数在 [1,n-1]) 之间。Rick 的集合是 s_1)，其中有 k_1) 个数，Morty 的集合是 s_2)，其中有 k_2) 个数。游戏开始后，两人轮流操作。在操作中，玩家必须从他的集合中选出一个数 x)，怪物将从当前位置顺时针移动 x) 个位置，如果怪物移动后进入了黑洞，则该玩家获胜。
你的任务是对于每一个怪物的位置以及玩家先后手顺序，判断游戏先手获胜、后手获胜、无限循环。（每个玩家都采取最优操作）
nleq 7000)。

思路

设 f[0/1][x]) 表示 Rick/Monty 先手，怪兽位置在 x) 时的情况。0) 表示平局，1) 表示先手胜，2) 表示先手败。
先把所有先手一步可以获胜的位置初始化，然后扔进一个队列里拓扑排序。对于当前的点 f[y][x])：

f[y][x]=1)，那么就找到另一方可以到达 f[y][x]) 的所有位置，让那个位置的度数减一。当度数等于 0) 时，说明那个位置先手必败，并插入队列。
f[y][x]=2)，另一方可以到达 f[y][x]) 的所有位置必然先手必胜。

时间复杂度 On^2))。

代码

#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
using namespace std;

const int N=7010;
const string s[3]={"Loop","Win","Lose"};
int n,m[2],a[2][N],deg[2][N],f[2][N];
queue<pair<int,int> > q;

int main)
{
	scanf"%d%d",&n,&m[0]);
	for int i=1;i<=n;i++) deg[0][i]=m[0];
	for int i=1;i<=m[0];i++)
	{
		scanf"%d",&a[0][i]);
		f[0][n-a[0][i]+1]=1;
		q.pushmpn-a[0][i]+1,0));
	}
	scanf"%d",&m[1]);
	for int i=1;i<=n;i++) deg[1][i]=m[1];
	for int i=1;i<=m[1];i++)
	{
		scanf"%d",&a[1][i]);
		f[1][n-a[1][i]+1]=1;
		q.pushmpn-a[1][i]+1,1));
	}
	while q.size))
	{
		int x=q.front).fi,y=q.front).se^1; q.pop);
		if f[y^1][x]==2)
			for int i=1;i<=m[y];i++)
			{
				int z=x-a[y][i]+n-1)%n+1;
				if z!=1 && !f[y][z]) f[y][z]=1,q.pushmpz,y));
			}
		else
			for int i=1;i<=m[y];i++)
			{
				int z=x-a[y][i]+n-1)%n+1;
				if z!=1 && !f[y][z])
				{
					deg[y][z]--;
					if !deg[y][z]) f[y][z]=2,q.pushmpz,y));
				}
			}
	}
	for int i=2;i<=n;i++) cout<<s[f[0][i]]<<" ";
	cout<<"
";
	for int i=2;i<=n;i++) cout<<s[f[1][i]]<<" ";
	return 0;
}