【笔记】Borůvka's Algorithm

Borůvka 算法是一种计算图最小生成树的贪心算法,于 1926 年被 Otakar Borůvka 首次发表。 基本原理 首先,我们会找到图上每个节点到其他节点的最短边,然后把这些边加入森林中。我们不断重复这个过程,即每次给森林中每棵树找到连接其他树的最短边,然后将这样的边加入森林。 每次操作会减少森林中树的数量至少一半,于是我们可以在对数次操作内完成这个算法。 均摊复杂度为 $\Theta((n+m)\log n)$。 典型例题 对于大多数的图,Kruskal 和 Prim 已经非常优秀了。这里我们给出一个特殊情况,在这种情况下 Borůvka 的效率比前两者高得多。 给定 $n$ 个二维平面内的点,两点之间边权为两点的曼哈顿距离,求这些点的最大生成树大小。 在这里,图中边的数量达到了 $n^2$ 级别,不适宜直接计算。 因为边权是曼哈顿距离,我们发现我们可以较快地算出对于每棵树,到它距离最远的点的距离,Borůvka 算法可以在 $\Theta(…

【笔记】线图 / Line graph

在图论中,一张无向图的线图是能体现其连边状态的一种生成图。有关线图的中文资料很少,但有关它的外文资料非常丰富。在这篇文章中,我将简单介绍线图的定义,以及提出计算线图最小生成树大小的一种方法。 Formal definition 给定一张无向图 $G$,它的线图 $L(G)$ 满足以下条件 $L(G)$ 中的每个节点表示 $G$ 中的一条边;$L(G)$ 中两个节点之间连边,当且仅当它们代表的边在 $G$ 中有公共点。 Example 下面展示了一张图(蓝色节点)和它的线图(绿色节点),线图上每个节点标出了原图上边两个端点的编号。 Minimum spanning tree 现在我们有一张无向图 $G$ 和它的线图 $L(G)$。如果我们我们把图 $G$ 的点和边都赋上权值,在 $L(G)$ 中,我们可以认为点权为原图中对应边的边权,边权为原图中对应公共点的点权。 我们解决这个问题的思路都基于…

【笔记】快速沃尔什变换入门

概念 快速沃尔什变换是一种类似 FFT,用来加速逻辑位运算卷积的算法。具体地,它被设计为用来解决以下问题: $$C_k=\sum_{i\oplus j=k}a_i\times b_j$$ 其中,$\oplus$ 表示位运算 $\lor, \wedge, \veebar$。直接枚举 $i,j$ 的复杂度是 $\Theta(n^2)$,FWT 能加速这个过程到 $\Theta(n\log n)$。 原理 前面说到它类似 FFT,因为它们都是通过先做一个变换,相乘,然后逆变换得到结果的,而变换的过程都是折半、分治。 我们定义变换为 $tf$,有 $$tf(C)…

【笔记】从傅里叶变换到数论变换

概述 我们可以使用傅里叶变换来快速计算卷积。然而快速傅立叶变换具有一些实现上的缺点,我们必须做复数而且是浮点数的运算,因此计算量会比较大,而且浮点数运算产生的误差会比较大。 这个问题可以用数论变换解决。在模意义下,一些整数可以发挥单位复根的作用,使我们更精确地计算只有整数参加的卷积运算结果。 原根 概念 在 $FFT$ 中,我们利用了单位复根的以下性质: $\omega_n^k$ 互不相同;$\omega_{2n}^{2k}=\omega_n^k$;$\omega_n^{k+\frac{n}{2}}=-\omega_n^k$当 $k \neq 0$ 时,$1+\omega_n^k+(\omega_n^k)^2+\cdots+…

【Note】Palindromic Tree / 回文树

这篇文章将提出 回文树 的概念,一种解决回文串相关问题的优美数据结构。 感谢它的发明者 Mikhail Rubinchik,在 Petrozavodsk Summer Camp 2014 中向我们讲述了这一概念,使得这篇文章的创作成为可能。 结构 和其他所有树形结构一样,回文树由节点构成。在这里,每个节点代表了一个回文串。 四节点回文树的样例 在节点之间有边相连。一条从 $u$ 连至 $v$ 的树边上会标有一个字母 $x$,表示在 $u$ 处的回文串左右加上一个 $x$ 得到 $v$ 处的回文串。 ‘aba’ 由 ‘b’ 在左右两边各添加一个 ‘a’ 得来 同时也存在着一些非树边,我们称之为 $fail$ 指针。…

【Note】FHQTreap / 非旋 Treap

定义 当我们提到 “Treap” 的时候,我们实际上说的是 “Tree” + “Heap”。Treap 的每个节点拥有两个值:”Key” 和 “Val”。其中 “Key” 满足堆的性质,而 “Val” 满足二叉搜索树的性质。 朴素的 Treap 在插入的时候给每个点一个随机的 Key,通过旋转来满足堆的性质。对于 FHQTreap,我们不再使用旋转维护,转而使用拆分和合并。 核心操作 拆分 我们将一个 Treap 按特定的值 Val 拆分成两个 Treap –…

【Note】Minkowski sum / 闵可夫斯基和

The red figure is the Minkowski sum of blue and green figures. ©Wikipedia 概念 闵可夫斯基和是两个欧几里得空间的点集的和,以德国数学家闵可夫斯基命名。我们这样定义点集 $A$ 和 $B$ 的闵可夫斯基和: $$A+B=\{a+b \ | \ a \in A,b \in B \}$$ 类似地,闵可夫斯基差可以被定义为: $$A-B=\{c \ | \ c +B \subseteq A\} $$ 计算方法 考虑点集 $A + B$ 的凸包上的每一个点 $c = a + b$,那么 $a$ 一定位于…

【学习笔记】快速傅里叶变换

12/20/2018 重写。 概述 快速傅里叶变换(Fast Fourier Transform,FFT)是一种可在 $\Theta(n \log n)$ 时间内完成的离散傅里叶变换(Discrete Fourier transform,DFT)算法。 这篇文章将简单地讲解它的工作原理,以及使用 C++ 的代码实现。 基本概念 多项式 在数学中,由若干个单项式相加组成的代数式叫做多项式。多项式中的每个单项式叫做多项式的项,这些单项式中的最高项次数,就是这个多项式的次数。 系数表示 设 $A(x)$ 表示一个 $n-1$ 次多项式,所有项系数组成的 $n$ 维向量 $(a_0,a_1,\cdots,a_…