题解 | #集合问题#

题目描述

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

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

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

思路

因为p[i]是正数，所以一定要小于max(a,b)

用map<ll,ll> mp记录p[i]的下标 i

如果a-p[i]这个数存在，就和i配对，否则令i和n+1配对；

如果b-p[i]这个数存在，就和i配对，否则令i和0配对。

若存在某个数x，既不能放A集合，也不能放B集合，那么两个集合的并查集一定会相交。

因为A B两集合分别和0 n+1连接，所以在对father[ ]初始化的时候，把边界扩展到0-n+1

void init()
{
	for(ll i=0;i<=n+1;i++)
		f[i]=i;
}

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;

ll a,b,n;
ll p[maxn],f[maxn];
map<ll,ll> mp;

void init()
{
	for(ll i=0;i<=n+1;i++)
		f[i]=i;
}
ll find(ll x)
{
	if(x!=f[x]) f[x]=find(f[x]);
	return f[x];
}
void union1(ll a,ll b)
{
	ll fa=find(a);
	ll fb=find(b);
	if(fa!=fb) f[fa]=fb;
}
void solve()
{
	for(ll i=1;i<=n;i++)
	{
		if(mp[b-p[i]]) union1(i,mp[b-p[i]]);
		else union1(i,0);//b集合不能放 就和0连接
		if(mp[a-p[i]]) union1(i,mp[a-p[i]]);
		else union1(i,n+1);
	}
	ll f0=find(0),fn=find(n+1);
	if(f0==fn)//a b都不能放 一定会相交
		printf("NO\n");
	else 
	{	
		printf("YES\n");
		for(ll i=1;i<=n;i++)
		{
			if(find(i)==f0)
				printf("0 ");
			else printf("1 ");
		}
		printf("\n");
	}		
}

int main()
{
	cin>>n>>a>>b;
	ll maxx=0;
	for(ll i=1;i<=n;i++)
	{
		cin>>p[i];
		mp[p[i]]=i;
		maxx=max(maxx,p[i]);
	}
	if(maxx>=max(a,b)) printf("NO\n");
	else {init();solve();}
	return 0;
}