ACWing 258 石头剪子布

题意简述

现在有(n)个小朋友,已经分成了三份(你并不知道是怎么分的)和一个裁判,每个组里的小朋友都只能出单一的“石头”,或“剪刀”,或“布”,而裁判可以任意出。现在给你(m)个对局情况,求出那个裁判。若裁判人选有多个,则输出Can not determine,若必须没有裁判或多余两个裁判,输出Impossible,否则输出裁判和最早能判断裁判的轮数

简单口胡

很容易想到扩展域并查集,将每个小朋友分成三个,一个是他本身(itself),一个是他赢了的(win),一个是他输了的(lose),维护三个并查集,根据(m)个对局情况分类讨论维护。
定义如下:

胜负(<,=,>) (opt)
< 0
= 1
> 2
集合 对应标号
(itself_x) (x)
(win_x) (x + n)
(lose_x) (x + 2n)
int Go_solve(int _f,bool optx = 1)
{
    bool flag = 1;
    for(int i = 1; i <= 3 * n; i++) f[i] = i;
    for(int i = 1; i <= m; i++)
    {
        if(a[i].x == _f || a[i].y == _f && optx) continue;
        if(a[i].opt == 0) // x < y
        {
            if(find(a[i].x) == find(a[i].y) || find(a[i].x + n) == find(a[i].y)) 
            {
                if(optx == 1) lst[_f] = i;
                if(optx == 0 && (a[i].x == _f || a[i].y == _f)) return i;
                else {flag = 0;break;}
            }
            f[find(a[i].x)] = find(a[i].y + n);
            f[find(a[i].x + n)] = find(a[i].y + 2 * n);
            f[find(a[i].x + 2 * n)] = find(a[i].y);
        }
        else if(a[i].opt == 1)
        {
            if(find(a[i].x + n) == find(a[i].y) || find(a[i].x + 2 * n) == find(a[i].y)) 
            {
                if(optx == 1) lst[_f] = i;
                if(optx == 0 && (a[i].x == _f || a[i].y == _f)) return i;
                else {flag = 0;break;}
            }
            f[find(a[i].x)] = find(a[i].y);
            f[find(a[i].x + n)] = find(a[i].y + n);
            f[find(a[i].x + 2 * n)] = find(a[i].y + 2 * n);
        }
        else if(a[i].opt == 2)
        {
            if(find(a[i].x) == find(a[i].y) || find(a[i].x + 2 * n) == find(a[i].y))  
            {
                if(optx == 1) lst[_f] = i;
                if(optx == 0 && (a[i].x == _f || a[i].y == _f)) return i;
                else {flag = 0;break;}
            }
            f[find(a[i].x)] = find(a[i].y + 2 * n);
            f[find(a[i].x + n)] = find(a[i].y);
            f[find(a[i].x + 2 * n)] = find(a[i].y + n);
        }
    }
    if(optx == 0) return m;
    return flag;
}

并进行处理。
对于求解最早知道是裁判的轮数,可以转变为“将别的不是裁判的都排除掉”,记录下对于每个(i)的情况的最早的出现情况的数(lst_i),并取最大值。

# include <bits/stdc++.h>
using namespace std;

const int N = 505,M = 2005;

int n,m;

struct node
{
    int x,y,opt;
}a[M];

int f[N * 3];

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

int lst[N];

int Go_solve(int _f,bool optx = 1)
{
    bool flag = 1;
    for(int i = 1; i <= 3 * n; i++) f[i] = i;
    for(int i = 1; i <= m; i++)
    {
        if(a[i].x == _f || a[i].y == _f && optx) continue;
        if(a[i].opt == 0) // x < y
        {
            if(find(a[i].x) == find(a[i].y) || find(a[i].x + n) == find(a[i].y)) 
            {
                if(optx == 1) lst[_f] = i;
                if(optx == 0 && (a[i].x == _f || a[i].y == _f)) return i;
                else {flag = 0;break;}
            }
            f[find(a[i].x)] = find(a[i].y + n);
            f[find(a[i].x + n)] = find(a[i].y + 2 * n);
            f[find(a[i].x + 2 * n)] = find(a[i].y);
        }
        else if(a[i].opt == 1)
        {
            if(find(a[i].x + n) == find(a[i].y) || find(a[i].x + 2 * n) == find(a[i].y)) 
            {
                if(optx == 1) lst[_f] = i;
                if(optx == 0 && (a[i].x == _f || a[i].y == _f)) return i;
                else {flag = 0;break;}
            }
            f[find(a[i].x)] = find(a[i].y);
            f[find(a[i].x + n)] = find(a[i].y + n);
            f[find(a[i].x + 2 * n)] = find(a[i].y + 2 * n);
        }
        else if(a[i].opt == 2)
        {
            if(find(a[i].x) == find(a[i].y) || find(a[i].x + 2 * n) == find(a[i].y))  
            {
                if(optx == 1) lst[_f] = i;
                if(optx == 0 && (a[i].x == _f || a[i].y == _f)) return i;
                else {flag = 0;break;}
            }
            f[find(a[i].x)] = find(a[i].y + 2 * n);
            f[find(a[i].x + n)] = find(a[i].y);
            f[find(a[i].x + 2 * n)] = find(a[i].y + n);
        }
    }
    if(optx == 0) return m;
    return flag;
}

int main(void)
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i = 1; i <= m; i++)
        {
            int ax = 0,bx = 0;
            int k = 0;
            char s[10];
            scanf("%s",s);
            while(isdigit(s[k]))
            {
                ax = ax * 10 + s[k] - '0';
                ++k;
            }
            if(s[k] == '<') a[i].opt = 0;
            else if(s[k] == '=') a[i].opt = 1;
            else if(s[k] == '>') a[i].opt = 2;
            ++k;
            while(isdigit(s[k]))
            {
                bx = bx * 10 + s[k] - '0';
                ++k;
            }
            a[i].x = ax + 1,a[i].y = bx + 1;
        }
        for(int i = 1; i <= 3 * n; i++)
        {
            f[i] = i;        
        }
        /*
        x           itself
        x + n       win
        x + 2 * n   lose
        */
        vector <int> A;
        for(int i = 1; i <= n; i++) lst[i] = 0;
        for(int i = 1; i <= n; i++) // 裁判
        {
            if(Go_solve(i)) 
            {
                A.push_back(i);
            }
        }
        if(A.size() == 0) 
        {
            printf("Impossible
");
        }
        else 
        {
            if(A.size() >= 2)
            {
                printf("Can not determine
");
            }
            else
            {
                int cur = 0;
                for(int i = 1; i <= n; i++)
                {
                    cur = max(cur,lst[i]);
                }
                printf("Player %d can be determined to be the judge after %d lines
",A[0] - 1,cur);
            }
        }
    }
    
    return 0;
}
原文地址:https://www.cnblogs.com/luyiming123blog/p/14711436.html