徐皓天 / 博客

CATEGORY

笔记

29 篇文章，按发布日期排列。

29 篇文章

闵可夫斯基和 学习笔记

笔记更新于 2026 年 5 月 6 日

给定两个点集，将其中的点两两做向量加法。由凸多边形的边合并，进一步理解 DP 中的卷积优化。

MY OI

笔记更新于 2020 年 8 月 23 日

NOI2020 加油！！！

k-D Tree 学习笔记

笔记

k-D Tree 是一种可以高效处理 k 维空间信息的数据结构，在算法竞赛的题目中一般 k = 2。

莫队 学习笔记

笔记

莫队算法是由莫涛提出的算法，可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。

生成函数 学习笔记

笔记更新于 2020 年 5 月 6 日

生成函数即母函数，是组合数学中尤其是计数方面的一个重要理论和工具。

动态 DP 学习笔记

笔记更新于 2020 年 3 月 19 日

动态 DP 在 NOIP2018D2T3 考察后风靡 OI 圈，然而我却一直没学。

原根 学习笔记

笔记更新于 2020 年 3 月 19 日

数论中的一个小概念，也是 NTT 的基础。

后缀自动机 学习笔记

笔记更新于 2020 年 7 月 29 日

因为 SA 就很有用了，所以一直不想学 SAM。突然不知道为什么就想学了，可能是为了吊打兔兔吧。 后缀自动机 (SAM) 是一个能解决许多字符串相关问题的有力的数据结构。 直观上，SAM 可以理解为将字符串的所有子串高度压缩至理论复杂度下界 O(n) 的形式。

二分图与网络流 学习笔记

笔记更新于 2024 年 4 月 25 日

本文于 2020.3.9 进行了全文更新。 本文包括了二分图与网络流的绝大部分重要知识点，限于篇幅和作者水平，本文省略了较多的证明过程和推导过程。 学习二分图与网络流，最重要的是大量的刷题。在更新时，作者思索再三，决定删掉所有【练习】。一个原因是，原本的习题结构太乱，并没有很好的…

虚树 学习笔记

笔记更新于 2020 年 4 月 3 日

又是以前学过的知识…… 对于一类特殊的树上问题，虚树通常可以简化树的结构，从而降低时间复杂度。

Z 函数 学习笔记

笔记

Z 函数，又称扩展 KMP (exkmp)，可以 O(n) 求出一个字符串的所有后缀与这个字符串的 LCP 长度。

Prufer 序列 学习笔记

笔记更新于 2020 年 2 月 12 日

Prufer 序列是一种将带标号的树用一个唯一的整数序列表示的方法。 在本文中，我们要求树的节点数 ≥ 2。

平衡树学习笔记

笔记更新于 2020 年 8 月 14 日

其实是学过的，然后，就忘了…… 本文介绍 Splay/Link Cut Tree/FHQ Treap 三种平衡树相关的数据结构。

长链剖分 学习笔记

笔记更新于 2020 年 2 月 21 日

长链剖分常用于优化一类特殊的动规，它可以在满足某些要求时，将 O(n) 的转移复杂度均摊为 O(1)。此外，长链剖分还有一些优秀的性质，目前长链剖分在信息学竞赛中应用很广泛。

矩阵树定理 学习笔记

笔记更新于 2020 年 6 月 26 日

Kirchhoff 矩阵树定理（简称矩阵树定理）解决了一张图的生成树个数计数问题。