并查集

介绍 这篇博客主要介绍一些并查集的高级应用。 目前我所知的并查集应用有: 权值并查集 可撤销并查集 可持久化并查集(还没学) 权值并查集 略,目前我所知的

最短路径树

介绍 最短路径树是指一个图,在以 某个点 为根,跑出来单源最短路以后,形成的树结构。 具体建树方法就是:在跑单源最短路的时候,用一个 pre[] 数组记录一下每

最小生成树

介绍 最小生成树就是给定一张边有权值的图,求一个生成树使得边权和最小。 最小生成树有着以下几个性质: 最小生成树不唯一,次小生成树可以通过枚举非树

Trie 和 01 Trie

介绍 01-Trie 指将整数拆成二进制,然后将二进制以字符串的形式储存在 Trie 中。 Trie可以解决以下问题: 给定一些数 $a_1,a_2,…,a_

单调队列

介绍 单调队列可以用于解决滑动窗口最值问题。 简单来说,单调队列内维护的是 index,单调队列要满足两个特性: q[tail] - q[head] < m,其中 $m$ 是窗口的大小。 队

基环树

定义 基环树指的是一个 $n$ 个节点,$n$ 条边的联通图。 叫基环树的原因是:给定一棵树,在这棵树上加上 任意一条边,就可以形成一个基环树了。 基环树的性

CCPC2020秦皇岛

排名 Solve: 5 (ADEFJ) Penalty: 767 Rank: 122/343 (35%) 题解 D - Exam Results 题意 给定 $n$ 个学生,第 $i$ 个学生的分数要么为 $a_i$,要么为 $b_i$。 给定整数 $P \in [1,100]$,如果最高

二次剩余

二次剩余用于解决在 模意义下开根 的问题: 题意 给定一个质数 $P$ 和一个非负整数 $N$,求 $x$ 使得 $$x^2 \equiv N (\text{mod } P)$$ 本问题等价于求 $$\sqrt N ~(\text{mod } P)$$ 性质 这个问题可能无

普通生成函数(OGF)

介绍 生成函数可以解决形如 满足XX条件的方案数共有多少种 的问题,它也能够解决 推导通项公式 等问题,生成函数常常与多项式运算结合在一起。 定义 对于一