Two Sets（并查集分类）-白红宇

Two Sets（并查集分类）

阅读量：5076 次

发布时间：2019-06-12

本文共 2222 字，大约阅读时间需要 7 分钟。

　　　　http://codeforces.com/group/1EzrFFyOc0/contest/469/problem/D

　　题意：给n个互不相同的数以及两数a，b，有两个类A，B。

　　　　　对于n个数中的任意数x，若x在A中，a-x也必在A中；若x在B中，b-x也必在B中。试问这组数满足上述条件否？若满足则输出YES，并说明第i个数属于第几类（类别用0,1表示）；若不满足，则输出NO。

　　　　　样例：4 5 9　　　　　　YES

　　　　　　　　2 3 4 5　　　　　0 0 1 1

　　　　　　　　3 3 4　　　　　　NO

　　　　　　　　1 2 4

　　题解：该题可用并查集解，由于x的范围过大，先用map离散化一下。

　　　　　我们将类A的其中一个叶子定为n+1,类B其中一个叶子定为n+2。

　　对于任意的c[i]:

　　　　　　若a-c[i]存在，则c[i]和a-c[i]必在同一类中但不知道在哪个类中。

　　　　　　很好想，若c[i]在A中，则a-c[i]必须也在A中和c[i]配对；若c[i]在B中，a-c[i]若在A中，则不存在与其配对的c[i]（n个数各不相同），则该情况不可能存在，即a-c[i]也在B中。

　　　　　　若a-c[i]不存在，则c[i]只可能在B中。

　　　　　　对于b-c[i]存在的讨论同理，若b-c[i]存在，则其与c[i]在同一集合，若不存在，则c[i]可能在A中。

　　若满足条件，A,B两棵树应该无交集，即find(n+1)!=find(n+2)。对于每个c[i]，只需要看find(c[i])等于find(n+1)还是find(n+2)从而得出其在哪个类中。

　　若不满足，直接输出NO即可。

满足条件时：

AC代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
             9 #include
             
              10 #define inf int(0x3f3f3f3f)11 #define pi acos(-1.0)12 #define lson l,m,rt<<113 #define rson m+1,r,rt<<1|114 #define ll long long15 #define MAXN 10000516 using namespace std;17 18 19 int n,a,b;20 int c[MAXN];21 int fa[MAXN];22 23 map
              
                mp;24 25 void Init()26 {27 for(int i=1;i<=n+2;i++)28 fa[i]=i;29 }30 31 int findfa(int x)32 {33 if(fa[x]==x)return x;34 fa[x]=fa[fa[x]];35 36 return findfa(fa[x]);37 }38 39 void Unit(int x,int y)40 {41 x=findfa(x);42 y=findfa(y);43 if(x==y)return ;44 45 fa[y]=x;46 }47 48 49 int main()50 {51 scanf("%d%d%d",&n,&a,&b);52 53 for(int i=1;i<=n;i++)54 {55 scanf("%d",&c[i]);56 mp[c[i]]=i;//离散化57 }58 59 Init();60 for(int i=1;i<=n;i++)61 {62 if(mp[a-c[i]])63 Unit(mp[c[i]],mp[a-c[i]]);//同一集合中，相连接64 else65 Unit(mp[c[i]],n+1);//只可能在B中，踢到B树去66 67 if(mp[b-c[i]])68 Unit(mp[c[i]],mp[b-c[i]]);69 else70 Unit(mp[c[i]],n+2);//踢到A树去71 }72 73 //若a-c[i]与b-c[i]都不存在 则AB树相连了74 75 if(findfa(n+1)==findfa(n+2))76 {77 printf("NO\n");78 return 0;79 }80 81 printf("YES\n");82 83 for(int i=1;i<=n;i++)84 {85 if(findfa(mp[c[i]])==findfa(n+1))86 printf("1 ");87 else if(findfa(mp[c[i]])==findfa(n+2))88 printf("0 ");89 else//1 2 2 1 即c[i]在A,B中都满足90 printf("1 ");91 92 }93 94 return 0;95 }

转载于:https://www.cnblogs.com/reminito/p/8504851.html

你可能感兴趣的文章