CF468B Two Sets
题意翻译
给出 nn 个各不相同的数字，将它们分别放入 AA 和 BB 两个集合中，使它们满足：
- 若数字 xx 在集合 AA 中，那么数字 a-xa−x 也在集合 AA 中；
- 若数字 xx 在集合 BB 中，那么数字 b-xb−x 也在集合 BB 中。 输入格式：
输入的第一行输入三个整数 n,a,b (1 \leq n \leq 10^{5} ; 1 \leq a,b \leq 10^{9} )n,a,b(1≤n≤105;1≤a,b≤109)。
输入的第二行有 nn 个各不相同的正整数，且每个正整数的数值大小都在 [1,10^{9}][1,109] 内。 输出格式：
若不能能将这 nn 个数在满足条件的情况下全部放入 AA 和 BB 这两个集合中，则输出
NO。若这 nn 个数在满足条件的情况下能被全部放入 AA 和 BB 这两个集合中，则第一行输出
YES，第二行输出 nn 个数 00 或 11 ，第 ii 个数为 00 表示第 ii 个数在集合 AA 中，第 ii 个数为 11 表示第 ii 个数在集合 BB 中。
题解：
很容易看出来这道题最难搞的是冲突的处理，也就是a-x,b-x和x同时存在于原数列的情况。
于是就有了思路（比较清奇，因为是先想到什么东西难搞，然后再回推思路）
也就是：
对于一个\(x\)来说，能分成以下4种情况进行分类讨论：
1.\(a-x\)不存在，\(b-x\)不存在。这种情况直接NO。
2.\(a-x\)存在，\(b-x\)不存在。这种情况是集合A。
3.\(a-x\)不存在，\(b-x\)存在。这种情况是集合B。
4.\(a-x\)存在，\(b-x\)存在。
第四种情况就是着重要讨论的冲突情况。
那么我们接下就需要再找到一个证据来唯一确定这个数的从属集合。也就是：还需要判断是否存在\(y\)有\(a-y=b-x\)或者\(b-y=a-x\)其中之一存在。
如果存在\(a-y=b-x\)，那么就把\(x\)和\(a-x\)和\(y\)和\(a-y(b-x)\)都放到集合A中。同理\(b-y=a-x\)存在的情况。如果都不存在就输出NO。
然后我们采用并查集来维护这个东西。
我还写了个版本是\(set\)直接模拟维护的，但是挂了，，，有兴趣的同学请去讨论区康康，感谢抓虫。
代码：
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int maxx,n,a,b,fa[maxn],val[maxn];
map<int,int> mp;
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
fa[fx]=fy;
}
int main()
{
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;i++)
{
scanf("%d",&val[i]);
mp[val[i]]=i;
maxx=max(maxx,val[i]);
fa[i]=i;
}
fa[0]=0;
fa[n+1]=n+1;
if(maxx>=max(a,b))
{
printf("NO");
return 0;
}
for(int i=1;i<=n;i++)
{
if(mp[a-val[i]]>0)
merge(i,mp[a-val[i]]);
else
merge(i,n+1);
if(mp[b-val[i]]>0)
merge(i,mp[b-val[i]]);
else
merge(i,0);
}
int l=find(0),r=find(n+1);
if(l!=r)
{
puts("YES");
for(int i=1;i<=n;i++)
{
if(i!=1)
printf(" ");
if(find(i)==l)
printf("0");
else
printf("1");
}
}
else
puts("NO");
return 0;
}