这实际上是一个 Tarjan 求割点的裸题。 具体来说是这样的。首先，对于每一个连通块，答案显然是独立的。然后 …
lp4430 猴子打架/Prufer 序列
额…看起来是一道找规律题，实际上还是挺有门道的。 题目的题意就是，求 n 个点的点、边均有标号的生 …
lp4577 FJOI2018 领导集团问题
我们尝试类比序列上的情况来看这一题。 对于序列上的情况，我们维护一个集合 \(S\) ，其中 \(S_i\) …
CF102268C
贪心构造即可。 具体来说，如果把a依次标成-n…-1，那么只会有三种数：0（贡献是下标-1），n（贡献是0）以 …
CF1009F Dominant Indices
首先介绍一下我们亲爱的dsu on tree，也就是（一种？）树上启发式合并。 它本质上就是一种优化的暴力：对 …
lp1341 无序字母对
仔细观察这题：考虑到字母对可以反向，我们不妨把它们看作无序数对。这就把题意转化为了，给你n个无序数对，让你找到 …
lp4027 NOI2007 货币兑换
我们观察到，整个行为一定能被拆分为全买和全卖。 略微思考一下就可以证明这个定理。倘若先部分买再部分买，再全卖， …
lp2564 SCOI2009 生日礼物
尺取法即可。 开一个桶维护珍珠的颜色，然后扫一遍。每一次将最前端的点弹出，然后移动至下一个合法点。
lp2219 HAOI2007 修筑绿化带
我们知道，如果我们确定了每个大矩形包含的权值最小的小矩形，那么我们只需要枚举一遍每一个大矩形并比较它们的回形部 …
lp3313 SDOI2014 旅行
虽然这一题被划在主席树下面，但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。 树链剖分后我们考虑对每一 …
lp3285 SCOI2014 方伯伯的OJ
题目要求维护一个编号序列和一个排名序列，并支持四种操作： 1.按照编号修改编号，并返回该编号的排名。 2.将一 …
lp4768 NOI2018 归程
克鲁斯卡尔重构树模板题。 我们发现，这一题可以拆成两个步骤。第一个步骤，是找到所有u可以通过共享单车达到的点； …
lp3168 CQOI2015 任务查询系统
观察题面，我们发现这是一道变态题：区间加点，单点查询第k大，强制在线——这tm不是变态题么！别的不说，权值怎么 …
lp3302 SDOI2013 森林
我们发现，树上的链上第k大是可以使用主席树来维护的。对于每一个节点，我们从它的父亲复制一个版本，然后每一次求出 …
lp5395 【模板】第二类斯特林数·行
第二类斯特林数，指的是一组表示「将n个不同的元素划分为m个非空不相交集的方案数」的组合数。有时写作\(S(n, …
lp2501 HAOI2006 数字序列
我们分别考虑一二问。 对于第一问，我们思考一个子序列是合法的「不用修改」的子序列的充要条件。 容易想到的，这个 …
lp3233 HNOI2014 世界树
让我们来分析这道题。 我们很容易地可以发现，如果一个节点是末端节点，那么它肯定是由它祖先中的第一个节点管辖更优 …
lp4717 【模板】快速沃尔什变换
快速沃尔什变换是一种类似于快速傅里叶变换的操作。它是用来处理子集卷积的有效工具。 我们依次考虑操作符为and …
lp2622 关灯问题II
显然，对于某个状态，按下某个按钮之后，一定会得到另一个状态。 而灯的状态最大只有\(2^10\)。 故而考虑建 …
lp2519 HAOI2011 problem a
我们为每个考生设置一个可能的区间。这个区间的左端点是l=a+1，右端点是r=n-b。 仔细观察，会发现，这个可 …