2022-08-30

《算法竞赛》学习指北

没什么，就是单纯因为书多感到迷茫所以写写。

本文将向你介绍《算法竞赛》系列丛书的所含内容及个人学习安排。

丛书内容

算法竞赛入门经典/刘汝佳编著 —2版. —北京：清华大学出版社，2014

《算法竞赛入门经典（第2版）》，是系列中的核心算法理论书，系统地讲解 C/C++ 语言基础知识，数据结构知识，以及信息学奥赛和 ACM/ICPC 中的常考必考算法知识点、技巧和剖析。

第 1 部分是语言篇（第 1～4 章），纯粹介绍语言，几乎不设计算法，但逐步引入一些工程性的东西，如测试、断言、伪代码和迭代开发等。
第 2 部分是算法篇（第 5～8 章），在介绍算法等同时继续强化语言，补充了第 1 部分没有涉及的语言特性，如位运算、动态内存管理等，并延续第一部分的风格，在需要时引入更多的思想和技巧。
第 3 部分是竞赛篇（第 9～11 章），设计竞赛中常用的其他知识点和技巧。和前两部分相比，第 3 部分涉及的内容更加广泛，其中还包括一些难以理解的 “学术内容”，但其实这些才是算法的精髓。

算法竞赛入门经典. 训练指南 / 刘汝佳，陈峰编著. —北京：清华大学出版社，2021.5

《算法竞赛入门经典——训练指南》，是《入门经典》的姊妹篇，主要针对更多的算法竞赛题型进行横向拓展，以及更广范围内的讲解和训练，“覆盖面广，点到为止，注重代码” 是此书的最大特点。

此书不是一本算法竞赛入门类图书，因此并不从程序设计语言、算法的概念、基础数据结构、渐进复杂度分析这些内容讲起。如果你是一个新手，建议先阅读紫书（和此书搭配着阅读也可以）。

此书是完全的题目导向，掌握了书中的所有例题，也就掌握了书中的主要知识点和方法、技巧。在习题中也有少量相对不那么重要、例题没有涉及的东西，在每章的小结部分会明确指出。换句话说，对于每个知识点，最好的方法是结合例题分析和代码去理解，上机实践，最终达到能独立解决同类问题的目的。

算法竞赛入门经典——习题与解答/陈峰编著. —北京：清华大学出版社，2018

《算法竞赛入门经典——习题与解答》，是《入门经典》的配套习题详解，讲其中的所属练习题，尤其是限于篇幅无法展开的练习题，进行了细致的解析，使其更简单、易学，快速提升读者的算法思维能力。更适合初学者配合着《入门经典》一起学习。

算法竞赛入门经典. 算法实现 / 陈峰编著. —北京：清华大学出版社，2021.5

《算法竞赛入门经典——算法实现》，是一本高效备考工具书，择选近些年来信息学奥赛中最新、最经典的比赛真题，给出优化过的各类代码实现模版，通过它可以快速备考各类竞赛。

此书不介绍具体的算法理论知识，而是精选紫书和蓝书中的经典题目，按算法要点和竞赛考点重新进行分拆和归类，并提供 240 余套简洁、高效、规范、完整、的实现代码模版。此外，也加入了一些虽然未在两本书中出现，但实际上对初学者入门非常重要的题目代码。

第 1 章介绍 C++ 编程基础与 STL 中的常用算法实现，共计 15 道真题的算法实现。
第 2 章介绍算法设计与优化，包含算法优化策略、贪心算法、搜索算法、动态规划算法等内容，共计 56 道真题的算法实现。
第 3 章介绍数学相关算法，包含数论、组合计数、概率与期望、组和游戏、置换、矩阵和现行方程组、快速傅立叶变换（FFT）、数值方法、数学专题等内容，共计 46 道真题的算法实现。
第 4 章介绍数据结构相关算法，包含基础数据结构、区间信息维护、排序二叉树、树的经典问题与方法、动态树与 LCT、离线算法、kd-tree、可持久化数据结构、嵌套和分块数据结构等内容，共计 52 道真题的算法实现。
第 5 章介绍字符串相关算法，包含 Trie 与 KMP 以及 AC 自动机、后缀数组、后缀自动机等内容，共计 13 道真题的算法实现。
第 6 章介绍计算几何相关算法，包含二维几何基础、圆有关的计算问题、二维几何常用算法、三维几何基础、几何专题算法等内容，共计 21 道真题的算法实现。
第 7 章介绍图论相关算法，共包含深度优先遍历、最短路问题、生成树相关问题、二分图匹配、网络流问题，共计 36 道真题的算法实现。