258. 石头剪子布

题意挺好理解，但是当我看样例的时候就傻了。不是说好的只有一个裁判的吗？出现矛盾的时候该怎么判定裁判？

分析

观察这个数据量就会发觉是有猫腻的，直接从正面求出裁判并不是很容易，那么直接枚举裁判呢？由于裁判是可以随便出的，那么把它从所有对局中除去后理应没有矛盾才对。所以就有了如下做法

枚举裁判，从前往后遍历对局，按照并查集例题食物链的做法去处理就行。可能遇到的情况有下面两种
1. 直到发现第一个矛盾，那么当前枚举的这个人就不应该是裁判。然后把当前对局标号记录下来，表示最早到该对局时可以发现裁判并不是当前枚举的这个人。
2. 从头到尾没有矛盾，那么这个人可能就是裁判，答案结果数+1
如果答案结果数大于1，表示可能的裁判有很多种，输出 Can not determine
如果答案结果数为1，要输出排除其他所有不可能是裁判的人最小的对局号
如果答案结果数为0，表示没有裁判，输出 Impossible

const int N = 505;

const int M = 2020;

struct node{

    int a,b,c;

}q[M];

int fa[N*3],n,m,last[N];

int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}

//判断是否有矛盾

bool conflict(int j){

    int a = q[j].a, b = q[j].b, c = q[j].c;

    if(c == 0){

        if(find(a) == find(b+n) || find(a) == find(b+2*n))return true;

        fa[find(a)] = find(b);

        fa[find(a+n)] = find(b+n);

        fa[find(a+2*n)] = find(b+2*n);

    }else if(c == 1){//a<b

        if(find(a) == find(b) || find(a) == find(b+n))return true;

        fa[find(a+2*n)] = find(b+n);

        fa[find(a)] = find(b+2*n);

        fa[find(a+n)] = find(b);

    }else{

        if(find(a) == find(b) || find(a) == find(b+2*n))return true;

        fa[find(a+2*n)] = find(b);

        fa[find(a+n)] = find(b+2*n);

        fa[find(a)] = find(b+n);

    }

    return false;

}

int main()

{

    while(~scanf("%d%d",&n,&m)){

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

            char ch;

            scanf("%d%c%d",&q[i].a,&ch,&q[i].b);

            if(ch == '=')q[i].c = 0;

            else if(ch == '<')q[i].c = 1;

            else q[i].c = 2;

            q[i].a++;q[i].b++;

        }

        //last数组存放最早的矛盾对局号，如果循环结束后还是-1表示枚举的人可以是裁判

        memset(last,-1,sizeof last);

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

            for(int j=1;j<=n*3;j++)fa[j]=j;

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

                if(q[j].a == i || q[j].b == i)continue;

                if(conflict(j)){

                    last[i] = j;

                    break;

                }

            }

        }

        int cnt = 0, id = 1, times = 0;

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

            if(last[i] == -1){

                cnt ++;

                id = i;

            }

            times = max(times,last[i]);

        }

        //cout << cnt << endl;

        if(cnt > 1)puts("Can not determine");

        else if(cnt == 1)printf("Player %d can be determined to be the judge after %d lines\n",id-1,times);

        else puts("Impossible");

    }

    return 0;

}

最后感谢题解区的各位大佬

巴特西

ACwing 258. 石头剪子布

258. 石头剪子布

分析

最新文章

热门文章