15167集合问题

题目描述 

给你a,b和n个数p[i]，问你如何分配这n个数给A,B集合，并且满足：

若x在集合A中，则a-x必须也在集合A中。

若x在集合B中，则b-x必须也在集合B中。

输入描述:

第一行 三个数 n a b 1<=n<=1e5 1<=a,b<=1e9 第二行 n个数 p1 p2 p3...pn 1<=pi<=1e9

输出描述:

如果可以恰好分开就输出第一行 YES 然后第二行输出 n个数 分别代表pi 是哪个集合的 0 代表是A集合 1代表是B 集合 不行就输出NO 放在哪个集合都可以的时候优先放B

输入

4 5 9 2 3 4 5

输出

YES 0 0 1 1

输入

3 3 4 1 2 4

输出

NO

解题思路：并查集

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<map> using namespace std; map<int,int>mp; int a[100010]; int f[100010]; int getf(int v) { if(f[v]==v) return v; else { f[v]=getf(f[v]); return f[v]; } } void merge(int x,int y) { int t1=getf(x); int t2=getf(y); if(t1!=t2) f[t2]=t1; } int main() { int n,A,B; scanf("%d%d%d",&n,&A,&B); int ma=0; for(int i=1; i<=n; i++) { scanf("%d",&a[i]); mp[a[i]]=i; ma=max(ma,a[i]); } if(ma>max(A,B)) printf("No\n"); else { for(int i=0; i<=n+1; i++) f[i]=i; for(int i=1; i<=n; i++) { if(mp[B-a[i]])//B-a[i]存在 merge(i,mp[B-a[i]]);//合并序号i和mp[B-a[i]]的序号 else merge(i,0);//如果B-a[i]不存在,放到和0一个集合中，即放到A集合里面 if(mp[A-a[i]]) merge(i,mp[A-a[i]]);//A-a[i]存在合并序号i和mp[A-a[i]]的序号 else merge(i,n+1);//如果A-a[i]不存在，放到和n+1一个集合中，即放到B集合中 } // for(int i=0;i<=n;i++) // printf("%d>>>>\n",f[i]); //1>>>> //1>>>> //3>>>> //3>>>> int fa=getf(0); int fb=getf(n+1); if(fa==fb)//如果一个数存在两个集合中,则与题意矛盾 { printf("NO\n"); } else { printf("YES\n"); for(int i=1; i<=n; i++) { if(i!=1) printf(" "); int ff=getf(i); if(ff==fa) printf("0"); else//*****不可以用else if(ff==fb),虽然把mp[B-a[i]]存在的情况和i进行了合并 //但是并不代表一定与n+1进行了合并。。。 printf("1"); } printf("\n"); } } return 0; }