标签: 并查集

8 篇文章

#61. 【UR #5】怎样更有力气
Description 题目链接:#61. UR #5 大力水手问禅师:“大师,很多事情都需要用很大力气才能完成,而我在吃了菠菜之后力气很大,于是就导致我现在非常依赖菠菜。我很讨厌我的现状,有没有办法少吃点菠菜甚至不吃菠菜却仍很有力气?” 禅师浅笑,答:“方法很简单,不过若想我教你,你需先下山徒手修路。” 山下是 $n$ 座村庄从 $1$ 到 $n…
P4117 [Ynoi2018] 五彩斑斓的世界
Description 题目链接:P4117 给定一个长为 $n$ 的序列,有 $m$ 个操作: 区间 $[l,r]$ 中大于 $x$ 的数减去 $x$。查询区间 $[l,r]$ 中 $x$ 的出现次数。 $1\leq n \leq 10^6,1\leq m \leq 5\times 10^5,1\leq l \leq r\leq n,0\leq …
LuoguP4119 [Ynoi2018] 未来日记
Description 题目链接:P4119 一个长为 $n$ 的序列 $a$,有 $m$ 次操作。 把区间 $[l,r]$ 内所有的 $x$ 变成 $y$。查询区间 $[l,r]$ 内第 $k$ 小值。 $1\leq n,m,a_i\leq 10^5$ Solution stO 陈指导 Orz,陈指导码了一个下午就做完了,蒟蒻我竟然写了3天。 首…
bzoj 2959 长跑 题解
Description   某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”,同学们纷纷离开寝室,离开教室,离开实验室,到操场参加3000米长跑运动。一时间操场上熙熙攘攘,摩肩接踵,盛况空前。  为了让同学们更好地监督自己,学校推行了刷卡机制。  学校中有n个地点,用1到n的整数表示,每个地点设有若干个刷卡机。  有以下三类事…
Luogu P4255 公主の#18文明游戏 题解
Describe 题目链接 这个游戏里有n个城市,标号1~n,有m条双向道路相连,编号1~m。 游戏里会系统会添加Ni个人到一个城市Xi,并给定这些人的信仰Ci 系统还会切断一条道路,并给定道路编号Xi 系统还会给定一个城市Xi,询问从Xi出发可以到达的所有城市中选择Ni个人,使得他们信仰都为Ci的概率为多少,对19260817取模。 Soluti…
Luogu P3535 [POI2012]TOU-Tour de Byteotia 题解
Link 题意 给定一个$n$个点$m$条边的无向图,问最少删掉多少条边能使得编号小于等于$k$的点都不在环上。 思路 要想让编号小于等于$k$的点都不在环上,那么就最好让所有编号大于$k$的边都在环上。 那么可以用并查集把所有编号大于$k$的边连起来,再判断编号小于等于$k$的边是否在环上即可。 Code #include<bits/std…