ResurrectionTX

题解

比赛(7) 笔记(6)

/ 注册

全部文章 / 题解（共3篇）

2020牛客NOIP赛前集训营-提高组（第三场）B 牛半仙的妹子图

首先因为能走过的边的边权是递增的，那么经典套路是枚举最大的边的长度然后用并查集合并图上点的连通性。按照题意，当困难度为的时候的答案就是将所有边权的边加进去之后起点所在的连通块中不同类型点的数量。注意类型数量比较少只有种，所以可以直接对每个并查集用维护并查集里出现的点的类型情况。发现有多次询问，...

并查集 bitset

2020-10-22

4 603

Luogu P3295 【[SCOI2016]萌萌哒】

Description 传送门 Solution 首先先考虑如果限制不是区间，而是告诉你两个位置的字符相等的做法。这样的话，我们可以把相等的位置加进一些集合里，最后答案就是\(9 \times 10 ^ {num - 1}\)，其中\(num\)代表不同的集合个数，这个可以简单地用并查...

倍增并查集 Luogu

2020-06-12

0 355

Luogu P2754 【[CTSC1999]家园 / 星际转移问题】

Description 传送门 Solution 判断有无解可以使用并查集，如果最后地球和月球能处在同一个集合中，那么肯定可以到达，只是时间长短的问题。因为多个飞船是同时飞行的，这样的问题不好直接处理。考虑星球的个数特别少，这时可以考虑按照时间轴建立分层图，\(S\)向每个时间点的地球...

分层图网络流并查集 Luogu

2020-06-12

0 386