列表

详情

NC205331. MobiusRing

描述

Does everyone know the Mobius Ring? The Mobius Ring is a structure that loops indefinitely. Here shows the picture of it:

Little Gyro is fond of the Mobius Ring. One day, Little Gyro found that Derrick was studying with his girlfriend, so he called another teammate Onlystar for his brand new game which was recently invented. And they were happily playing games on the Mobius Ring.
In this game, there are N positions numbered from 0 to N-1 arranged in a circle(in the clockwise order). Position numbered 0 is a black hole and others are all empty. And there's a huge monster in one of the empty positions. Both Little Gyro and Onlystar don't know the initial position of the monster yet, they only know it's not at the black hole. Before the game starts, the system will inform them of the monster's position randomly. But now, they want to be well prepared for every possible scenario.
At the beginning of the game, each person has a set of numbers between 1 and N-1 (inclusive). Little Gyro's set is named s_1 and contains k_1 elements while Onlystar's is named s_2 and contains k_2 elements. One of them goes first and the players change alternatively. In each player's turn, the player should choose an arbitrary number such as x from his set and then the monster will move to his next x-th position from its current position(also in the clockwise order). If and only if after the move that the monster falls into the black hole, the game ends while the person who makes the last move wins the game.
Given two number sets s_1, s_2, for each player goes first, you should determine if the starter wins, loses, or the game will stuck in an infinite loop for every initial position of the monster from 1 to N-1. Please note that, in case a player may lose the game or make the game go infinity, it's more profitable to control the game never end.

输入描述

There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains a single integer N (2 ≤ N ≤ 7000), indicating the total number of positions in game.
The second line contains an integer k_1 followed by k_1 distinct integers , ,..., , indicating Little Gyro's set.
The third line contains an integer k_2 followed by k_2 distinct integers , ,..., , indicating Onlystar's set.
It's guaranteed that 1 ≤ k_1,k_2 ≤ N-1 and 1 ≤ , ,...,  ≤ N-1, and in the huge data file, T is exactly 1.

输出描述

For each case, in the first line output N-1 words separated by a space where i-th word is "Win"(without quotes) if its in the scenario that Little Gyro plays first and monster is initially at the position numbered i+1 as he wins, output "Lose"(without quotes) if he loses or "Loop"(without quotes) if the game will never end.
Similarly, in the second line print N-1 words separated by a space where i-th word is "Win"(without quotes) if its in the scenario that Onlystar plays first and monster is initially at the position numbered i+1 he wins, "Lose"(without quotes) if he loses and "Loop"(without quotes) if the game will never end.
Note: Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!

示例1

输入: 

2
5
2 3 2
3 1 2 3
8
4 6 2 3 4
2 3 6

输出: 

Lose Win Win Loop
Loop Win Win Win
Win Win Win Win Win Win Win
Lose Win Lose Lose Win Lose Lose

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 389ms, 内存消耗: 1388K, 提交时间: 2020-06-06 14:56:33 

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<cmath>
#include<string.h>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue> 
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<sstream>
#include<fstream>
#define ZERO 1e-6
#define p pair<int,int>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
const int MAXN=1e4+10;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

struct Node
{
	int NO;
	bool F;
	int Statu;
};

int N,M;
vector<int> step[2];
Node ans[MAXN][2];
int deg[MAXN][2];
bool visited[MAXN][2];
queue<Node> q;
char str[3][10]={"Loop","Win","Lose"};

int back(int now,int length)
{
	return (now-length+N)%N;
}

void bfs()
{
	Node now;
	int x,y;
	
	while(!q.empty())
	{
		q.pop();
	}
	q.push(ans[0][0]);
	q.push(ans[0][1]);
	while(!q.empty())
	{
		now=q.front();
		q.pop();
		if(now.F)
		{
			y=1;
		}
		else
		{
			y=0;
		}
		if(now.Statu==1)
		{
			for(int i=0;i<step[y].size();i++)
			{
				x=back(now.NO,step[y][i]);
				if(!visited[x][y])
				{
					if(++deg[x][y]==step[y].size())
					{
						ans[x][y].Statu=2;
						visited[x][y]=true;
						M++;
						q.push(ans[x][y]);
					}
				}
			}
		}
		else if(now.Statu==2)
		{
			for(int i=0;i<step[y].size();i++)
			{
				x=back(now.NO,step[y][i]);
				if(!visited[x][y])
				{
					ans[x][y].Statu=1;
					visited[x][y]=true;
					M++;
					q.push(ans[x][y]);
				}
			}
		}
		if(M>>1==N)
		{
			return;
		}
	}
}

int main()
{
	int T;
	int temp;
	
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&N);
		step[0].clear();
		step[1].clear();
		scanf("%d",&M);
		while(M--)
		{
			scanf("%d",&temp);
			step[0].push_back(temp);
		}
		scanf("%d",&M);
		while(M--)
		{
			scanf("%d",&temp);
			step[1].push_back(temp);
		}
		for(int i=0;i<N;i++)
		{
			ans[i][0].NO=i;
			ans[i][0].F=true;
			ans[i][0].Statu=0;
			deg[i][0]=0;
			visited[i][0]=false;
			ans[i][1].NO=i;
			ans[i][1].F=false;
			ans[i][1].Statu=0;
			deg[i][1]=0;
			visited[i][1]=false;
		}
		ans[0][0].Statu=2;
		ans[0][1].Statu=2;
		visited[0][0]=true;
		visited[0][1]=true;
		M=2;
		bfs();
		for(int i=1;i<N;i++)
		{
			printf("%s%c",str[ans[i][0].Statu],i==N-1?'\n':' ');
		}
		for(int i=1;i<N;i++)
		{
			printf("%s%c",str[ans[i][1].Statu],i==N-1?'\n':' ');
		}
	}
	
	return 0;
}

上一题

© 2024 nowcoder.com