AcWing 258. 石头剪子布

如果找到裁判，但裁判的人选多于 1 个，则输出 Can not determine。

如果根据输入推断的结果是必须没有裁判或者必须有多个裁判，则输出 Impossible。

具体格式可参考样例。

数据范围
1≤N≤500,
0≤M≤2000

输入样例：
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

思路：

        这一题一共又三种情况，石头、剪刀、布，并且题目中明确告诉我们，除了裁判外，每个人都是固定的种类，然后每个人会相互存在大小关系，比如A>B,B>C,那么根据游戏规则我们肯定可以知道C>A，分三种情况，因此可以用带权并查集。

        然后本题还有一个裁判机制，裁判可以随便出，对于一个有裁判在的对局，由于裁判可以随便出，所以时可能照成矛盾的，但是除了裁判所在对局的其他对局，关系都是合法的。

       

        因此我们可以枚举所有人去找裁判。

        对于每个人，枚举不包括这个人的对局

        1.如果这些对局都是合法的，说明这个人可能时裁判，裁判人数+1

        2.如果遇到第一个不合法的对局，说明这个人不是裁判，这时候需要记录这是第几局，因为一直到这一局，是判断这个人不是裁判的依据

       

        最终会得出可能的裁判人数：

        1.裁判人数>1 ，可能有多个裁判，输出不确定

        2.裁判人数=1 ，只有一个裁判，需要输出裁判的编号和最早确定他是裁判的轮数，我们需要确定其他所有人不是裁判才能确定当前人是裁判。 因此需要枚举其他所有不是裁判的人，从最早判断它们不是裁判的轮数中取一个最大值，就是最早能排除其他人确定当前人是裁判的位置。

        3.裁判人数=0 没有裁判，输出没有

        代码：

#include
 
using namespace std;
 
const int N=1e5+10;
 
int n,m;
 
int p[N],d[N];
 
bool st[N];//记录每个人是否是裁判
 
int f[N];//记录第i个人最早判定不是裁判的轮数
 
int a[N],b[N];// 第i轮对局是谁对谁
char c[N];//记录第i局对局的关系
 
int find(int x) {
	if(x!=p[x]) {
		int root=find(p[x]);
		d[x]+=d[p[x]];
		d[x]%=3;
		p[x]=root;
	}
 
	return p[x];
}
 
bool check(int k) { //判断第k轮对局是否合法
 
	int x=a[k],y=b[k];//首先取出两人编号
 
	int t=1;//记录大小关系，><是1，=是0
	if(c[k]=='=')t=0;
	if(c[k]=='>')swap(x,y);//保证x
 
	int px=find(x),py=find(y);
 
	if(px==py) { //在同一集合，判断是否合法
		if((d[x]-d[y]+3)%3!=t) {
			//说明不合法
			return false;
		}
	} else {
		//说明不在同一集合
		p[px]=py;
		d[px]=(t+d[y]-d[x]+3)%3;
	}
 
	return true;
}
 
int main() {
	while(cin>>n>>m) {
		//读入操作人，和操作次数
 
		for(int i=1; i<=m; i++) {
			cin>>a[i]>>c[i]>>b[i];
		}
 
		memset(f,0,sizeof f);//初始化每个人判定不是裁判的轮数
 
		int cnt=0,num=0;//cnt表示可能是裁判的人数，num表示裁判编号
 
		for(int i=0; i//枚举所有人
			for(int j=0; j0;//初始化并查集和关系
 
			bool flag=true;//判断当前人是否可能是裁判
 
			for(int j=1; j<=m; j++) { //枚举对局
				if(a[j]!=i&&b[j]!=i&&!check(j)) {
					//cout<
					//不符合题意的对局，说明这个人不是裁判
					flag=false;
					f[i]=j;
					break;
				}
			}
 
			if(flag) { //说明这个人可能是裁判
				cnt++;
				num=i;
			}
		}
 
		if(!cnt)puts("Impossible"); //没有裁判
		else if(cnt>1)puts("Can not determine"); //多个裁判
		else {
			int res = 0; //记录最早能确定裁判的轮数
			for(int i = 0; i < n; i++) //枚举所有人
				if(i != num) //如果当前人不是裁判
					res = max(res, f[i]); //更新最早确定轮数
			printf("Player %d can be determined to be the judge after %d lines\n", num, res);
		}
	}
	return 0;
}