2 条题解

  • 0
    @ 2026-3-16 20:42:08

    直接给我掉!

    有心了

    #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;
    }
    
    • -2
      @ 2024-5-26 15:24:48

      g'g'f'd'g'd

      • 1

      信息

      ID
      169
      时间
      1000ms
      内存
      128MiB
      难度
      10
      标签
      递交数
      3
      已通过
      1
      上传者