比较重要的图论，tg 中考得比较多。
Luogu P7368 Asteroids G
Posted on
Symbols count in article: 1.9k Reading time ≈ 4 mins.
Symbols count in article: 1.9k Reading time ≈ 4 mins.
没人写 Dinic ，我就来一篇吧
P4897
Posted on
Symbols count in article: 3.7k Reading time ≈ 8 mins.
Symbols count in article: 3.7k Reading time ≈ 8 mins.
看大家都是倍增，我换一个简单点的方法吧。
网络流
Posted on
Symbols count in article: 2.5k Reading time ≈ 5 mins.
Symbols count in article: 2.5k Reading time ≈ 5 mins.
update: 2021-4-12 9:58 增加最小割的内容
P5192
Posted on
Symbols count in article: 5.4k Reading time ≈ 12 mins.
Symbols count in article: 5.4k Reading time ≈ 12 mins.
同步发表于 P5192 题解。
二分图
Posted on
Symbols count in article: 4.8k Reading time ≈ 10 mins.
Symbols count in article: 4.8k Reading time ≈ 10 mins.
简单的前置知识。
欧拉回路
Posted on
Symbols count in article: 2k Reading time ≈ 4 mins.
Symbols count in article: 2k Reading time ≈ 4 mins.
代码简单。
Manacher
Posted on
Symbols count in article: 1.9k Reading time ≈ 4 mins.
Symbols count in article: 1.9k Reading time ≈ 4 mins.
其实应用范围并不是很广。主要是预处理比较麻烦，而且很多问题回归原串的话是比较麻烦的。
并查集
Posted on
Symbols count in article: 5.3k Reading time ≈ 12 mins.
Symbols count in article: 5.3k Reading time ≈ 12 mins.
简单的前置知识。
树状数组
Posted on
Symbols count in article: 5.8k Reading time ≈ 13 mins.
Symbols count in article: 5.8k Reading time ≈ 13 mins.
简单的前置知识。
线段树
Posted on
Symbols count in article: 9.9k Reading time ≈ 22 mins.
Symbols count in article: 9.9k Reading time ≈ 22 mins.
非常重要的数据结构
Treap
Posted on
Symbols count in article: 4.3k Reading time ≈ 9 mins.
Symbols count in article: 4.3k Reading time ≈ 9 mins.
比较基础的平衡树。
二叉搜索树
Posted on
Symbols count in article: 499 Reading time ≈ 1 mins.
Symbols count in article: 499 Reading time ≈ 1 mins.
简单的前置知识。
树套树
Posted on
Symbols count in article: 7.3k Reading time ≈ 16 mins.
Symbols count in article: 7.3k Reading time ≈ 16 mins.
本质是一个区间通过线段树划分为 $\log n$ 个区间，每一个区间在分别维护，一般用 $O(\log n)$ 的数据结构，所以时间复杂度为 $O(n\log ^ 2 n)$，空间复杂度为 $O(n\log n)$，使用时注意空间。
AC 自动机
Posted on
Symbols count in article: 2.8k Reading time ≈ 6 mins.
Symbols count in article: 2.8k Reading time ≈ 6 mins.
字符串中相对比较难的知识点。
KMP algorithm
Posted on
Symbols count in article: 781 Reading time ≈ 2 mins.
Symbols count in article: 781 Reading time ≈ 2 mins.
比较简单的前置知识。
Sqrt algorithm
Posted on
Symbols count in article: 5.7k Reading time ≈ 12 mins.
Symbols count in article: 5.7k Reading time ≈ 12 mins.
优雅的暴力，注意可以在线。
莫队
Posted on
Symbols count in article: 12k Reading time ≈ 27 mins.
Symbols count in article: 12k Reading time ≈ 27 mins.
离线的区间统计一类问题的利器。
树链剖分
Posted on
Symbols count in article: 6.6k Reading time ≈ 14 mins.
Symbols count in article: 6.6k Reading time ≈ 14 mins.
可以将树上操作转化为区间操作。
左偏树
Posted on
Symbols count in article: 4k Reading time ≈ 9 mins.
Symbols count in article: 4k Reading time ≈ 9 mins.
又叫可合并堆。