ACM/ICPC算法训练教程 余立功著 PDF下载

ACM 国际大学生程序设计竞赛(ACM/ICPC)是由国际计算机界历史悠久、颇具权威性 的组织 ACM 学会主办，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛， 其目的旨在使大学生运用计算机来充分展示自已分析问题和解决问题的能力。 因历届竞都赛 荟萃了世界各大洲的精英，云集了计算机界的“希望之星”，而受到国际各知名大学的重视， 并受到全世界各著名计算机公司的高度关注， 成为世界各国大学生最具影响力的国际级算计 机类的赛事。

南京理工大学参与该项赛事八年， 获得亚洲区银奖5 个， 铜奖12 个。 同时在训练中也 积累了一些训练的资料。南京理工大学ACM/ICPC 集训队根据多年训练积累，整理的 《ACM/ICPC 算法训练教程》适合 ACM/ICPC 初学者，及具有一定基础的计算机算法和编 程爱好者。适合作为本科及研究生算法与数据结构类课程的参考教材。

本书资料全部来自南京理工大学 ACM/ICPC 集训队内部资料。 由张珂、 张俊华等集训 队员负责整理。因成书仓促，错误在所难免，望批评指正。

序                                                                              

第一章算法基础                                                                  

1.1穷举（枚举）法                                                               

1.2递归法                                                                       

1.3分治法                                                                       

1.4贪心法                                                                       

1.5模拟法                                                                       

第二章：数据结构                                                                

2.1引言                                                                         

2.2基本数据结构                                                                 

2.3查找与排序                                                                   

2.4并查集                                                                       

2.5堆（优先队列）                                                               

2.6Hash表                                                                       

2.7线段树                                                                       

第三章数论                                                                      

3.1和素数有关的问题                                                             

3.1.1素数基础                                                                   

3.1.2素数问题举例                                                               

3.2最大公约数欧几里得及扩展欧几里得算法                                         

3.2.1欧几里得与扩展欧几里得简介                                                 

3.2.2欧几里得与扩展欧几里得举例                                                 

3.3整数因子分解                                                                 

3.3.1整数因子分解简介                                                           

3.3.2整数因子分解举例                                                           

第四章计算几何                                                                  

4.1计算几何的基础——矢量                                                       

4.1.1矢量基础                                                                   

4.2确定任意一对线段是否相交                                                     

4.3寻找凸包                                                                     

4.3.1寻找凸包                                                                   

4.3.2凸包举例                                                                   

4.4寻找最近点对                                                                 

4.4.1寻找最近点对方案                                                           

第五章图算法                                                                    

5.1引言                                                                         

5.2最小生成树                                                                   

5.2.1Prim算法                                                                   

5.2.2Kruskal算法                                                                

5.3最短路算法                                                                   

5.3.1Dijkstra算法                                                               

5.3.2Bellman-Ford算法                                                           

5.3.3Floyd-Warshall算法                                                         

5.4无向图的连通性                                                               

5.4.1无向连通图割点和桥                                                         

5.4.2欧拉图问题                                                                 

5.5有向图的强连通分量                                                           

5.5.1Kosaraju算法                                                               

5.5.2Tarjan算法                                                                 

5.5.3Gabow算法                                                                  

6.1概要                                                                         

6.2深度优先搜索（DFS——DepthFirstsearch）                                      

6.3广度优先搜索（BFS——BreadthFirstSearch）                                    

6.4启发式搜索(介于深搜与宽搜之间的搜索)                                         

6.5双向宽搜                                                                     

6.6总结                                                                         

第七章网络流算法                                                                

7.1网络流的一般概念                                                             

7.1.1网络流的一些基本符号                                                       

7.1.2网络流的三个性质                                                           

7.2最大流                                                                       

7.2.1网络流的定义                                                               

7.2.2增广路法                                                                   

7.3有上下界网络的最大流和最小流                                                 

7.4网络流的预流推进算法                                                         

7.5最小费用最大流                                                               

第八章动态规划                                                                  

8.1动态规划简介                                                                 

8.2动态规划例题                                                                 

第九章字符串                                                                    

9.1KMP算法                                                                      

9.1.1算法介绍                                                                   

9.1.2next指针                                                                   

9.2字典树（Tries）                                                              

9.3AC自动机                                                                     

9.4后缀数组                                                                     

9.4.1基本概念                                                                   

9.4.2后缀数组的构造                                                             

9.4.3后缀数组的应用