题目

题目链接：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]) 的所有位置必然先手必胜。

时间复杂度 (O(n^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.push(mp(n-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.push(mp(n-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.push(mp(z,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.push(mp(z,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;
}