生之、如舟

并查集

动态规划(8) 博弈论(1) 图论(7) 基本算法(29) 思维(3) 数学(14) 数据结构(5) 数论(18) 最短路(4) 枚举(1) 树状数组(13) 树论(4) 模板(7) 比赛(15) 算法总结(3) 线段树(11) 蓝桥杯(1) 贪心(1)

/ 注册

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

E. Binary Matrix 【并查集】2500

E. Binary Matrix 题意给一个很大的矩阵，问联通块的个数是多少。其中因为矩阵非常大，用的16进制输入的。解法这题非常卡常，光是读入量就已经1.6e7了，所以这里我使用了getchar()来读入。然后对于联通块的个数，就是总的1个数 - 并查集合并的次数考虑一行一行处理并查集...

图论2500 并查集

2020-11-17

0 658

Acwing.240. 食物链【并查集】【带扩展域】来自专栏

240. 食物链题目链接：https://www.acwing.com/problem/content/description/242/ 思路将域扩大成3倍 x 吃 x+N,x+N吃x+2N，x+2N吃x，于是如果出现了x吃y的关系，就可以得出下面图片所示的种族关系。同一个颜色表示同一个物种，...

并查集

2020-04-25

0 971

238. 银河英雄传说【带权并查集】来自专栏

238. 银河英雄传说题目链接：https://www.acwing.com/problem/content/240/ 思路是否在同一个集合很好维护，边带权记录某个节点到祖先(列的第一个节点)的距离就好。然后查询两个节点的间隔就是：abs(w[a]-w[b])-1 代码 #include<...

并查集

2020-04-25

0 820

P1621 集合【暴力】【并查集】来自专栏

P1621 集合题目链接：https://www.luogu.com.cn/problem/P1621 思路发现1e5/2+ 1e5/3 + 1e5/5+1e5/7+....的结果不到1e6，所以可以直接采用暴力，对于每个质因数P把在[L,R]区间的倍数join一下就行代码 #include&...

并查集

2020-04-25

0 837

关押罪犯【并查集】来自专栏

关押罪犯题目链接：https://ac.nowcoder.com/acm/problem/16591 思路见此题的视频讲解：https://www.bilibili.com/video/BV1nz411b75c 代码 #include <iostream> #include <...

并查集

2020-04-25

0 688

codeforces div2 603 D. Secret Passwords 【并查集】来自专栏

codeforces div2 603 D. Secret Passwords 题目大意：有很多的字符串，如果两个字符串有相同字母，就属于同一组，字符串a与b一组，b与c一组，那么a也与c一组，问这所有字符串可以被分成几组。思路我们只需要维护26个小写字母的并查集就可以了。同属于一个字符串里面...

2020-04-15

0 628

2019 ICPC 徐州网络赛 B.so easy 【并查集路径压缩】来自专栏

2019 ICPC 徐州网络赛 B.so easy (并查集) 题目链接：https://nanti.jisuanke.com/t/41384 题目大意给定n个数，从1到n排列，其中有q次操作，操作(1) 删除一个数字 // 操作(2)求这个数字之后第一个没有被删除的数字（包括自己）。思路本题...

并查集

2020-04-14

0 743

POJ1733-Parity game 【带权并查集】

Parity game 题目有一个长度为n的序列给出Q条限制l,r,str str==odd 表示[l,r]区间内的数的和是奇数，否则为偶数请你输出最小的不满足条件的编号-1（即最后一个满足的），如果全部满足，输出总数Q！分析算是一个带权并查集的模板题。dis[i]记录他到根结点的距离，假如a...

并查集

2020-02-19

0 819

ZOJ3261-Connections in Galaxy War 【逆向思维+并查集+离线处理】

Connections in Galaxy War 题目假设有编号从0开始的n个点，每个点都有一个非负权值p[i]。现在有没有重边的m条边和Q个操作。对于操作有两种类型destroy a b 表示摧毁a,b点之间的边query a 表示从a出发能到的点中,权值比a大权值最大,在权值最大前提下编号最...

并查集

2020-02-19

0 700

POJ1456-Supermarket 【贪心+并查集】

Supermarket 题目超市里有N个商品. 第i个商品必须在保质期(第di天)之前卖掉, 若卖掉可让超市获得pi的利润.每天只能卖一个商品.现在你要让超市获得最大的利润. 分析首先涉及到最大利润，那么我们到方案要尽可能到让利润大的商品卖出去，可以考虑利润从大到小排序发现一些什么性质。当我们选...

并查集

2020-02-18

0 848