Z_L_G

分类

总结(8) 训练赛(3) 题解(48)

/ 注册

全部文章（共6篇）

算法入门-[SCOI2010]游戏

题意有n个二元组，每个二元组可以选取一个值，组成一个长为n的序列，问从1开始的最大连通能到几思路并查集，对于单一二元组，我们总希望选择其中小的对于一个连通块：一定属于下述两种情况之一 n个数的连通块，有n-1条边，则最大的元素选不到 n个数的连通块，有超过n-1条边，则所有元素...

并查集广度优先搜索思维

2025-04-12

0 10

算法入门-奶酪

题意有一块奶酪，高度为h，内部有n个球洞，半径均为r,问这些球洞能否贯穿奶酪思路使用并查集，合并到顶和底两个大集合中，最后检查顶和底是否在同一个集合注意，和顶部连通的球洞可能同时和底部连通，注意处理方式另一种思路为使用深度优先搜索，看全部搜完后最大深度能否超过h AC代码(并查集)...

并查集深度优先搜索

2025-04-03

0 23

算法入门-食物链-并查集特殊用法

PS 此题是并查集的一种抽象运用，通过开大空间，将一条逻辑链存到一个合并集合里开眼看世界题意三种动物：a吃b，b吃a，c吃a n只动物，m条信息，信息就两类——ab是同类\a吃b 若一条信息和之前矛盾，则认为新出现的是假信息，求一共有多少条假信息思路最终维护三个集合，每个集合代表...

并查集

2025-03-31

0 17

算法入门-DongDong认亲戚

题意 n个人，m次操作每次操作要么在a,b之间建立亲戚关系，要么查询a，b之间是否为亲戚思路并查集典例，最开始每个结点的父亲是自己，建立，就合并两个，查询就查询 AC代码 #include<bits/stdc++.h> using namespace std; int f...

并查集

2025-03-31

0 18

算法入门-Parity_game-并查集

题意给定长为n的01串，给出m次描述，找出第一次矛盾的描述序号思路将区间值转化为端点值 eg:[5,10]中有奇数个1，说明前4个数中1的个数和前10个数中1的奇偶性不同，也就是前4个数中有奇数个一的时候前10个数有偶数个1 维护一个大小为2n的father数组，当属于1-n表明为奇数，...

并查集 map

2025-03-31

0 18

并查集

介绍实现集合的合并和查找用树来存储一个集合如果两个点有共同根，就在一个集合里合并只需要把一个点的根放到另一个点的根的下面就行两种优化按秩合并把矮的集合的根放到高的集合的根的下面总能保证深度不超过logn 路径压缩（简单常用）操作复杂度O(logn) 忽视两个点的父子关系，...

并查集

2025-03-31

0 18