ICPC2020澳门

例1 A. Accelerator 题意 给定 $n$ 个正整数 $a_1,a_2,…,a_n$,它们总共有 $n!$ 种 permutation。 对于每一种 permutation $a_{k_1},

二维差分

介绍 一维差分可以用于解决以下问题: 给定一系列的区间加/减操作,最后询问整个数组的元素。 那么二维差分就可以解决: 给定一系列的矩阵加/减操作,最

树套树

介绍 树套树常常用于解决一些二维数点问题。 经典的问题如:矩阵内查询和/最大值,更新矩阵内一个点的值等等。 在介绍树套树之前,先简单讲一下树状数组

组合数学

本文主要记录一些组合数学的常用模型。 组合数 $C(n,m)$ $C_n^0 = C_n^n = 1$ $C_n^k = C_{n-1}^k + C_{n-1}^{k-1}$ $C_n^k = \frac{n!}{k!(n-k)!}$ 注:$0! = 1, (0!)^{-1} = 1$ 证明公式2 $n$ 个中选 $k$ 个, 考虑 $n$ 个元素中的第一个元素

拉格朗日插值

拉格朗日插值 给定 $n$ 个点,我们可以确定唯一的最高 degree 为 $(n-1)$ 的多项式。 设多项式为 $f(x)$,第 $i$ 个点的坐标为 $(x_i,y_i)$,那么这个多项式

最大权闭合子图

定义 闭合子图 对于一个 有向图 $G=(V,E)$,它的一个闭合子图 $G'=(V’,E’)$ 满足: $\forall u \in V'$,如果 $(u,v) \in E$,则 $v \in V’, (u,v) \in E'$ 简单来说,就是对于子图中的每

并查集

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

最短路径树

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

最小生成树

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