求助 NOI online CCF 题解 T2 的 70pts 做法

学术版

zhiyangfan @ 2022-03-28 20:46:41

就，有没有老哥解释一下具体细节。

我想了好久这个森林大概是啥样的，是父亲集合一定包含儿子集合吗？这样确实只有 \mathcal{O}(n) 条边，且仅需要比较 \mathcal{O}(n) 次，那怎么构造呢qwq

是每次选 x 那条链扔进去的话，\mathcal{O}(nm) 了吧qwq 毕竟每次找包含 x 的就 \mathcal{O}(n) 了。

想不通想不通，来个哥哥解释一下吧。

by warzone @ 2022-03-28 20:54:09

@zhiyangfan 每条链上的点可以按照出现次数排序确定祖先关系。

然后基数排序。

by zhiyangfan @ 2022-03-28 20:57:45

@wangrx 还是有点不太懂

我现在不太懂怎么把链拉出来，而且这个链，总点数也得是 \mathcal{O}(nm) 的吧。（

祖先关系和出现次数又有啥关系啊。（（

by Loser_King @ 2022-03-28 20:58:26

讲一下我的做法：你考虑先建一个虚点 0 包含集合 1\sim n，然后题述条件就相当于存在一个环，大概是这样：

------------
  |      |
 ------  |
     |   |
    -------

考虑如何处理重合情况，如果对于两个集合 x,y，满足 x 和 y 有交并且不存在集合 z 满足 x\subseteq z \subseteq y，则连边 x\leftrightarrow y。

这个时候可以发现答案为 NO 与当前连边形态为树为充要条件。

by Loser_King @ 2022-03-28 21:00:02

注：加边时要按集合大小从大到小加。

by matrix_ok @ 2022-03-28 21:00:05

@zhiyangfan 总点数是O(m)的,因为每次会把包含x的集合拿出来,总点数是O(m)

by zhiyangfan @ 2022-03-28 21:01:57

@like_AC 8 草，感觉是我完全没理解到题解啥意思（

按我的理解，比如

1
5 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5

总点数不就是 25 了吗（每次都拿 1\sim 5

by Loser_King @ 2022-03-28 21:02:24

注意这样维护不用显式建图。

by zhiyangfan @ 2022-03-28 21:02:27

@Loser_King

感觉这个方法很牛，我想想

by matrix_ok @ 2022-03-28 21:03:55

@zhiyangfan 对啊,m就是所有k之和

by zhiyangfan @ 2022-03-28 21:05:18

@like_AC 草草草，我傻了

行了，我完全懂了。

| 下一页