列表

详情

NC51137. Rochambeau

描述

N children are playing Rochambeau (scissors-rock-cloth) game with you. One of them is the judge. The rest children are divided into three groups (it is possible that some group is empty). You don’t know who is the judge, or how the children are grouped. Then the children start playing Rochambeau game for M rounds. Each round two children are arbitrarily selected to play Rochambeau for one once, and you will be told the outcome while not knowing which gesture the children presented. It is known that the children in the same group would present the same gesture (hence, two children in the same group always get draw when playing) and different groups for different gestures. The judge would present gesture randomly each time, hence no one knows what gesture the judge would present. Can you guess who is the judge after after the game ends? If you can, after how many rounds can you find out the judge at the earliest?

输入描述

Input contains multiple test cases. Each test case starts with two integers N and M  in one line, which are the number of children and the number of rounds. Following are M lines, each line contains two integers in [0, N) separated by one symbol. The two integers are the IDs of the two children selected to play Rochambeau for this round. The symbol may be “=”, “>” or “<”, referring to a draw, that first child wins and that second child wins respectively.

输出描述

There is only one line for each test case. If the judge can be found, print the ID of the judge, and the least number of rounds after which the judge can be uniquely determined. If the judge can not be found, or the outcomes of the M rounds of game are inconsistent, print the corresponding message.

示例1

输入: 

3 3
0<1
1<2
2<0
3 5
0<1
0>1
1<2
1>2
0<2
4 4
0<1
0>1
2<3
2>3
1 0

输出: 

Can not determine
Player 1 can be determined to be the judge after 4 lines
Impossible
Player 0 can be determined to be the judge after 0 lines

原站题解

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

C++14(g++5.4) 解法, 执行用时: 58ms, 内存消耗: 376K, 提交时间: 2019-11-06 08:08:57 

//Author:XuHt
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 2006;
int n, m, a[N], b[N], fa[N], d[N], p[N];
char c[N];

int get(int x) {
	if (fa[x] == x) return x;
	int root = get(fa[x]);
	d[x] = (d[x] + d[fa[x]]) % 3;
	return fa[x] = root;
}

bool work(int x, int y, int k) {
	int fx = get(x), fy = get(y);
	if (fx == fy) {
		if (k == 0 && d[x] != d[y]) return 0;
		if (k == 1 && (d[x] + 1) % 3 != d[y]) return 0;
		return 1;
	}
	fa[fy] = fx;
	d[fy] = (d[x] - d[y] + 3 + k) % 3;
	return 1;
}

bool pd(int x) {
	if (c[x] == '=' && !work(a[x], b[x], 0)) return 1;
	if (c[x] == '<' && !work(a[x], b[x], 1)) return 1;
	if (c[x] == '>' && !work(b[x], a[x], 1)) return 1;
	return 0;
}

void Rochambeau() {
	for (int i = 0; i < m; i++)
		scanf("%d%c%d", &a[i], &c[i], &b[i]);
	memset(p, 0, sizeof(p));
	int cnt = 0, num = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) fa[j] = j;
		memset(d, 0, sizeof(d));
		bool flag = 0;
		for (int j = 0; j < m; j++)
			if (a[j] != i && b[j] != i && pd(j)) {
				flag = 1;
				if (j > p[i]) p[i] = j + 1;
				break;
			}
		if (!flag) {
			num = i;
			++cnt;
		}
	}
	if (!cnt) puts("Impossible");
	else if (cnt == 1) {
		int ans = 0;
		for (int i = 0; i < n; i++)
			if (i != num && p[i] > ans)
				ans = p[i];
		printf("Player %d can be determined to be the judge after %d lines\n", num, ans);
	} else puts("Can not determine");
}

int main() {
	while (cin >> n >> m) Rochambeau();
	return 0;
}

C++(clang++11) 解法, 执行用时: 71ms, 内存消耗: 408K, 提交时间: 2020-11-20 21:53:05 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510,M=2010;
int n,m,num,fa[N<<2];
struct Node{
	int a,b;
	char ch;
}c[M];
int getfa(int x){
	if(x==fa[x])
		return x;
	return fa[x]=getfa(fa[x]);
}
void Merge(int x,int y){
	int fx=getfa(x),fy=getfa(y);
	fa[fx]=fy;
}
bool pd(int p){
	for(int i=1;i<=m;i++){
		int x=c[i].a,y=c[i].b;
		if(x==p||y==p)
			continue;
		int xw=x+n,xl=x+2*n,yw=y+n,yl=y+2*n;
		if(c[i].ch=='>'){
			if(getfa(x)==getfa(y)||getfa(xl)==getfa(y)){
				num=max(num,i);
				return false;
			}
			Merge(xw,y),Merge(yl,x),Merge(xl,yw);
		}
		else if(c[i].ch=='='){
			if(getfa(xl)==getfa(y)||getfa(xw)==getfa(y)){
				num=max(num,i);
				return false;
			}
			Merge(x,y),Merge(xw,yw),Merge(xl,yl);
		}
		else{
			if(getfa(xw)==getfa(y)||getfa(x)==getfa(y)){
				num=max(num,i);
				return false;
			}
			Merge(xl,y),Merge(yw,x),Merge(xw,yl);
		}
	}
	return true;
}
int main(){
	while(cin>>n>>m){
		for(int i=0;i<3*n;i++)
			fa[i]=i;
		for(int i=1;i<=m;i++)
			cin>>c[i].a>>c[i].ch>>c[i].b;
		int cnt=0,ans;
		num=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<3*n;j++)
				fa[j]=j;
			if(pd(i))
				cnt++,ans=i;
		}
		if(cnt>1)
			cout<<"Can not determine"<<endl;
		else if(cnt==1)
			cout<<"Player "<<ans<<" can be determined to be the judge after "<<num<<" lines"<<endl;
		else
			cout<<"Impossible"<<endl;
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 28ms, 内存消耗: 512K, 提交时间: 2023-07-28 20:22:54 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define endl "\n"
using namespace std;
#define N 1000010

struct node{
	int fa,re;//0平1赢2输 
}p[N];

int n,q,m,l[N],k,vis[N],pla,jud,num,a[N],b[N],d[N],s1,s2,s3;
char s[N]; 

int root(int x){
	if(x==p[x].fa)return x;
	int tmp=p[x].fa;
	p[x].fa=root(tmp);
	p[x].re=(p[tmp].re+p[x].re)%3;
	return p[x].fa;
}


signed main(){
 	ios::sync_with_stdio(0);
	cin.tie(0);
	while(cin>>n>>m){
		for(int i=1;i<=m;i++){
			char c;
			cin>>a[i]>>c>>b[i];
			if(c=='=')d[i]=0;
			if(c=='>')d[i]=1;
			if(c=='<')d[i]=2;
		}
		if(n==1){
			cout<<"Player 0 can be determined to be the judge after 0 lines"<<endl;
			continue;
		}
		int num=0,ron=0;
		for(int o=0;o<n;o++){
			int k=1;
			for(int i=0;i<=n;i++)p[i].fa=i,p[i].re=0,vis[i]=0;
			for(int i=1;i<=m;i++){
				int x=a[i],y=b[i],w=d[i];
				if(x==o||y==o)continue;
				int ra=root(x),rb=root(y);
				if(ra!=rb){
					p[ra].fa=rb;
					p[ra].re=(p[y].re+w-p[x].re+3)%3;
				}else{
					if(p[x].re!=(w+p[y].re)%3){
						ron=max(ron,i);
						k=0	;	
						break;				
					}
				}
			}
			num+=k;
			if(k==1)pla=o;
		}
		if(num==1)cout<<"Player "<<pla<<" can be determined to be the judge after "<<ron<<" lines";
		else if(num==0)cout<<"Impossible";
		else cout<<"Can not determine";
		cout<<endl;
	}
	return 0;
}

上一题

© 2024 nowcoder.com