复习导引
复习导引
Part1 序列类
- 多功能型：
1.1分块，莫队(奇偶排序加速莫队)
1.2树状数组
1.3线段树，函数式线段树，可持久化函数式线段树(主席树)，\(\text{Segmentbeats}\)(吉老师树) , \(\text{ZKW}\)线段树，线段树合并
1.4二叉堆，左偏树，配对堆，可持久化左偏树
1.5平衡树：\(\text{Splay}\)，\(\text{Treap}\)，非旋\(\text{Treap}\)，可以持久化非旋\(\text{Treap}\)
1.6李超树
17.线段树分治，半动态线段树分治（一边分治一边得到加边的范围）
1.7\(\text{K-D Tree}\)
1.8树套树，\(\text{CDQ}\)分治，高维问题
1.9莫队二次离线
2.特殊型：
2.1单调栈/单调队列，\(\text{Sparse\_Table}\)，笛卡尔树
2.2并查集，按秩合并，可持久化并查集
(2.3猫树，珂朵莉树)
\[ \ \]
\[ \ \]
\[ \ \]
\[ \ \]
dp
1.决策单调性
分治决策单调性，四边形不等式
2.斜率优化
单调栈/单调队列维护凸包，单调队列查询或者二分单调栈
以及李超树暴力维护
3.分数规划
形如求\(\displaystyle(\frac{p}{q})_{max}\)的，二分答案\(k\)然后求\((p-kq)_{max}\)，称为分数规划
4.数位dp
注意 正向/逆向dp 的大小判断方法
5.插头dp
熟悉二进制维护状态的方法
6.有限自动机上的\(dp\)状态定义
7.花样容斥
7.1奇偶容斥\((-1)^{j-i}\)，二项式反演
7.2\(\text{MinMax}\)容斥 [ZJOI2020] 抽卡70分做法
7.3分层图容斥(巨神兵)
8.状态割裂 (COCI20162017 Contest#6 F)
9.二项展开/斯特林数展开求\((\sum)^k\)
10.小体积的背包问题
11.降阶子问题[HDU-6848]
12.\(dp\)套\(dp\)
13.无限问题的循环节\(dp\) 「CTS2019 | CTSC2019」重复
14.树上动态\(dp\)
15.\(\text{dfs}\)序\(dp\) [HDU-5909] 「清华集训2016」连通子树
16.斯坦纳树 「THUSCH 2017」巧克力
\[ \ \]
\[ \ \]
\[ \ \]
树上
1.倍增，树剖，\(\text{tarjan LCA}\)，\(\text{Euler}\)序\(\text{LCA}\)
2.合并连通块的直径
3.\(\text{DSU on Tree}\)
4.点分治/边分治，动态点分治
边分治：将多度点建立虚边，下分为二叉树，然后找到边中心
5.虚树
6.树\(\text{hash}\)
7.\(\text{Kruskal}\)重构树
8.\(\text{Prufer}\)序列\((n^{n-2})\)
9.最小树形图[朱-刘算法]
10.多树问题：点分治+虚树+数据结构
11.\(\text{LCT}\)
(12.\(\text{Top Tree}\))
(13.树分块)
图论/线性规划
\(G=(V,E)\)
1.点双，边双
2.基环树
3.仙人掌，圆方树
4.\(\text{SPFA,Dijkstra,Johnson}\)
5.差分约束
6.网络流，预流推进，费用流，\(\text{Dijkstra}\)费用流，上下界网络流，最大流/最小割树，(\(\text{Stoer-Wagner}\)算法)
7.二分图匈牙利，一般图带花树，带权\(\text{Kuhn–Munkres}\)(注意复习Luogu/UOJ上的\(\text{BFS}\)版本)
8.\(2-\text{sat}\)，注意方案输出方法
9.欧拉回路(UOJ模板)，(哈密顿路？)
10.平面图的欧拉定理
(11.弦图)
12.对偶
13.单纯形
14.拟阵交
\[ \ \]
\[ \ \]
\[ \ \]
字符串
1.\(\text{hash,kmp,AC Automaton}\)
2.\(\text{Manacher}\)(马拉车。。)，\(\text{Palindrome Automaton}\)(回文自动机)
3.\(SA\)后缀数组(倍增,DC3,SAIS)，\(SAM\)后缀自动机，广义\(\text{SAM}\)(多串)
\(\text{SA}:\)常见：按照\(\text{LCP}\)大小分段进行统计
\(\text{SAM}:\)结合树，\(\text{LCA}\)
4.\(\text{Trie}\)即可持久化
5.\(\text{Period,Border}\)
6.(\(\text{Exkmp}(Z\)函数\()\))
7.\(\text{Lyndon}\)分解
8.最小循环同构\(O(n)\)
9.\(\text{Runs}\)
\[ \ \]
\[ \ \]
\[ \ \]
\[ \ \]
贪心/博弈/结论
1.\(\text{Nim}\)，反\(\text{Nim}\)，\(k\)进制\(\text{Nim}\) (CodeChef November Challenge2019 Winning Ways)
2.威佐夫博弈
\[ \ \]
\[ \ \]
\[ \ \]
数学
\(\text{Matrix-Tree}\)定理即扩展
11.\(\text{DAG}\)的\(\text{LGV}\)引理 [HDU-5852]
\[ \ \]
\[ \ \]
\[ \ \]
\[ \ \]