个人整理
并查集
【poj】
第一题 poj 1182 食物链
点击打开链接poj 1182
思路: 带权并查集
分析:
1 典型的带权并查集的题目
2 如果x和y是同类的关系认为是0,如果是x吃y那么关系认为是1,那么x和y的关系为2就说明y吃x
3 那么如果x和y同类则rank[x] == rank[y] , 如果x吃y那么rank[x] == (rank[y]+1)%3 , 注意mod3的使用
点击查看代码
第二题 poj 1308 Is It A Tree?
点击打开链接 poj 1308
思路: 普通并查集
分析:
1 题目输入一些边,要我们去判断是否是一棵树
2 根据题目的意思,空树也是树或者只有一个跟节点的是树
3 不满足的情况是边是自环即x == y的情况,还有就是加入一条边形成环。由于树是一个连通分量,所以最后判断一下是不是只有一个连通分量
4 输入的边可能是自环,这个是一个trick
点击查看代码
第三题 poj 1611 The Suspects
点击打开链接poj 1611
思路: 普通并查集
分析:
1 题目最终要求的是和0同一个集合的元素的个数
2 比较简单的题,在线更新并查集,开个数组记录当前集合的元素的个数
点击查看代码
第四题 poj 1703 Find them, Catch them
点击打开链接poj 1703
思路: 简单带权并查集
分析:
1 题目要询问给定的x和y是否是同一个动物
2 我们假设如果不同,那么权值为1,否则为0。因此对于给定的x和y,那么如果x和y不在一个集合里面那么就是不确定,否则就可以根据rank来判断是什么关系
点击查看代码
第五题 poj 1988 Cube Stacking
点击打开链接 poj 1988
思路: 带权并查集
分析:
1 题目给定2种指令 M x y把x的集合放在y集合的上面,C x求x的下面有多少个元素
2 我们用rank[x]表示x以下有多少个元素,那么对于指令M x y我们始终把左边的合并到右边,那么这样rank就满足压缩的性质
3 但是因为这边的合并和普通不一样,它是把x所在的集合放在y所在集合上面,实际上是x的跟节点合并到y集合的最远点,所以我们应该开个数组记录当前集合最远的点
点击查看代码
第六题 poj 2236 Wireless Network
点击打开链接poj 2236
思路: 普通并查集
分析:
1 初始值所有的电脑都是坏的,然后给肯定n个点的坐标,只有距离不大于d的才认为连通的
2 现在给定两种操作,O p表示编号为p的电脑被修好了,S p q询问p q是否是连通的
3 简单的并查集,先预处理出所有的点到其他点的距离,然后每一次修好一个电脑之后就去更新并查集,遇到询问的时候只要判断是否在同一个集合里面即可
点击查看代码
第七题 poj 2492 A Bug's Life
点击打开链接poj 2492
思路: 带权并查集
分析:
1 用rank[i] = 0表示关系相同,用rank[i] = 1表示关系不同
2 在输入的时候把两个元素之间的关系建立起来,然后判断当前的两个元素是否在同一个集合里面,如果是则判断是不是属于同一个类型即可
点击查看代码
第八题 poj 2524 Ubiquitous Religions
点击打开链接poj 2524
水题
点击查看代码
第九题 poj 1456 Supermarket
点击打开链接poj 1456
思路: 贪心+并查集
分析:
1 题目的意思是给定n个物品的利润和出售的最后时间,求最大的利润
2 比较明显的贪心问题,按照利润排序,假设当前是第i个物品,那么利润为pi出售的时间为di,那么假设di还没有物品销售那么肯定先销售第i个物品,否则找di~1这些时间里面是否有没有销售物品
3 如果按照2的思路做法最坏的情况是O(n^2),但是数据比较弱可以过。但是我们这边可以利用并查集来优化,根据2如果di已经被占用了那么我们要去找di~1的时间,这里利用并查集的思路。如果di被占用了之后,那么father[di] = di-1说明如果下次再来一个销售日期为di的话是要放到di-1天,那么对于第i个物品我们只要判断find(di)是不是大于0,如果是di可以放到find(di)这一天销售,否则跳过
点击查看代码
第10题 poj 1733 Parity game
点击打开poj 1733
思路: 带权并查集
分析:
1 题目给定n个条件,要我们找到第一个不满足条件的编号
2 每一个条件给的是区间[l,r]的1的奇偶数,很明显[l,r]这个区间的1的个数可以由[0,r]-[0,l-1]得来
3 那么我们利用并查集的思想,rank[x]表示的是x到跟节点这个区间即[x,father[x]]这个区间的1的个数,那么奇偶性可以由1和0来表示
4 题目还有一个难点就是要离散化,一般的离散化的步骤是排序+去重,然后找的时候利用二分即可
点击查看代码
第十一题 poj 2912 Rochambeau
点击打开poj 2912
思路: 带权并查集
分析:
1 有n个小孩玩游戏,里面有一个入是裁判,剩下的人分为三组。现在我们既不知道裁判是谁也不知道分组的情况。现在n个小孩玩剪刀石头布,已知每组的小孩只会出同一种手势,问谁是裁判
2 题目说了输入=的时候说明是同一组,如果是<或>的时候说明是不同一组,那么根据食物链那一题的思路,我们设rank[x]表示x和根节点的关系,如果是=那么rank[x] = 0,如果是<则rank[x] = 1,否则为rank[x] = 2
3 剩下的就是怎么求最少几轮得到裁判的编号,要得出最后的裁判,也就是其他的人度不满足的最大的那一轮,因为那一轮过后就能确定裁判了
4 判断关系的时候,如果是不同的集合那就合并,否则判断是否有rank[x] == (rank[y]+val)%3
点击查看代码
【hdu】
第一题 hdu 3038 How Many Answers Are Wrong
点击打开hdu 3038
思路: 带权并查集
分析:
1 给定一序列的区间的和,求错误的个数
2 典型的带权并查集,区间[l,r]的和等于sum[r]-sum[l-1]。对于一般涉及到区间和还有个数的问题的时候,都要把左下标减一来处理
3 用rank[x]表示的是x到跟节点的和即[x,find(x)]的和,那么对于给定的x,y,val,fx为x的跟节点,fy为y的跟节点
如果fx != fy那么这个时候就要考虑fx和fy的关系
fx > fy ,则father[fy] = fx; rank[fy] = rank[x]-val-rank[y];
fx < fy ,father[fx] = fy; rank[fx] = rank[y]+val-rank[x];
否则判断rank[x]-rank[y]是否为val
点击查看代码
第二题 hdu 1856 More is better
点击打开链接hdu 1856
思路: 离散化+并查集
分析:
1 点数最多为10^7,但是边数最多10^5,所以我们必须采用离散化,然后利用带权并查集的思想,rank[x]表示的是以x为根节点的集合的元素个数
2 这一题主要注意的就是当n = 0的时候,因为题目说了刚开始有10^7个人在房间里面,所以n = 0的时候最多有一个人出去
点击查看代码
第三题 hdu 1198 Farm Irrigation
点击打开hdu 1198
思路: 并查集
分析:
1 题目给定11快小方形,然后给定一个n*m的描述求n*m矩阵内的连通分量的个数
2 首先我们应该解决怎么保存11块小方形,我们可以利用一个思维的分量来描述,比如A我们描述成{1,0,0,1}
3 那么我们就可以做到在线进行并查集的操作,对于[i,j]这个方块,它可能和[i-1,j]和[i,j-1]进行相连,那么用i*m+j来唯一表示一个位置,那么最后枚举整个二维矩阵即可
点击打开查看代码
第四题 hdu 3635 Dragon Balls
点击打开hdu 3635
思路: 并查集
分析:
1 题目说有n个城市每一个城市有一个龙珠编号为i,现在有m行的输入包括两种的情况
T x y 把x所在的集合的所以龙珠转移到y集合上 Q x 询问x所在集合的龙珠的个数
2 我们利用rank[x]表示的是根节点为x的集合的元素的个数,但是现在我们发现求转移的次数不好求,刚开始我用的是一个vector数组来保存,比如v[x]表示以x为根节点的集合的元素,那么如果是把fx这个集合并到fy上的话,那么我们枚举v[fx]。但是这个方法TLE了
3 后来看了网上的题解,发现在求转移次数的时候我们也可以利用递归合并的思想,比如把fx所在的集合转移到fy的时候,那么我们只要把fx的转移次数加一,那么下次递归的时候我们在里面进行处理即可
点击查看代码
第五题 hdu 2473 Junk-Mail Filter
点击打开hdu 2473
思路: 并查集
分析:
1 题目初始化给定n个不同的点,然后给定m个操作,有两种类型 m x y 表示x和y是同一种类型,s x表示把x从集合中单独提前出来
2 这一题和uva11987很像,我们可以在初始化的时候把所有的节点的根节点设置成i+n, 那么我们遇到提取x的时候就不会碰到x刚好是根节点的情况
3 在合并x和y的时候我们应该要考虑的问题是x和y是不是之前被提前过的,如果都不是那么直接合并,否则我们应该注意合并的方向
4 遇到s x的时候我们把x的父亲节点设为cnt,cnt是一个移动的数值,注意这里cnt的值,数值应该要开大一点,这边我WA了很多次
5 最后统计连通分量的个数即可
点击打开查看代码
第六题 hdu 3172 Virtual Friends
点击打开hdu 3172
思路: 简单并查集
分析:
1 利用map对每个人进行编号,然后利用并查集即可
2 这一题有个地方就是输入case的时候要判断不等于EOF
点击打开查看代码
第七题 hdu 3047 Zjnu Stadium
点击打开hdu 3047
思路: 带权并查集
分析:
1 题目要求的是错误的条件的个数,这一题还是比较简单的带权并查集
2 我们用rank[x]表示的x到跟节点的距离,那么对于x和y来说,如果x和y在不同集合那么把x和y合并,否则直接判断rank[x] == (rank[y]+val)%300
点击查看代码
第八题 hdu 2818 Building Block
点击打开hdu 2818
思路: 带权并查集
分析:
1 题目给定2种指令 M x y把x的集合放在y集合的上面,C x求x的下面有多少个元素
2 我们用rank[x]表示x以下有多少个元素,那么对于指令M x y我们始终把左边的合并到右边,那么这样rank就满足压缩的性质
3 但是因为这边的合并和普通不一样,它是把x所在的集合放在y所在集合上面,实际上是x的跟节点合并到y集合的最远点,所以我们应该开个数组记录当前集合最远的点
点击查看代码
第九题 hdu 3461 Code Lock
点击打开hdu 3461
思路: 并查集+离散化+快速幂
分析:
1 题目给定长度为n的字符串,然后给定m个操作,询问最后的不同字符串的个数
2 考虑长度为n的时候,因为每个字符有26种情况('a'~'z'),所以有26^n。因为有m次的操作,题目中说了如果可以被变换那么认为是相同的字符串,那么不同的字符串就是所有不被操作区间的组合
3 那么我们利用并查集去求有操作的集合的个数,比如[1,3],[3,5]和[1,5]是三个集合,而[1,3],[4,5]和[1,5]则是2个集合
4 对于区间[l,r],那么我们一般转化为处理(l-1,r],这样不用考虑端点的问题了,最后利用快速幂求出ans即可
点击查看代码
第十题 hdu 1558 Segment set
点击打开hdu 1558
思路: 计算几何+并查集
分析:
1 有n个操作,最后求有几个集合或者说是连通分量
2 对于输入一条线段我们就去前面找能够和它相交的线段,利用并查集进行合并并且更新rank数组,rank[x]数组保存的是以x为跟节点的集合的线段的数量
3 这一题难点就是线段的相交判断
点击打开查看代码
【zoj】
第一题 zoj 3261 Connections in Galaxy War
点击zoj 3261
思路: 带权并查集
分析:
1 题目说的是有n个星球0~n-1,每个星球都有一个战斗值。n个星球之间有一些联系,并且n个星球之间会有互相伤害
2 根本没有思路的题,看了网上的思路才知道是逆向并查集。如果我们按照正常的并查集来做,以战斗值最大为根节点的话,当询问的时候很容易,但是碰到删除边的时候就很困难了,所以这里才用逆向的并查集思路
3 我们先把所有的输入保存,然后我们可以这么考虑,从后面往前面枚举q次条件,如果是destroy我们认为是加边,这样的话就很好维护并查集了
4 但是这边我们还要考虑初始的状态,由于涉及到删边而且不一定是删除所有的边,所以我们只要在m个关系里面扣除要删除的边,然后建立集合做为初始的状态
点击查看代码
【uva】
第一题 uva 1160X-Plosives
思路: 普通并查集
分析:
1 题目意思不难理解,一些化学物品由两种元素组成,如果刚好有k个化学物品刚好由k个元素组成的话,那么将会爆炸
2 k个化学物品刚好由k个元素组成,那么等价于k条边刚好由k的点组成,那么这一题就变成判断是否在同一个集合的问题了
点击查看代码
第二题 uva 1329 Corporative Network
思路: 带权并查集
分析:
1 给定两种操作。I u v 是把节点u的父节点设为v ,并且节点u 和 节点v的节点距离为(|u-v|)%1000,E u询问u到跟节点之间的距离
2 比较简单的带权并查集
点击查看代码
第三题 uva 11987 Almost Union-Find
思路: 并查集
分析:
1 题目给定三种操作,符合并查集的模式
2 但是有一种操作和普通的并查集不同的是,2 p q要把p并到q的集合,那么这个时候p所在的集合就会发生变化,如果p刚好是它那个集合的跟节点那么这个时候就要重新调整这个集合
3 那么我们为了避免这种删除跟节点的情况出现,我们就把所有的i~n的节点的跟节点指向i+n,这样保证了删除的时候肯定不会是根节点。这样就变成了简单的并查集问题了
点击查看代码
第四题 uva 12232 Exclusive-OR
思路: 并查集的扩展应用
分析:
1 题目给定三种指令,I p v表示Xp = v, I p q v表示Xp^Xq = v,
Q k Xp1 Xp2...Xpk求Xp1^Xp2^...^Xpk的值。
2 对于的异或的性质:1 a^0 = a,2 a^c^b^c = a^b,异或一个数偶数次等于没有异或,因为异或偶数次的值为0,根据性质1那么结果没有影响
3 因此对于第一种命令I p v,我们可以虚拟出一个点Xn = 0,那么p^xn = v,那么第一和第二种命令我们可以统一成p^q = v的模式。
4 那么我们设val[i] = Xi^Xfather[i],但是要注意的是Xn要始终为那个集合的跟节点,因为这样我们才能够通过val[i]的值判断Xi是否存在。
5 那么Xp1^Xp2^...^Xpk = (val[Xp1]^val[Xp2]^...^val[Xpk])^(Xfather[xp1]^Xfather[xp2]^...^Xfather[xp2]);因为(val[Xp1]^val[Xp2]^...^val[Xpk])我们很容易求出来,所以我们现在就判断Xfather[xp1]^Xfather[xp2]^...^Xfather[xp2]是否存在,根据性质2我们只需要判断父亲节点出现次数为奇数的,如果父亲节点为Xn,那么值存在,否在不存在我们不能求出ans
点击查看代码
分享到:
相关推荐
大家尽管下载,并查集专题现在已经上传,尽请期待
① 参考本书第 10 章“10.10.2 kruskal 算法”。图 1 并查集的初始化(2)合并,例如加入第一个朋友关系(1, 2)。在并查集 s 中,把结点
本例我们使用iServer java6R自带地图“京津地区土地利用现状图”,对Landuse_R数据集做单值专题图,根据Landuse_R数据集的LANDTYPE字段将土地利用划分为林地与非林地这种类型通过专题图展示出来,Landuse_R数据集中...
本系列速查表包含 200 多张知识卡片,分为『计算机科学』『机器学习』『计算机视觉和深度学习基础』『计算机视觉和深度学习精选专题』4个主题,用以回顾多年的 ML 研究、课程和学习中的所有内容,并为机器学习工程师...
提出一种基于锚文本和标题信息过滤并结合网页内容相关度判断的HITS专题检索策略,利用专题训练集判断主题相关度,很好地解决了只依靠查询字符串判断的弊端。实验表明,此策略能很好地提高专题信息汇聚精确度和检索的...
本例我们使用iServer Java 6R自带地图“京津地区土地利用现状图”,对Landuse_R数据集做单值专题图,根据Landuse_R数据集的LANDTYPE字段将土地利用划分为林地与非林地这种类型通过专题图展示出来,Landuse_R数据集中...
董老师的选修课中有一节专题“不相交集合的算法与讨论”,“不相交集合”即为并查集。在刘汝佳的《算法艺术》或其他高级数据结构教材中可找到。我们用森林表示一个并查集,每棵树是一个集合,用树根来标识一个集合。
董老师的选修课中有一节专题“不相交集合的算法与讨论”,“不相交集合”即为并查集。在刘汝佳的《算法艺术》或其他高级数据结构教材中可找到。我们用森林表示一个并查集,每棵树是一个集合,用树根来标识一个集合。
7.9 数据结构(二): 并查集, DFA, Trie树,Trie图等 7.10 搜索:深搜,广搜,剪枝,IDA*算法 7.11 计算几何:线与线求交,线与面求交,求凸包,半平面求交等 7.15 若干图论问题:最小生成树 最短路 强连通分量、桥...
本系列速查表包含 200 多张知识卡片,分为『计算机科学』『机器学习』『计算机视觉和深度学习基础』『计算机视觉和深度学习精选专题』4个主题,用以回顾多年的 ML 研究、课程和学习中的所有内容,并为机器学习工程师...
经典算法:(二分匹配,背包专题,筛选法,简单数学题,贪心算法,递推求解,动态规划,并查集,母函数,搜索,组合博弈等入门算法)
本系列速查表包含 200 多张知识卡片,分为『计算机科学』『机器学习』『计算机视觉和深度学习基础』『计算机视觉和深度学习精选专题』4个主题,用以回顾多年的 ML 研究、课程和学习中的所有内容,并为机器学习工程师...
涉及各种算法的讲解,比如(二分匹配,背包专题,筛选法,简单数学题,贪心算法,递推求解,动态规划,并查集,母函数,搜索,组合博弈等入门算法)
5. 并查集 6. 二叉堆 7. 逆序数(归并排序) 8. 树状DP 9. 欧拉路 10. 八数码 11. 高斯消元法 12. 字符串匹配(KMP算法) 13. 全排列,全组合 14. 二维线段树 15. 稳定婚姻匹配 16. 后缀数组 17. 左偏树 18. 标准RMQ-ST ...
本系列速查表包含 200 多张知识卡片,分为『计算机科学』『机器学习』『计算机视觉和深度学习基础』『计算机视觉和深度学习精选专题』4个主题,用以回顾多年的 ML 研究、课程和学习中的所有内容,并为机器学习工程师...
leetcode小岛出水口 LeetCode 题解 基础篇 数组,栈,队列 ...并查集 跳表 剪枝 专题篇 二分法 滑动窗口 位运算 搜索(BFS, DFS, 回溯) 背包问题 动态规划 分治 贪心 其他 包括自己的打卡,官方题解和精选题解
leetcode小岛出水口 LeetCode 题解 讲义 先导篇 基础 进阶 专题 笔记 题目 ...并查集 跳表 剪枝 专题篇 二分法 滑动窗口 位运算 搜索(BFS, DFS, 回溯) 背包问题 动态规划 分治 贪心 其他 全部参考题解
并查集 二分 数组 滑动窗口 递归 字符串 栈与队列(单调栈) 堆 树状数组、线段树 跳表 哈希链表 水池抽样 milestone 2020年6月9日,800题 √ 2020年6月21日,在这个特别的日子里(不仅仅是Eclipse),完成度50% √...
位运算系列动态规划系列 有效括号系列设计系列先锋和系列首要树并查集每日一题拓展跳表剪枝每日一题 字符串匹配每日一题 拓展翻译堆每日一题专题文章二分法每日一题拓展翻译 滑动窗口每日一题拓展翻译位运算搜索...
并查集 图 设计 拓扑排序 字典树 树状数组 线段树 二叉搜索树 递归 脑经急转弯 记忆化 队列 极小化极大 蓄水化抽样 几何 map 数组 哈希表 链表 数学 双指针 字符串 二分查找 分治算法 动态规划 回溯算法