题目链接

题意：有n（n <= 500）个人玩石头剪刀布， 他们被分成固定的三组（一组只能出石头，另一组只能出剪刀， 最后一组只能出布， 当然也可以为空组）， 然后在这些人中有一个judge， 他可以不受规则约束，想出啥就出啥。
现在给你m组游戏结果， 问你是否能判断出谁是裁判， 输出对应信息。

分析： 我一开始想着要用并查集去做， 和食物链这题类似， 但是却想不到如何找矛盾。
然后搜博客， 发现清一色的暴力 /哭 ，暴力就暴力吧。

按照最后暴力出来的人数：按照题意
0人 ： Impossible
大于1人 ： Can not determine
等于1人： Player %d can be determined to be the judge after %d lines

等于一人的时候就比较复杂了，关键是判断是在第几句话出现的问题， 又一次头大。（按照别人的说法， 是在判断其他人的矛盾的时候， 去那时的一个最大值， 这就有点迷糊了， 等着我真正理解了再来补吧， 哭叽）

还有一点， 三种类看三倍数组

ac代码：（）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
//#include <bits/stdc++.h>
#include <iostream>
#include "algorithm"
#include "cstdio"
#include "queue"
#include "set"
#include "cstring"
#include "string"
#define esp 1e-6
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;
int f[N];

struct node{
    int a, b, f;
}no[N];

int tofind(int x){
    if (f[x] != x)
        f[x] = tofind(f[x]);
    return f[x];
}

void tojoin(int x, int y){
    x = tofind(x);
    y = tofind(y);
    if (x != y)
        f[x] = y;
}
set<int> se;
int main(){
    int n, m;
    int a, b, k;
    char c;
    while(cin >> n >> m){
        for (int i = 0; i <= 3 * n; i++){
            f[i] = i;
        }
        se.clear();
        for (int i = 1; i <= m; i++){
            cin >> a >> c >> b;
            no[i].a = a, no[i].b = b;
            if (c == '=')
                no[i].f = 0;
            else if (c == '>')
                no[i].f = 1;
            else if (c == '<')
                no[i].f = -1;
        }
        int ff = 1, j, pos = 0;
        for (int i = 0; i < n; i++){
            for (j = 0; j <= 3 * n; j++){
                f[j] = j;
            }
            for (j = 1; j <= m; j++){
                a = no[j].a, b = no[j].b, k = no[j].f;
                if (a != i && b != i){
                    /*cout << "i: " << i << "\n" << "a:" << a << "\n" << "b:" << b << "\n";*/
                    if (k == 0){
                        if (tofind(a) == tofind(b + n) || tofind(b) == tofind(a + n)){
                            ff = 0;
                            break;
                        }
                        tojoin(a, b);
                        tojoin(a + n, b + n);
                        tojoin(a + 2 * n, b + 2 * n);
                    }
                    else if (k == 1){
                        if (tofind(a) == tofind(b) || tofind(a + n) == tofind(b)){
                            ff = 0;
                            break;
                        }
                        tojoin(a, b + n);
                        tojoin(a + n, b + 2 * n);
                        tojoin(a + 2 * n, b);
                    }
                    else if (k == -1){
                        if (tofind(a) == tofind(b) || tofind(a) == tofind(b + n)){
                            ff = 0;
                            /*if (i == 1){
                                cout << "*****\n";
                                cout << tofind(a) << ' ' << tofind(b + n) << "\n";
                            }*/
                            break;
                        }
                        tojoin(b, a + n);
                        tojoin(b + n, a + 2 * n);
                        tojoin(b + 2 * n, a);
                    }
                }
            }
            if (ff)
                se.insert(i);
            else
                pos = max(pos, j);
            ff = 1;
        }
        k = se.size();
      /*  set<int>::iterator it;
        for (it = se.begin(); it != se.end(); it++){
            cout << *it << "**\n";
        }*/
        if (k == 0)
            puts("Impossible");
        else if (k > 1)
            puts("Can not determine");
        else if (k == 1){
            printf("Player %d can be determined to be the judge after %d lines\n", *se.begin(), pos);
        }

    }
    return 0;
}
1
恰似你一低头的温柔，较弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan