目录

第 1章基础算法 ....................................1 4.3.4矩阵树定理 .................... 87 

1.1枚举 ..........................................1 4.4最短路问题 .............................. 90 

1.2模拟 ..........................................4 4.4.1 Dijkstra..........................90 

1.3递归 ..........................................7 4.4.2 Bellman-Ford..................90 

1.4分治基础 ...................................9 4.4.3 SPFA.............................91 

1.5贪心 ........................................16 4.4.4 Floyd.............................91 

1.6排序 ........................................ 204.5次短路与 k短路 ....................... 96 

4.6差分约束问题........................... 99  第 2章基础数据结构 ........................... 24 4.7拓扑排序 ................................101 

2.1栈和队列 ................................. 24 4.8连通性问题 .............................102 

2.2堆 ........................................... 27 4.8.1强连通分量 ...................102 

2.3并查集..................................... 30 4.8.2 2-SAT问题 ...................103 

2.4前缀和与差分........................... 35 4.8.3割点与割边 ...................104 

2.5树状数组 ................................. 38 4.9图的匹配问题..........................111 

2.6线段树..................................... 41 4.9.1二分图最大匹配 ............111 

2.7 ST表....................................... 46 4.9.2二分图最大权匹配 .........113 

2.8分块 ........................................ 48 4.9.3一般图最大匹配 ............115 

2.9莫队算法 ................................. 524.10支配树 ..................................118

第 3章搜索 ......................................... 57 第 5章高级数据结构 ..........................122 

3.1深度优先搜索........................... 57 5.1树链剖分 ................................122 

3.2宽度优先搜索........................... 58 5.2可持久化数据结构 ...................127 

3.3搜索优化策略........................... 62 5.2.1主席树..........................127 

3.3.1双向广搜 ....................... 62 5.2.2可持久化 trie.................131 

3.3.2剪枝 .............................. 64 5.3虚树 .......................................133 

3.3.3记忆化搜索 .................... 66 5.4平衡树....................................137 

3.3.4迭代加深搜索.................68 5.4.1 Treap............................137 

3.4 A. ........................................... 705.4.2伸展树..........................141 

5.5动态树....................................148  第 4章图论 ......................................... 74 5.6数据结构的嵌套 ......................152 

4.1图论基础 ................................. 74 5.7 K-Dimensional树 .....................156

4.1.1度和路径 ....................... 74 

4.1.2图的定义 ....................... 74 第 6章网络流 ....................................162 

4.1.3存储结构 ....................... 74 6.1最大流....................................162 

4.1.4树的直径 ....................... 75 6.1.1网络流概述 ...................162 

4.1.5欧拉回路 ....................... 76 6.1.2残余网络与增广路 .........163 

4.1.6哈密尔顿回路................. 77 6.1.3 Ford-Fulkerson算法 .......163 

4.2最近公共祖先........................... 79 6.1.4最小割最大流定理 .........164 

4.2.1 Tarjan法 ........................ 79 6.1.5 Dinic算法.....................165 

4.2.2倍增法........................... 79 6.2费用流....................................174 

4.2.3树链剖分法 .................... 80 6.3上下界网络流..........................178 

4.3生成树..................................... 80 6.3.1无源汇上下界可行流......178 

4.3.1 Prim算法 ...................... 80 6.3.2有源汇上下界网络流......179 

4.3.2 Kruskal算法 .................. 81 6.4常见模型 ................................180 

4.3.3次小生成树 .................... 84 6.4.1混合图欧拉回路 ............180 

程序设计算法基础 

6.4.2 最大权闭合子图 ............181 

6.4.3 动态加点 ......................181

第 7章动态规划 .................................183 

7.1动态规划基础..........................183 

7.1.1 线性动态规划................183 

7.1.2 多维动态规划................188 

7.2背包问题 ................................195 

7.2.1  01背包.........................195 

7.2.2 完全背包 ......................199 

7.2.3 多重背包 ......................203 

7.3状态压缩动态规划 ...................205 

7.4区间动态规划..........................210 

7.5树形动态规划..........................214 

7.6数位动态规划..........................219 

7.7概率期望动态规划 ...................224 

7.8插头动态规划..........................229 

7.9动态规划的优化 ......................234 

7.9.1 四边形不等式优化 .........234 

7.9.2 斜率优化 ......................238 

7.9.3 数据结构优化................240 

7.10动态规划例题 ........................245

第 8章分治 ........................................255 

8.1二分答案 ................................255 

8.2快速幂....................................260 

8.3 CDQ分治 ...............................263 

8.4整体二分 ................................268 

8.5树分治....................................273

第 9章数学 ........................................278 

9.1数学基础 ................................278 

9.1.1 组合数学基础................278 

9.1.2 线性代数基础................280 

9.1.3 数论基础 ......................284 

9.1.4 素数 .............................287 

9.2同余式....................................289 

9.2.1 同余方程 ......................289 

9.2.2 逆元 .............................290 

9.2.3 欧拉公式 ......................291 

9.2.4 欧拉降幂 ......................291 

9.2.5 中国剩余定理................292 

9.2.6 扩展中国剩余定理 .........293 

9.2.7 卢卡斯定理与扩展卢卡斯..........................293 

9.2.8 非对称加密—— RSA算法......................295 

9.3数论函数 ................................296 

9.3.1 积性函数 ......................296 

9.3.2 狄利克雷卷积................296 

9.3.3 莫比乌斯函数................297 

9.3.4 莫比乌斯反演................298 

9.3.5 杜教筛..........................300 

9.3.6  Min_25筛.....................303 

9.4数列 .......................................308 

9.4.1 卡特兰数 ......................308 

9.4.2 斐波那契数列................309 

9.4.3 伯努利数列 ...................314 

9.5多项式理论 .............................317 

9.5.1 傅里叶变换 ...................317 

9.5.2 原根 .............................322 

9.5.3 快速数论变换................323 

9.5.4 生成函数 ......................323 

9.6简单博弈 ................................336 

9.6.1 组合博弈模型及变形......336 

9.6.2  SG函数和 SG定理 ........344

第 10章字符串...................................347 

10.1 Hash算法..............................347 

10.2最小循环表示 ........................350 

10.3 Lyndon分解 ..........................352 

10.4 Manacher算法 .......................355 

10.5回文自动机 ...........................357 

10.6 KMP算法 .............................364 

10.7扩展 KMP算法......................371 

10.8字典树 ..................................376 

10.9 AC自动机.............................380 

10.10后缀数组 .............................389 

10.11后缀自动机..........................395

第 11章计算几何 ...............................407 

11.1计算几何基础 ........................407 

11.1.1 几何元素定义.............407 

11.1.2 向量的基本运算 .........408 

11.1.3 几何元素间的位置关系..........................411 

11.2凸包 .....................................416 

11.3半平面交...............................418 

11.4旋转卡壳...............................423 

11.5三维几何...............................427 

11.5.1 三维几何基础.............427 

11.5.2 三维凸包 ...................429

参考文献 ..............................................433