Codeforces 468B Two Sets 并查集

题目大意:给出n个数,要求将n个数分配到两个集合中,集合0中的元素x,要求A-x也再0中,同理1集合。

写了几个版本号,一直WA在第8组数据...最后參考下ans,写了并查集过了

学到:1、注意离散的逻辑思维,官方答案的 从条件推逆否命题

2、并查集做法:fa[find(i)]=mp[a-p[i]]
? find(a-p[i]) :
find(n+2);

3、离散化然后hash的方法,用map时间还是承受得住的,写起来也简单

//#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std; #define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)
const ll ll_INF = ((ull)(-1))>>1;
const double EPS = 1e-8;
const double pi = acos(-1.0);
const int INF = 100000000; const int MAXN = 1e5+100; int fa[MAXN],p[MAXN],vis[MAXN];
int n,a,b;
map <int , int> mp; int Fi(int x)
{
if(x!=fa[x])fa[x]=Fi(fa[x]);
return fa[x];
} void un(int x, int y)
{
x=Fi(x);
y=Fi(y);
fa[x]=y;
}
int flag;
void init()
{
for(int i=0;i<=n+3;i++)
fa[i]=i;
mp.clear();
CL(vis,0xff);
flag=1;
} /*void solve()
{
for(int i=1;i<=n;i++)
{
if(mp[a-p[i]])
{
if(Fi(fa[mp[a-p[i]]])==Fi(n+2) || mp[b-p[i]])
{
flag=0;
return;
}
else
{
un(mp[a-p[i]],n+1);
}
}
else
{
if(mp[b-p[i]])
{
if(Fi(fa[mp[b-p[i]]]) == Fi(n+1) || mp[a-p[i]])
{
flag=0;
return;
}
else
{
un(mp[b-p[i]],n+2);
}
}
else
{
flag=0;
return;
}
}
}
}*/
void solve()
{
for(int i=1;i<=n;i++)
{
fa[Fi(i)] = mp[a-p[i]] ? Fi(mp[a-p[i]]) : Fi(n+2);
fa[Fi(i)] = mp[b-p[i]] ? Fi(mp[b-p[i]]) : Fi(n+1);
}
} int main()
{
//IN("D.txt");
while(~scanf("%d%d%d",&n,&a,&b))
{
init();
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
mp[p[i]]=i;
}
solve();
if(flag && Fi(n+1)!=Fi(n+2))
{
printf("YES\n");
int ans[MAXN],cnt=1;
for(int i=1;i<=n;i++)
{
if(Fi(i) == Fi(n+1))
ans[i]=0;
else
ans[i]=1;
}
printf("%d",ans[1]);
for(int i=2;i<=n;i++)
printf(" %d",ans[i]);
putchar('\n');
}
else
puts("NO"); }
return 0;
}
上一篇:EF6多线程与分库架构设计之Repository


下一篇:Codeforces 859E Desk Disorder 并查集找环,乘法原理