正解:并查集+离散化
解题报告:
其实题目还挺水的,,,但我太傻逼了直接想挂了,,,所以感觉还是有个小坑点所以还是写个题解记录下我的傻逼QAQ
首先这题一看,就长得很像NOIp关押罪犯?然后就噼里啪啦打一个并查集上去,再随便离散化一下,就能获得90pts的好成绩,,,(因为数据太水了QAQ
然后考虑为什么不能用那题的套路?仔细思考下,用并查集的条件是什么?
——可传递性
简单来说,比如已知x=y,y=z,则必有x=z,所以这里可以用个并查集把他们缩成一块对趴
但这儿不光有x=y的条件,还有x≠y的条件鸭,显然x≠y,y≠z不能推出x≠z,所以显然不相等关系是不需要并查集维护的,就直接先把相等的做掉最后判一下不相等的是否相等就好
顺便说下,那为什么之前做关押罪犯的时候我们就要把不相等也维护了?因为那题只有两个阵营,所以可以得到不相等关系的关系
最后留个思考题,,,
这题是留一堆条件问能否达成嘛
那如果改成,每给一个条件都问能否达成,不能达成就跳过,怎么做?
umm自行思考趴QAQ其实并不难来着QAQ(解法在这儿,,,然而你们都不知道密码鸭嘻嘻嘻
最后放下代码
对了这题要离散化这个点我好像忘了说了,,,算了挺显然的我就$cue$下昂QAQ
over!
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define t(i) edge[i].to
#define mp make_pair
#define ri register int
#define rb register bool
#define rc register char
#define lb(x) lower_bound(st+1,st+st_cnt,x)-st
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt) const int N=1e6+;
int n,m,fa[N],st[N<<],st_cnt;
struct op{int l,r;bool typ;}ope[N]; il int read()
{
rc ch=gc;ri x=;rb y=;
while(ch!='-' && (ch<'' || ch>''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
int fd(ri x){return fa[x]==x?x:fa[x]=fd(fa[x]);}
il bool cmp(op gd,op gs){return gd.typ>gs.typ;} int main()
{
freopen("1955.in","r",stdin);freopen("1955.out","w",stdout);
int T=read();
while(T--)
{
n=read();st_cnt=;
rp(i,,n)ope[i]=(op){st[++st_cnt]=read()+,st[++st_cnt]=read()+,read()};
sort(st+,st++st_cnt);st_cnt=unique(st+,st++st_cnt)-st-;rp(i,,st_cnt)fa[i]=i;
sort(ope+,ope++n,cmp);rp(i,,n)ope[i].l=lb(ope[i].l),ope[i].r=lb(ope[i].r);
rp(i,,n)
{
if(ope[i].typ){ri fa1=fd(ope[i].l),fa2=fd(ope[i].r);fa[fa1]=fa2;}
else{ri fa1=fd(ope[i].l),fa2=fd(ope[i].r);if(fa1==fa2)printf("NO\n"),i=n+;}
if(i==n)printf("YES\n");
}
}
return ;
}
这儿是代码QAQ