codeforces #268 div2 D

对于这道题第一感觉是图论相关
然后我们先分析,假设a[i]在A集合需要的元素是a[x],在B集合是a[y]
那么假设a[i]在A集合,那必然a[x]也必须在A集合,由于a[y]如果在B集合就没有对应元素,则a[y]也一定在A集合
同理,当a[i]在B集合,a[x],a[y]一定也要在B集合
对此我们可以分析出,要想有解,那么a[i],a[x],a[y]必定在同一集合
这样我们可以构造出一堆堆团,每个团都只可能在唯一的集合
那这个团属于那个集合呢?假如这个团有一个元素a[j]它有一个不存在对应在A集合的元素,
那么这个团一定是在B集合的,否则反之;
这样我们也很容易想到什么时候无解,那一定是某个团中既存在一个元素不存在对应在A集合的元素,又存在一个元素不存在对应在B集合的元素
所以就很好解决了,我们用n+1,n+2分别表示不存在对应在A集合的元素,不存在对应在B集合的元素
不难想到用并查集维护团,然后搞定(其实不难,可惜现场nc没想出来)

 var ans,a,fa,c:array[..] of longint;
p,q,x,i,n:longint; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; function getf(x:longint):longint;
begin
if fa[x]<>x then fa[x]:=getf(fa[x]);
exit(fa[x]);
end; procedure sort(l,r: longint);
var i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) shr ];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if not(i>j) then
begin
swap(a[i],a[j]);
swap(c[i],c[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; function find(x:longint):longint;
var l,r,m:longint;
begin
l:=;
r:=n;
while l<=r do
begin
m:=(l+r) shr ;
if a[m]=x then exit(m);
if a[m]>x then r:=m-
else l:=m+;
end;
exit(-);
end; procedure union(x,y:longint);
var k1,k2:longint;
begin
k1:=getf(x);
k2:=getf(y);
if k1<>k2 then fa[k2]:=k1;
end; begin
readln(n,p,q);
for i:= to n do
begin
read(a[i]);
c[i]:=i;
fa[i]:=i;
end;
fa[n+]:=n+;
fa[n+]:=n+;
sort(,n); for i:= to n do
begin
x:=find(p-a[i]);
if x<>- then union(i,x)
else union(i,n+);
x:=find(q-a[i]);
if x<>- then union(i,x)
else union(i,n+);
end;
if getf(n+)=getf(n+) then
begin
writeln('NO');
halt;
end;
writeln('YES');
for i:= to n do
if getf(i)=getf(n+) then ans[c[i]]:= else ans[c[i]]:=;
for i:= to n do
begin
write(ans[i]);
if i<>n then write(' ');
end;
writeln;
end.
上一篇:连接Excel时出现未指定的错误


下一篇:php js 排序