forked from UPCACM/DuckKnowNothing
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmain.toc
executable file
·120 lines (120 loc) · 9.44 KB
/
main.toc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
\contentsline {section}{\numberline {1}字符串处理}{5}{section.1}
\contentsline {subsection}{\numberline {1.1}SAM}{5}{subsection.1.1}
\contentsline {subsection}{\numberline {1.2}AC自动机}{6}{subsection.1.2}
\contentsline {subsection}{\numberline {1.3}z-algorithm}{14}{subsection.1.3}
\contentsline {subsection}{\numberline {1.4}后缀数组}{15}{subsection.1.4}
\contentsline {subsection}{\numberline {1.5}最长上升子序列}{19}{subsection.1.5}
\contentsline {subsection}{\numberline {1.6}Manacher}{19}{subsection.1.6}
\contentsline {subsection}{\numberline {1.7}KMP}{20}{subsection.1.7}
\contentsline {subsection}{\numberline {1.8}ex-KMP}{21}{subsection.1.8}
\contentsline {subsection}{\numberline {1.9}Sunday}{22}{subsection.1.9}
\contentsline {subsection}{\numberline {1.10}字符串哈希}{23}{subsection.1.10}
\contentsline {subsection}{\numberline {1.11}字符串最大最小表示}{24}{subsection.1.11}
\contentsline {section}{\numberline {2}排序算法}{25}{section.2}
\contentsline {subsection}{\numberline {2.1}归并排序}{25}{subsection.2.1}
\contentsline {section}{\numberline {3}数学}{26}{section.3}
\contentsline {subsection}{\numberline {3.1}扩展欧几里得算法}{26}{subsection.3.1}
\contentsline {subsection}{\numberline {3.2}求逆元}{26}{subsection.3.2}
\contentsline {subsection}{\numberline {3.3}Miller robin素数检验}{27}{subsection.3.3}
\contentsline {subsection}{\numberline {3.4}快速傅里叶变换}{28}{subsection.3.4}
\contentsline {subsection}{\numberline {3.5}快速数论变换}{30}{subsection.3.5}
\contentsline {subsection}{\numberline {3.6}求原根}{32}{subsection.3.6}
\contentsline {subsection}{\numberline {3.7}BM黑盒线代}{34}{subsection.3.7}
\contentsline {subsection}{\numberline {3.8}FWT}{36}{subsection.3.8}
\contentsline {subsection}{\numberline {3.9}Simpson积分}{37}{subsection.3.9}
\contentsline {subsection}{\numberline {3.10}扩展欧拉定理}{37}{subsection.3.10}
\contentsline {subsection}{\numberline {3.11}杜教筛}{38}{subsection.3.11}
\contentsline {subsection}{\numberline {3.12}Pell方程}{38}{subsection.3.12}
\contentsline {subsection}{\numberline {3.13}莫比乌斯反演}{39}{subsection.3.13}
\contentsline {subsection}{\numberline {3.14}常用素数}{39}{subsection.3.14}
\contentsline {subsection}{\numberline {3.15}快速取模乘}{40}{subsection.3.15}
\contentsline {subsection}{\numberline {3.16}多项式算法(逆元,exp,ln)}{42}{subsection.3.16}
\contentsline {subsection}{\numberline {3.17}gcd}{46}{subsection.3.17}
\contentsline {subsection}{\numberline {3.18}Eratosthenes素数筛}{46}{subsection.3.18}
\contentsline {subsection}{\numberline {3.19}扩展BSGS}{47}{subsection.3.19}
\contentsline {subsection}{\numberline {3.20}欧拉函数}{49}{subsection.3.20}
\contentsline {subsection}{\numberline {3.21}矩阵快速幂}{50}{subsection.3.21}
\contentsline {subsection}{\numberline {3.22}组合数}{54}{subsection.3.22}
\contentsline {subsection}{\numberline {3.23}长整型无脑取模乘}{60}{subsection.3.23}
\contentsline {section}{\numberline {4}数据结构}{60}{section.4}
\contentsline {subsection}{\numberline {4.1}KD-Tree}{60}{subsection.4.1}
\contentsline {subsection}{\numberline {4.2}李超树}{63}{subsection.4.2}
\contentsline {subsection}{\numberline {4.3}左偏树\&优先队列}{64}{subsection.4.3}
\contentsline {subsection}{\numberline {4.4}树链剖分}{67}{subsection.4.4}
\contentsline {subsection}{\numberline {4.5}Treap}{76}{subsection.4.5}
\contentsline {subsection}{\numberline {4.6}线段树}{83}{subsection.4.6}
\contentsline {subsection}{\numberline {4.7}主席树}{85}{subsection.4.7}
\contentsline {subsection}{\numberline {4.8}二叉查找树}{89}{subsection.4.8}
\contentsline {subsection}{\numberline {4.9}Splay}{93}{subsection.4.9}
\contentsline {subsection}{\numberline {4.10}线段树}{102}{subsection.4.10}
\contentsline {subsection}{\numberline {4.11}二叉堆\&优先队列}{104}{subsection.4.11}
\contentsline {subsection}{\numberline {4.12}树状数组}{107}{subsection.4.12}
\contentsline {subsection}{\numberline {4.13}二维树状数组}{108}{subsection.4.13}
\contentsline {subsection}{\numberline {4.14}可持久化Trie树}{109}{subsection.4.14}
\contentsline {subsection}{\numberline {4.15}并查集}{111}{subsection.4.15}
\contentsline {subsection}{\numberline {4.16}栈\&队列}{111}{subsection.4.16}
\contentsline {subsubsection}{\numberline {4.16.1}单调栈}{111}{subsubsection.4.16.1}
\contentsline {subsubsection}{\numberline {4.16.2}队列}{112}{subsubsection.4.16.2}
\contentsline {subsubsection}{\numberline {4.16.3}单调队列}{113}{subsubsection.4.16.3}
\contentsline {section}{\numberline {5}动态规划}{114}{section.5}
\contentsline {subsection}{\numberline {5.1}数位dp}{114}{subsection.5.1}
\contentsline {subsection}{\numberline {5.2}状态压缩}{115}{subsection.5.2}
\contentsline {subsection}{\numberline {5.3}背包问题}{115}{subsection.5.3}
\contentsline {subsubsection}{\numberline {5.3.1}01背包}{115}{subsubsection.5.3.1}
\contentsline {subsubsection}{\numberline {5.3.2}多重背包}{115}{subsubsection.5.3.2}
\contentsline {subsubsection}{\numberline {5.3.3}完全背包}{116}{subsubsection.5.3.3}
\contentsline {section}{\numberline {6}图论}{116}{section.6}
\contentsline {subsection}{\numberline {6.1}二分图}{116}{subsection.6.1}
\contentsline {subsubsection}{\numberline {6.1.1}KM}{116}{subsubsection.6.1.1}
\contentsline {subsubsection}{\numberline {6.1.2}匈牙利}{121}{subsubsection.6.1.2}
\contentsline {subsection}{\numberline {6.2}拓扑排序}{123}{subsection.6.2}
\contentsline {subsubsection}{\numberline {6.2.1}DFS拓扑排序}{123}{subsubsection.6.2.1}
\contentsline {subsubsection}{\numberline {6.2.2}Kahn拓扑排序}{124}{subsubsection.6.2.2}
\contentsline {subsection}{\numberline {6.3}最短路}{126}{subsection.6.3}
\contentsline {subsubsection}{\numberline {6.3.1}堆优化Dijkstra}{126}{subsubsection.6.3.1}
\contentsline {subsubsection}{\numberline {6.3.2}SPFA}{127}{subsubsection.6.3.2}
\contentsline {subsubsection}{\numberline {6.3.3}次短路Dijkstra}{128}{subsubsection.6.3.3}
\contentsline {subsubsection}{\numberline {6.3.4}AStar}{129}{subsubsection.6.3.4}
\contentsline {subsection}{\numberline {6.4}网络流}{131}{subsection.6.4}
\contentsline {subsubsection}{\numberline {6.4.1}Dinic}{131}{subsubsection.6.4.1}
\contentsline {subsubsection}{\numberline {6.4.2}MCMF}{133}{subsubsection.6.4.2}
\contentsline {subsection}{\numberline {6.5}连通图}{135}{subsection.6.5}
\contentsline {subsubsection}{\numberline {6.5.1}割边}{135}{subsubsection.6.5.1}
\contentsline {subsubsection}{\numberline {6.5.2}连通图Tarjan}{136}{subsubsection.6.5.2}
\contentsline {section}{\numberline {7}树}{137}{section.7}
\contentsline {subsection}{\numberline {7.1}LCA}{137}{subsection.7.1}
\contentsline {subsubsection}{\numberline {7.1.1}RMQ-ST}{137}{subsubsection.7.1.1}
\contentsline {subsubsection}{\numberline {7.1.2}Tarjan并查集}{138}{subsubsection.7.1.2}
\contentsline {subsubsection}{\numberline {7.1.3}倍增算法}{141}{subsubsection.7.1.3}
\contentsline {subsection}{\numberline {7.2}最小生成树}{142}{subsection.7.2}
\contentsline {subsubsection}{\numberline {7.2.1}O(elog2v)-primMST}{142}{subsubsection.7.2.1}
\contentsline {subsubsection}{\numberline {7.2.2}O(elogv)-prim+heap MST}{143}{subsubsection.7.2.2}
\contentsline {section}{\numberline {8}计算几何}{145}{section.8}
\contentsline {subsection}{\numberline {8.1}基础定义}{145}{subsection.8.1}
\contentsline {subsection}{\numberline {8.2}点}{145}{subsection.8.2}
\contentsline {subsection}{\numberline {8.3}线}{146}{subsection.8.3}
\contentsline {subsection}{\numberline {8.4}凸包}{148}{subsection.8.4}
\contentsline {subsection}{\numberline {8.5}三角形}{152}{subsection.8.5}
\contentsline {subsection}{\numberline {8.6}圆}{153}{subsection.8.6}
\contentsline {subsection}{\numberline {8.7}O(n)-求凸包 \& 旋转卡壳}{156}{subsection.8.7}
\contentsline {subsection}{\numberline {8.8}两圆相交面积}{158}{subsection.8.8}
\contentsline {subsection}{\numberline {8.9}两直线交点}{159}{subsection.8.9}
\contentsline {subsection}{\numberline {8.10}点在直线上的垂点}{159}{subsection.8.10}
\contentsline {subsection}{\numberline {8.11}矩形面积交}{159}{subsection.8.11}
\contentsline {subsection}{\numberline {8.12}线段类}{160}{subsection.8.12}
\contentsline {subsection}{\numberline {8.13}计算三角形外心}{162}{subsection.8.13}
\contentsline {section}{\numberline {9}STL}{164}{section.9}
\contentsline {subsection}{\numberline {9.1}accumulate}{164}{subsection.9.1}
\contentsline {section}{\numberline {10}其他}{164}{section.10}
\contentsline {subsection}{\numberline {10.1}约瑟夫问题}{164}{subsection.10.1}
\contentsline {subsection}{\numberline {10.2}RMQ-ST}{165}{subsection.10.2}
\contentsline {subsection}{\numberline {10.3}一些理论}{165}{subsection.10.3}
\contentsline {subsection}{\numberline {10.4}随机数和文件输出}{166}{subsection.10.4}
\contentsline {subsection}{\numberline {10.5}随机遍历数组}{166}{subsection.10.5}
\contentsline {subsection}{\numberline {10.6}尺取}{167}{subsection.10.6}
\contentsline {subsection}{\numberline {10.7}std::unordered\_map避免TLE}{167}{subsection.10.7}
\contentsline {subsection}{\numberline {10.8}输入输出挂}{168}{subsection.10.8}
\contentsline {subsection}{\numberline {10.9}CDQ分治}{170}{subsection.10.9}
\contentsline {subsection}{\numberline {10.10}vim配置}{172}{subsection.10.10}
\contentsline {subsection}{\numberline {10.11}程序对拍器}{173}{subsection.10.11}
\contentsline {subsection}{\numberline {10.12}简易对排器}{174}{subsection.10.12}