算法竞赛入门经典训练指南 刘汝佳 PDF格式 文字版 有书签目录
本书是《算法艺术与信息学竞赛》的学习指导。所谓学习指导,是告诉读者学什
么,如何学。算法包罗万象,很难在一本书中的篇幅覆盖很多内容的通知对每个知识
点进行细致讲解,因此本书更多的是作为一本导引、工具书、手册或者学习大纲,给
读者以宏观上的学习指导。和原书《算法艺术与信息学竞赛》相比,本书的特点有:
² 大量知识讲解。
² 更多循序渐进的习题。
² 重要算法的源代码。
从知识结构上看,本书的覆盖面比原书更广,补充了原书没有涉及到在知识点,
包括计算理论中的NP完全理论和图灵机的基本概念、数据结构中的伸展树、Treap,左
偏树、二项堆、Fibonacci堆、数论中的指数和原根、分解因数的快速算法、数值计算
中的高斯消元法和FFT、组合游戏论初步、更多序列经典问题和线段树、后缀数组等
数据结构的应用、树更多经典问题、多模式串匹配算法、后缀树构造的Ukkonen算法、
后缀数组构造的Skew算法、更加详细的强连通分量/双连通分量算法、最大流和最小费
用流算法、二分图和任意图的最大基数匹配算法和最大权匹配算法、稳定婚姻问题、
线性规划在网络优化中的作用、向量代数基础、多边形剖分算法、平面剖分、半平面
交、三维凸包、Voronoi图和直线排列的构造算法、几何对偶性的应用、Minkowski和与
简单运动规划问题等。
从题目上看,本书的题目集中在习题部分,这样保证知识讲解部分相对完整和纯
粹,也避免了用过多篇幅叙述和具体题目相关的内容。这些题目选择范围更广,难度
搭配也更加合理,且包含了常见的小技巧,和原书那些巧妙但难以理解的题目比较起
来更适合于初学者入门与提高,也为深入阅读原书打下了基础。
1