2 条题解
-
0
直接给我掉!
有心了
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 510, M = 2010; int n, m; int p[N], d[N]; int a[M], b[M], op[M]; // 存储输入数据 int find(int x) { if (p[x] != x) { int root = find(p[x]); d[x] = (d[x] + d[p[x]]) % 3; p[x] = root; } return p[x]; } int main() { while (cin >> n >> m) { for (int i = 0; i < m; i++) { char c; cin >> a[i] >> c >> b[i]; if (c == '=') op[i] = 0; else if (c == '<') op[i] = 1; // a < b 表示 a 输给 b else op[i] = 2; // a > b 表示 a 赢 b } int judge = -1, max_line = 0; int cnt = 0; // 可能为裁判的人数 // 枚举假设裁判 for (int i = 0; i < n; i++) { // 初始化并查集 for (int j = 0; j < n; j++) p[j] = j; memset(d, 0, sizeof d); int line = 0; // 记录发生矛盾的轮数(如果发生) for (int k = 0; k < m; k++) { int x = a[k], y = b[k]; if (x == i || y == i) continue; // 跳过涉及裁判的轮次 int fx = find(x), fy = find(y); if (fx == fy) { // 同根,检查关系是否矛盾 if ((d[x] - d[y] + 3) % 3 != op[k]) { line = k + 1; // 记录矛盾轮数(从1开始计) break; } } else { // 合并 p[fx] = fy; d[fx] = (d[y] - d[x] + op[k] + 3) % 3; } } if (line == 0) { // 假设 i 是裁判没有矛盾 cnt++; judge = i; } else { // 记录排除其他候选人的最大轮数 max_line = max(max_line, line); } } // 输出结果 if (cnt == 0) { cout << "Impossible" << endl; } else if (cnt > 1) { cout << "Can not determine" << endl; } else { cout << "Player " << judge << " can be determined to be the judge after " << max_line << " lines" << endl; } } return 0; }
- 1
信息
- ID
- 169
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者