打卡信奥刷题（3483）用C++实现信奥题 P10686 Rochambeau

P10686 Rochambeau

题目描述

$N$ 个小朋友（编号为 $0,1,2,\dots ,N-1$）一起玩石头剪子布游戏。

其中一人为裁判，其余的人被分为三个组（有可能有一些组是空的），第一个组的小朋友只能出石头，第二个组的小朋友只能出剪子，第三个组的小朋友只能出布，而裁判可以使用任意手势。

你不知道谁是裁判，也不知道小朋友们是怎么分组的。

然后，孩子们开始玩游戏，游戏一共进行 $M$
轮，每轮从 $N$ 个小朋友中选出两个小朋友进行猜拳。

你将被告知两个小朋友猜拳的胜负结果，但是你不会被告知两个小朋友具体使用了哪种手势。

比赛结束后，你能根据这些结果推断出裁判是谁吗？

如果可以的话，你最早在第几轮可以找到裁判？

输入格式

输入可能包含多组测试用例。

每组测试用例第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行包含两个整数 $a,b$，中间夹着一个符号(>,=,<)，表示一轮猜拳的结果。

两个整数为小朋友的编号，a>b 表示 $a$ 赢了 $b$，a=b 表示 $a$ 和 $b$ 平手，a<b 表示 $a$ 输给了 $b$。

输出格式

每组测试用例输出一行结果。

• 如果有且仅有一个人可能是裁判，则输出 Player x can be determined to be the judge after y lines，其中 $x$ 为裁判编号，$y$ 为确定裁判的最少轮数。

• 如果无法确定裁判是谁，即裁判的人选多于 $1$ 个，则输出 Can not determine。

• 如果在仅有一个裁判的情况下无法完成所有回合，则输出 Impossible。

输入输出样例 #1

输入 #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

输出 #1

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

说明/提示

$1\le N\le 500$，$1\le M\le 2000$。

C++实现

#include<bits/stdc++.h>
using namespace std;
struct pss{
int a,b,f;//0是=,1是<
}gx[2005];
int rlt[501],fa[501],n,k,caipan,cp,md,amd;
int find(int x){
if(fa[x]==x) return x;
else{
int c=find(fa[x]);
rlt[x]=(rlt[x]+rlt[fa[x]])%3;
return fa[x]=c;
}
}
void uni(int x,int y,int rx,int ry,int d){
rlt[ry]=(rlt[x]–rlt[y]+d+3)%3;
fa[ry]=rx;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
while(cin>>n>>k){
for(int i=1,a,b;i<=k;i++){
char qm;
cin>>a>>qm>>b;
if(qm=='=') gx[i]=(pss){a,b,0};
if(qm=='>') gx[i]=(pss){b,a,1};
if(qm=='<') gx[i]=(pss){a,b,1};
}
cp=0,caipan=0,amd=0;
for(int p=0;p<n;p++){
md=2001;
memset(rlt,0,sizeof(rlt));
for(int i=0;i<n;i++) fa[i]=i;
for(int i=1;i<=k;i++){
int d=gx[i].f,x=gx[i].a,y=gx[i].b;
if(x==p||y==p) continue;
int rx=find(x),ry=find(y);
if(rx==ry)
if((rlt[y]–rlt[x]+3)%3!=d){
md=min(md,i);
continue;
}
uni(x,y,rx,ry,d);
}
if(md==2001) caipan++,cp=p;
else amd=max(amd,md);
}
if(caipan==0) cout<<"Impossible\\n";
if(caipan==1) cout<<"Player "<<cp<<" can be determined to be the judge after "<<amd<<" lines\\n";
if(caipan>1) cout<<"Can not determine\\n";
}
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容