专栏文章

题解：P10686 Rochambeau

mmyxRUC
P10686题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miofzu66
此快照首次捕获于
2025/12/02 18:35
3 个月前
此快照最后确认于
2025/12/02 18:35
3 个月前
查看原文

思路

作为经典的并查集问题，按照剪刀石头布分为三类，但是本题关键并不在于每个人属于哪一类，而是在于两个人的关系。这个关系我们可以用边权来记，由于规则分为平局和非平局，所以边权很容易用 0、10、1 来表示。因此读入数据的时候我们把输赢统一为一种情况，赢者在后
CPP
for (int i = 1; i <= m; i++) {
	cin >> pl[i].a >> pl[i].c >> pl[i].b;
	if (pl[i].c == '>') {
		swap(pl[i].a, pl[i].b);//交换顺序
	}
}
所以对于每个人，先初始化，（dd 作为到达根节点的距离，很好的衡量两个人的胜负或者平局关系）
CPP
for (int i = 1; i <= n; i++)f[i] = i;
memset(d, 0, sizeof(d));//d表示到根节点的距离
当我们考虑每组数据的时候，由于 NN 不超过 500500,不妨枚举每个人作为裁判，然后判断 MM 次游戏结果存不存在矛盾，（遇到裁判参与游戏就跳过，因为情况一定合理，裁判可以随意出），如果存在，说明这个人不是裁判；否则是裁判。
并查集函数
CPP
int dfs(int x) {
	if (x == f[x])return f[x];
	int t = dfs(f[x]);
	d[x] = d[x] + d[f[x]];
	return f[x] = t;
}
下面讨论对每局游戏的判断，假设是 x1x1 和 x2x2，递归寻找 x1x1 和 x2x2 所属的集合，并根据 x1x1 和 x2x2 的关系确定距离 disdis。
CPP
int x1=pl[i].a, x2=pl[i].b, dis = 0;
char c=pl[i].c;
if (x1 == k || x2 == k)continue;//裁判参与就不判断，因为一定不矛盾
int a = dfs(x1), b = dfs(x2);
if (c == '<'||pl[i].c=='>')dis = 1;
if (c == '=')dis = 0;
下面判断两种情况，就是两个人在不在一个集合以内
CPP
if (a == b)
{
      if (((d[x1] - d[x2]) % 3 + 3) % 3 != dis){
        ok = false;
        tp = min(tp, i);//记录判断裁判的位置
      }
}
else
{
      f[a] = b;
      d[a] = ((d[x2] - d[x1] + dis) % 3 + 3) % 3;
}

代码

CPP
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 505, M = 2005;
int f[N], d[N];
int cnt = 0, n = 0, m = 0;
struct node {
	int a, b;
	char c;
}pl[M];
int dfs(int x) {
	if (x == f[x])return f[x];
	int t = dfs(f[x]);
	d[x] = d[x] + d[f[x]];
	return f[x] = t;
}
int main(void) {
	while (cin >> n >> m) {
		int cnt = 0, num = 0, tp = 0, pos = 0;
		if (n == 1 && m == 0) {
			num = 0, pos = 0;
		}
		for (int i = 1; i <= m; i++) {
			cin >> pl[i].a >> pl[i].c >> pl[i].b;
			if (pl[i].c == '>') {
				swap(pl[i].a, pl[i].b);
			}
		}
		for (int k = 0; k < n; k++) {
			tp = 2001;
			for (int i = 0; i < n; i++)f[i] = i;
			memset(d, 0, sizeof(d));
			bool ok = true;
			for (int i = 1; i <= m; i++) {
				int x1=pl[i].a, x2=pl[i].b, dis = 0;
				char c=pl[i].c;
				if (x1 == k || x2 == k)continue;
				int a = dfs(x1), b = dfs(x2);
				if (c == '<'||c=='>')dis = 1;
				if (c == '=')dis = 0;
				if (a == b) {
					if (((d[x1] - d[x2]) % 3 + 3) % 3 != dis) {
						ok = false;
						tp = min(tp, i);
					}
				}
				else {
					f[a] = b;
					d[a] = ((d[x2] - d[x1] + dis) % 3 + 3) % 3;
				}
			}
			if (tp == 2001) cnt++, num = k;
			else pos = max(pos, tp);
		}
		if (cnt == 0) {
			cout << "Impossible" << endl;
		}
		else if (cnt > 1) {
			cout << "Can not determine" << endl;
		}
		else {
			cout << "Player " << num << " can be determined to be the judge after " << pos << " lines\n";
		}
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...