ymzqwq

并查集

233(7) BZOJ(4) Codeforces(5) dfs(1) DP(24) hdu(1) TopCoder(20) 不知道怎么分类(2) 乱搞(2) 分块(1) 博弈论(1) 图论(5) 平衡树(2) 搜索(4) 数论(18) 未归档(3) 杂记(2) 树(4) 树状数组(1) 模拟/暴力(5) 游记(1) 笔记整理(3) 线段树(1) 贪心(5) 递归(1) 递推(1)

/ 注册

全部文章 / 并查集（共4篇）

TopCoder SRM 589 Div1 250 GooseTattarrattatDiv1

由于每次相同的字母都是一起变的，所以相同的字母可以看作一个整体。先在原串上跑一遍回文，用并查集维护哪些字母要变成一样的。然后修改的时候当然就是把出现次数少的修改成出现次数多的…… 一开始智障以为是像合并果子一样的…结果发现只要全都合并到最大的那个上就好了于是代码就被我魔改成了堆排？？？ /...

2018-09-11

0 462

TopCoder SRM 576 Div1 250 ArcadeManao

一开始写了个智障版bfs，样例都没过。。然后心血来潮写个并查集，结果各种FST。。并查集的思路很简单，就是维护哪些点能相互到达，然后不断延长梯子，直到最底下一层和金币联通…… 二分+bfs估计也是可过的。 #include <bits/stdc++.h> using name...

2018-08-29

0 435

TopCoder SRM 572 Div1 250 NewArenaPassword

题目给出的条件是一些相等关系，很容易想到可以用并查集维护。要让每一个联通块都是相同的字母并且修改最少，肯定就是全部修改成出现最多的字母，暴力统计即可。 UPD：其实也不用并查集，相等的位置中间间隔的距离是固定的，直接跳就行了。 #include <bits/stdc++.h> usi...

2018-08-28

0 443

[CODEVS 1069][NOIP2010提高T3] 关押罪犯

传送门将边从大到小排序，用并查集维护，第一条无法满足的边就是答案。重点在于如何记录哪些点不在同一个集合。我们给每一个实点A对应一个虚点A’。若要记录A、B两点不在同一集合即给A、B’以及B、A’之间连边。接下来，若要记录B、C两点不在同一集合，连边之后A、C就在同一集合了。就不要吐槽我的...

2017-09-26

0 397