具体描述
《算法竞赛入门经典:训练指南》是《算法竞赛入门经典》的重要补充，旨在补充原书中没有涉及或者讲解得不够详细的内容，从而构建一个较完整的知识体系，并且用大量有针对性的题目，让抽象复杂的算法和数学具体化、实用化。《算法竞赛入门经典:训练指南》共6章，分别为算法设计基础、数学基础、实用数据结构、几何问题、图论算法与模型和更多算法专题，全书通过近200道例题深入浅出地介绍了上述领域的各个知识点、经典思维方式以及程序实现的常见方法和技巧，并在章末和附录中给出了丰富的分类习题，供读者查漏补缺和强化学习效果。
作者简介
目录信息
第1章 算法设计基础 1
1.1 思维的体操 1
1.2 问题求解常见策略 15
1.3 高效算法设计举例 39
1.4 动态规划专题 60
1.5 小结与习题 77
第2章 数学基础 103
2.1 基本计数方法 103
2.2 递推关系 109
2.3 数论 119
2.3.1 基本概念 119
2.3.2 模方程 126
2.4 组合游戏 132
2.5 概率与数学期望 139
2.6 置换及其应用 144
2.7 矩阵和线性方程组 151
2.8 数值方法简介 163
2.9 小结与习题 170
第3章 实用数据结构 186
3.1 基础数据结构回顾 186
3.1.1 抽象数据类型（ADT） 186
3.1.2 优先队列 188
3.1.3 并查集 191
3.2 区间信息的维护与查询 194
3.2.1 二叉索引树（树状数组） 194
3.2.2 RMQ问题 197
3.2.3 线段树（1）：点修改 199
3.2.4 线段树（2）：区间修改 202
3.3 字符串（1） 208
3.3.1 Trie 208
3.3.2 KMP算法 211
3.3.3 Aho-Corasick自动机 214
3.4 字符串（2） 219
3.4.1 后缀数组 219
3.4.2 最长公共前缀（LCP） 222
3.4.3 基于哈希值的LCP算法 224
3.5 排序二叉树 227
3.5.1 基本概念 227
3.5.2 用Treap实现名次树 230
3.5.3 用伸展树实现可分裂与合并的序列 239
3.6 小结与习题 244
第4章 几何问题 254
4.1 二维几何基础 254
4.1.1 基本运算 255
4.1.2 点和直线 256
4.1.3 多边形 258
4.1.4 例题选讲 259
4.1.5 二维几何小结 263
4.2 与圆和球有关的计算问题 264
4.2.1 圆的相关计算 264
4.2.2 球面相关问题 269
4.3 二维几何常用算法 270
4.3.1 点在多边形内判定 270
4.3.2 凸包 271
4.3.3 半平面交 276
4.3.4 平面区域 282
4.4 三维几何基础 286
4.4.1 三维点积 287
4.4.2 三维叉积 288
4.4.3 三维凸包 290
4.4.4 例题选讲 292
4.4.5 三维几何小结 295
4.5 小结与习题 296
第5章 图论算法与模型 307
5.1 基础题目选讲 307
5.2 深度优先遍历 310
5.2.1 无向图的割顶和桥 312
5.2.2 无向图的双连通分量 314
5.2.3 有向图的强连通分量 319
5.2.4 2-SAT问题 323
5.3 最短路问题 327
5.3.1 再谈Dijkstra算法 327
5.3.2 再谈Bellman-Ford算法 332
5.3.3 例题选讲 335
5.4 生成树相关问题 343
5.5 二分图匹配 347
5.5.1 二分图最大匹配 347
5.5.2 二分图最佳完美匹配 348
5.5.3 稳定婚姻问题 352
5.5.4 常见模型 355
5.6 网络流问题 357
5.6.1 最短增广路算法 358
5.6.2 最小费用最大流算法 363
5.6.3 建模与模型变换 365
5.6.4 例题选讲 368
5.7 小结与习题 372
第6章 更多算法专题 383
6.1 轮廓线动态规划 383
6.2 嵌套和分块数据结构 389
6.3 暴力法专题 395
6.3.1 路径寻找问题 395
6.3.2 对抗搜索 400
6.3.3 精确覆盖问题和DLX算法 406
6.4 几何专题 412
6.4.1 仿射变换与矩阵 412
6.4.2 离散化和扫描法 414
6.4.3 运动规划 423
6.5 数学专题 425
6.5.1 小专题集锦 425
6.5.2 快速傅里叶变换（FFT） 428
6.5.3 线性规划 430
6.6 浅谈代码设计与静态查错 431
6.6.1 简单的Bash 431
6.6.2 《仙剑奇侠传四》之最后的战役 440
6.7 小结与习题 447
附录A 训练指南：使用UVa/LA题库 481
A.1 UVa在线比赛推荐 481
A.2 LA套题（ACM/ICPC真题）推荐 482
A.3 UVa在线比赛单题推荐 483
附录B Java、C#和Python语言简介 505
B.1 Java 505
B.2 C# 507
B.3 Python 509
· · · · · · (收起)
读后感
1. p149 f(i,j) = f(i-1,j-1)+f(i-1,j)*(i-1) 应该改为 f(i,j) = f(i-1,j-1)*(i-1)+f(i-1,j) ——————————————————————————————
1. p149 f(i,j) = f(i-1,j-1)+f(i-1,j)*(i-1) 应该改为 f(i,j) = f(i-1,j-1)*(i-1)+f(i-1,j) ——————————————————————————————
1. p149 f(i,j) = f(i-1,j-1)+f(i-1,j)*(i-1) 应该改为 f(i,j) = f(i-1,j-1)*(i-1)+f(i-1,j) ——————————————————————————————
1. p149 f(i,j) = f(i-1,j-1)+f(i-1,j)*(i-1) 应该改为 f(i,j) = f(i-1,j-1)*(i-1)+f(i-1,j) ——————————————————————————————
1. p149 f(i,j) = f(i-1,j-1)+f(i-1,j)*(i-1) 应该改为 f(i,j) = f(i-1,j-1)*(i-1)+f(i-1,j) ——————————————————————————————
用户评价
初次接触算法竞赛，选择《算法竞赛入门经典》纯属偶然，当时只是被它简洁的书名所吸引。拿到书后，我便迫不及待地翻开。书中详实的内容，严谨的逻辑，以及由浅入深的讲解方式，让我这样一个对算法几乎一无所知的新手，也能感受到学习的乐趣。作者深入浅出地剖析了许多基础但至关重要的算法概念，从简单的排序、搜索，到更复杂的图论、动态规划，每一步都伴随着清晰的代码示例和深入的原理阐释。我尤其喜欢书中对各种数据结构的应用讲解，比如如何巧妙地利用栈来解决括号匹配问题，或者用队列实现广度优先搜索。这些知识点看似零散，但在作者的引导下，它们逐渐串联成了一个完整的知识体系。更重要的是，书中提供的例题和练习题，难度梯度合理，既能巩固刚学到的知识，又能激发解决问题的兴趣。我常常会花很长时间去钻研一道题，尝试不同的思路，最终在成功解决问题的那一刻，获得巨大的成就感。这本书不仅仅是一本技术手册，更像是一位循循善诱的良师益友，它点燃了我对算法世界的好奇心，也为我日后深入学习算法打下了坚实的基础。我发现，曾经觉得遥不可及的算法概念，在读完这本书后，仿佛也变得触手可及了。
在我浩瀚的书架中，《算法竞赛入门经典》无疑占据了一个特别的位置。它并非一本单纯的技术书籍，更多的是承载了我一段刻骨铭心的学习经历。犹记得那些无数个挑灯夜读的夜晚，我与书中的算法思想进行着一场场无声的搏斗。书中对于复杂度分析的详尽讲解，让我开始审视代码的效率，理解“时间就是金钱”在计算机科学中的真正含义。它教会了我如何权衡不同算法的优劣，如何在效率和易于实现之间找到最佳平衡点。书中的图论部分，尤其令我印象深刻。从最基础的图的表示方法，到各种遍历算法（DFS、BFS），再到最短路径（Dijkstra、Floyd-Warshall）和最小生成树（Prim、Kruskal），每一个算法的推导过程都如同抽丝剥茧，清晰无比。我曾为了理解Prim算法的贪心策略反复阅读，直到豁然开朗。书中提供的范例代码，不仅规范，而且易于理解，我常常将它们作为自己编写代码的模板，逐渐形成了良好的编码习惯。这本书的价值，远不止于知识的传授，它更是一种思维方式的塑造，一种解决问题能力的培养。它让我明白，算法的世界并非枯燥的数学公式堆砌，而是充满智慧与创造力的领域。
作为一名对编程充满热情的学生，《算法竞赛入门经典》是我踏入算法竞赛领域的第一块敲门砖。这本书的魅力在于它的“入门”二字，它没有将读者置于高深莫测的理论海洋，而是从最基本、最实用的算法概念出发，循序渐进地带领读者走进算法的世界。书中对递归和分治策略的阐释，让我领略到了“分而治之”的强大威力，例如快速排序和归并排序的实现，直观而又高效。我常常会动手去模拟这些算法的执行过程，加深对它们工作原理的理解。动态规划部分，虽然初看起来有些晦涩，但书中通过大量的经典例题，如背包问题、最长公共子序列等，逐渐揭示了其核心思想——状态转移。作者巧妙地将抽象的数学模型转化为具体的编程实现，让我从“看不懂”逐渐走向“会运用”。此外，书中关于字符串匹配（KMP算法）的讲解，也是我学习的重点。理解KMP算法的next数组构造过程，是攻克这一难关的关键，而书中对此的讲解非常到位。这本书不仅教会了我如何写出高效的算法，更教会了我如何去思考，如何去分析问题，如何去设计解决方案。它就像一把钥匙，为我打开了通往更广阔算法世界的大门。
《算法竞赛入门经典》在我学习算法的道路上，起到了不可替代的指引作用。它并非泛泛而谈，而是聚焦于算法竞赛中最常用、最核心的知识点，并将其讲解得透彻入微。书中的数据结构章节，特别是关于堆（优先队列）和哈希表的应用，让我对这些基本但强大的工具有了更深刻的认识。我曾经为了解决一个需要高效查找最小/最大元素的问题，反复思考如何运用堆，最终在书中找到了答案。书中关于二分查找的变种，以及在有序数组或其他数据结构中的应用，也极大地拓展了我的思路。让我意识到，即使是看似简单的二分查找，也有着丰富的应用场景和巧妙的实现技巧。此外，书中的一些高级主题，例如图的连通性（Tarjan算法）、二分图匹配等，虽然难度有所提升，但作者依然保持了清晰的讲解风格，并配以精心设计的题目，鼓励读者去挑战和探索。阅读这本书的过程，就像在攀登一座高峰，每克服一个难点，都能看到更开阔的风景。它培养了我独立思考和解决复杂问题的能力，也让我对算法竞赛产生了浓厚的兴趣，并渴望继续深入学习。
在我翻阅过的众多技术书籍中，《算法竞赛入门经典》以其独树一帜的风格，给我留下了深刻的印象。它没有华丽的辞藻，也没有过多的理论铺垫，而是直接切入算法的核心，以简洁明了的语言，配合大量精炼的代码示例，将复杂的算法原理娓娓道来。书中对回溯算法的讲解，让我理解了如何通过“试探”来寻找问题的解，例如N皇后问题和全排列的生成。作者通过对回溯过程的清晰描绘，以及对剪枝策略的探讨，让我掌握了设计回溯算法的基本框架。我尤其欣赏书中对常见算法的优化思路的讨论，比如如何改进朴素的最短路径算法，或者如何处理大规模图的遍历问题。这种对算法效率的极致追求，也深深影响了我的编程习惯。这本书不仅是一本学习算法的教科书，更是一本启发思考的工具书。它教会了我如何从题目中提炼出关键信息，如何将实际问题抽象成算法模型，以及如何利用已有的算法知识去解决它们。每一次阅读，都能从中获得新的启发和感悟，让我更加坚定地走在算法学习的道路上。
读完爽多了。
大白书，知识点分布有些乱，但是上面很多习题都很经典
当初准备算法比赛的时候看过，一共看过两遍。不过没有经过系统训练，进步很小！
多年以后我在北京清北学堂的宿舍床上捡到一本此书，随手翻了几页之后大惊失色：刘你好要是早两年出这本书的话我入门算法的时间肯定就没那么长了啊……
当初准备算法比赛的时候看过，一共看过两遍。不过没有经过系统训练，进步很小！
