poj 2912 Rochambeau（枚举+带权并查集）

题意：多个人玩石头剪刀布分成3组和一个裁判，每一组提前选定了自己出哪个手势，裁判可以随意出什么手势，问是否能够从给出的一系列石头剪刀布游戏中判断出哪个是裁判的，可以从第几局游戏中判断出来。

由于这题的数据量比较小可以枚举一下，枚举一下每一个人假设他们是裁判然后一系列并查集下来看

有没有出现矛盾如果没有那么这个人可能是裁判候补，如果有矛盾那么这个人肯定不是记录一下出现

问题的位置然后继续枚举。位置要去最远的，因为都要判完才知道。如果最后没有矛盾的数目大于2

说明不能确定裁判是谁，如果为0就不可能，其他则是

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int n , m , f[510] , root[510];

struct TnT {

    int x , y;

    char cp;

}node[2010];

void init() {

    for(int i = 0 ; i < n ; i++) {

        f[i] = i , root[i] = 0;

    }

}

int find(int x) {

    if(x == f[x])

        return x;

    int tmp = find(f[x]);

    root[x] = (root[x] + root[f[x]] + 3) % 3;

    return f[x] = tmp;

}

int main() {

    int x , y;

    char s[20] , cp;

    while(scanf("%d%d" , &n , &m) != EOF) {

        for(int j = 1 ; j <= m ; j++) {

            scanf("%s" , s);

            int len = strlen(s) , temp = 0;

            x = 0 , y = 0;

            for(int i = 0 ; i < len ; i++) {

                if(s[i] == '=' || s[i] == '<' || s[i] == '>') {

                    temp = i;

                    cp = s[i];

                    break;

                }

            }

            for(int i = 0 ; i < temp ; i++) {

                x *= 10;

                x += s[i] - '0';

            }

            for(int i = temp + 1 ; i < len ; i++) {

                y *= 10;

                y += s[i] - '0';

            }

            node[j].x = x , node[j].y = y , node[j].cp = cp;

        }

        int count = 0 , pos = 0 , flag = -1 , num = 0;

        for(int i = 0 ; i < n ; i++) {

            flag = -1;

            init();

            for(int j = 1 ; j <= m ; j++) {

                if(node[j].x == i || node[j].y == i)

                    continue;

                x = node[j].x , y = node[j].y , cp = node[j].cp;

                int a = find(x) , b = find(y);

                if(a == b) {

                    if(cp == '=') {

                        if(root[x] != root[y]) {

                            flag = j;

                            break;

                        }

                    }

                    if(cp == '>') {

                        if(root[x] != (root[y] + 2) % 3) {

                            flag = j;

                            break;

                        }

                    }

                    if(cp == '<') {

                        if(root[x] != (root[y] + 1) % 3) {

                            flag = j;

                            break;

                        }

                    }

                }

                else {

                    f[a] = b;

                    if(cp == '=') {

                        root[a] = root[y] - root[x];

                        root[a] = (root[a] + 3) % 3;

                    }

                    if(cp == '>') {

                        root[a] = root[y] - root[x] + 2;

                        root[a] = (root[a] + 3) % 3;

                    }

                    if(cp == '<') {

                        root[a] = root[y] - root[x] + 1;

                        root[a] = (root[a] + 3) % 3;

                    }

                }

            }

            if(flag == -1) {

                num = i;

                count++;

            }

            else

                pos = max(pos , flag);

        }

        if(count == 0) printf("Impossible\n");

        else if(count >= 2) printf("Can not determine\n");

        else

            printf("Player %d can be determined to be the judge after %d lines\n" , num , pos);

    }

    return 0;

}

巴特西

poj 2912 Rochambeau（枚举+带权并查集）

最新文章

热门文章