题目背景
无
题目描述
Alice 和 Bob 在一个圆环上玩游戏。圆环上有 n 个位置，按照顺时针顺序 依次标号为 1 到 n。Alice 和 Bob 分别有一个数字集合，集合中都是在 [1, n−1] 内的正整数。游戏开始时会有一个棋子摆在圆环上的某个位置，然后两人轮流 行动。轮到某个人的回合时，他可以从他的集合中选出某个数 x，然后把棋子 沿顺时针方向移动 x 个位置。如果某个人把棋子移动到了 1 号位置，那么他就 获胜了。两个人都会以最优策略行动。 你需要对不同先后手顺序以及棋子初始位置的每种情况，求出谁能获胜， 或者说游戏永远不会结束。
输入输出格式
输入格式：
第一行为一个正整数 n。 第二行的第一个正整数 k1 表示 Alice 的集合的大小，接下来的 k1 个正整 数表示 Alice 的集合中的数（保证这些数不会重复）。 第三行的第一个正整数 k2 表示 Bob 的集合的大小，接下来的 k2 个正整 数表示 Bob 的集合中的数（保证这些数不会重复）。
输出格式：
第一行输出 n − 1 个词，第 i 个词表示 Alice 先手且棋子初始在位置 i + 1 的答案。如果 Alice 必胜输出”Win”，必败输出”Lose”，游戏不会结束输 出”Loop”。 第二行输出 n−1 个词，第 i 个词表示 Bob 先手且棋子初始在位置 i+ 1 的 答案。如果 Bob 必胜输出”Win”，必败输出”Lose”，游戏不会结束输出”Loop”。
输入输出样例
53 3 1 22 2 3
Loop Win Win WinLose Win Win Loop
说明
对于 30% 的数据，保证 2 ≤ n ≤ 5。 对于 60% 的数据，保证 2 ≤ n ≤ 300。 对于 100% 的数据，保证 2 ≤ n ≤ 7000, 1 ≤ k1, k2 ≤ n − 1。
就是一个最简单的博弈问题，图都不用建一遍dfs就行了。。。
然而我考试的时候忘了标记已经计算过的节点然后才50。。。。。我好菜啊ww
#include#include #include #include #include #include #include #include #define ll long long#define maxn 7005using namespace std;int n,s,t,a[maxn],b[maxn];int win[maxn*2];int cnt[maxn*2];bool vis[maxn*2];inline int add(int x,int y){ x+=y; if(x>=n) return x-n; else return x;}inline void bfs(){ queue q; int x,to; q.push(0),q.push(n); win[0]=win[n]=-1; while(!q.empty()){ x=q.front(),q.pop(); vis[x]=1; if(x