[题解]gdfzoj2132

传送门

定义联通块为一个点的集合,该集合中的点相互碰撞,可留下任意一个点

这道题其实是求 联通块 个数

考虑 (O(n^2)) 做法:

用并查集思想,枚举每个点对,如果可以发生碰撞,就合并

(但是ACM赛制没有部分分)

满分做法:

对于两个不相交联通块 (S,T),如果 (S) 中有点 (x), (T) 中有点 (y),且 (x) , (y)可以发生碰撞,那么 (S) (cap) (T) 也是一个联通块(自证)

将点按照先 (x)(y) 的顺序排序后,可以发现联通块是连续的((1)(x) 是一个联通块, (x+1)(n) 又是一个联通块)

那么我们只需要计算联通块的断点即可

(maxl[i]) 表示从左往右前 (i) 个点, (y) 坐标的最大值(字面意思)

(然后 (maxr[i])(minl[i])(minr[i]) 也是字面意思)

排序后若点 (i) 和点 (i+1) 不在一个联通块内,当且仅当 (minl[i]) (leq) (maxr[i])

然后 (O(n)) 遍历一遍就可以了

代码不放了,去 (OJ) 上看吧

原文地址:https://www.cnblogs.com/ZHANG-SHENG-HAO/p/12661826.html