题解 P1955 【[NOI2015]程序自动分析】

· · 题解

题目

题意很明显了，并查集基本操作

我们把所有操作存下来，离线先处理合并（即要求相等），再对每个要求不相等判断根是否相同即可

以上思路很好想，其他题解也有详细描述，这篇题解主要想说的是：

离散化

首先由题目i，j的规模：1<=i,j<=1e9 可知需要离散化

离散化一般有三种方法

1.map

这个相信大家都会，不过似乎容易被卡，这里不讨论

2.unique函数

algorithm中的函数,把数组去重(不真正把重复的元素删除),然后返回末尾指针（某题解）

这也是大多数题解使用的方法

我一开始是这样写的：（注释来自某题解）

il void lsh(){                      //离散化  
    sort(book+1,book+cnt+1);
    reu=unique(book+1,book+cnt+1)-book; 
    //algorithm中的函数,把数组去重,然后返回末尾指针.这里减一个b就可以表示b现在的大小了 
    for(re int i=1;i<=n;++i){
        a[i].x=lower_bound(book+1,book+reu+1,a[i].x)-book;  
        //十分实用的lower_bound,寻找b中>=a[i].x的第一个数的指针 
        //因为x在b中一定存在,所以是直接求出x离散化后对应的值,减去b就是它的位置  
        a[i].y=lower_bound(book+1,book+reu+1,a[i].y)-book;
    }
}

然后我wa了第三个点 测出我错误的数据是：

2
4
8 2 0
2 9 1
2 7 1
9 7 0
3
9 2 0
1 3 1
2 3 1

NO
YES

我仔细对照题解，发现我加上（pre就是祖先数组）

memset(pre,0,sizeof(pre));

就AC了

但我想不明白啊 按理说pre每次使用前会有初始化为自己的过程，需要使用的部分明明可以直接覆盖

 for(re int i=1;i<=reu;++i) pre[i]=i;

当我输出一些中间变量时发现

对于
3
9 2 0
1 3 1
2 3 1

映射出来
1->1 2->2 3->3 9->6 （what？和自己想的不一样啊）
而此时reu=5
memset后询问时 一个数的根为0 才得到正确答案

那么关于unique离散化的正确性？？

网上各种博客看不懂，对unique完全不知道怎么用，它返回的到底是什么呢？？

求dalao评论区解惑QAQ

3.不使用map/unique

模板：

il void lsh(){
    sort(book+1,book+cnt+1);
    for(re int i=1;i<=cnt;++i)
        if(i==1||book[i]!=book[i-1]) b[++m]=book[i];
}
il int query(int x){
    return lower_bound(b+1,b+m+1,x)-b;
}

不需要对pre初始化0

中间数据

2 -> 1
7 -> 2
8 -> 3
9 -> 4
NO
1 -> 1
2 -> 2
3 -> 3
9 -> 4
YES

嗯这才是我想要的映射

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register
#define il inline
#define ll long long
using namespace std;

inline int read(){
    int s=0,f=0;char c=getchar();
    while(c<'0'||c>'9') f=(c=='-'),c=getchar();
    while(c>='0'&&c<='9') s=(s<<3)+(s<<1)+(c^'0'),c=getchar();
    return f?-s:s;
}

const int N=1e5+5;
int t,n,pre[N],cnt;
struct no{
    int x,y,op;
}a[N];
il bool cmp(no x,no y){return x.op>y.op;}

int book[N<<2],b[N<<2],m;

il void init(){
    for(re int i=1;i<=m;++i) pre[i]=i;
}
int find(int x){
    return pre[x]==x?x:pre[x]=find(pre[x]);
}
bool fl;

il void lsh(){
    sort(book+1,book+cnt+1);
    for(re int i=1;i<=cnt;++i)
        if(i==1||book[i]!=book[i-1]) b[++m]=book[i];
}
il int query(int x){
    return lower_bound(b+1,b+m+1,x)-b;
}
int main(){
    t=read();
    while(t--){
        memset(book,0,sizeof(book));cnt=m=0,fl=1;

        n=read();
        for(re int i=1;i<=n;++i){
            a[i].x=read(),a[i].y=read(),a[i].op=read();
            book[++cnt]=a[i].x,book[++cnt]=a[i].y;
        } 

        lsh();

        sort(a+1,a+n+1,cmp);
        init();
        for(re int i=1;i<=n;++i){
            int x=query(a[i].x),y=query(a[i].y);
            int fx=find(x),fy=find(y);
            if(a[i].op==1) pre[fx]=fy;
            else if(fx==fy){
                puts("NO");fl=0;break;
            } 
        }
        if(fl) puts("YES");
    }
    return 0;
}

求解惑