← #813

《竞赛程序员手册》（2018）[PDF]

查看原文 HN 讨论

文章摘要

这次的链接是一本完整的书：芬兰赫尔辛基大学 Antti Laaksonen 撰写的《Competitive Programmer’s Handbook》（竞赛程序员手册）。它免费托管在 CSES 网站上，PDF 共 296 页，封面标注为 2018 年 7 月 3 日的草稿版。这本书在 HN 上已经被反复提交过多次，本文不翻译书中内容，只概述它的定位、结构和特点。

定位。 作者在前言中说，这本书旨在全面介绍算法竞赛，读者需要已经掌握编程基础，但不需要任何竞赛背景。它主要面向想学习算法、参加国际信息学奥林匹克（IOI）或国际大学生程序设计竞赛（ICPC）的学生，当然对竞赛编程感兴趣的人都适合读。作者坦言，成为优秀的竞赛选手需要很长时间，但这也是大量学习的机会——只要花时间读书、做题、参赛，就一定能对算法建立起扎实的整体理解。

全书结构。 全书 30 章，分为三大部分：

1. 基础技术（第 1–10 章）：从竞赛入门讲起，包括语言选择、输入输出、数值处理、精简代码的技巧、常用数学知识以及比赛和学习资源；接着是时间复杂度、排序与二分查找、C++ 标准库数据结构（动态数组、set、map、迭代器等）、完全搜索（子集和排列生成、回溯、剪枝、折半搜索）、贪心算法、动态规划（硬币问题、最长上升子序列、背包、编辑距离、铺砖计数）、均摊分析（双指针、单调栈、滑动窗口最小值）、区间查询（前缀和、树状数组、线段树）以及位运算技巧。
2. 图算法（第 11–20 章）：图的基本概念与表示、DFS/BFS 遍历、最短路（Bellman–Ford、Dijkstra、Floyd–Warshall）、树上算法（直径、二叉树）、生成树（Kruskal、并查集、Prim）、有向图（拓扑排序、后继路径、判环）、强连通分量（Kosaraju 算法与 2-SAT）、树上查询（祖先、子树与路径、最近公共祖先、离线算法）、欧拉路径与哈密顿路径（包括 De Bruijn 序列和骑士巡游），以及网络流与割（Ford–Fulkerson、最大匹配、路径覆盖）。
3. 进阶主题（第 21–30 章）：数论（素数、模运算、解方程）、组合数学（二项式系数、卡特兰数、容斥原理、Burnside 引理、Cayley 公式）、矩阵（线性递推的矩阵快速幂）、概率（期望、马尔可夫链、随机化算法）、博弈论（Nim 游戏、Sprague–Grundy 定理）、字符串算法（Trie、字符串哈希、Z 算法）、平方根分解（包括莫队算法）、线段树进阶（懒标记、动态开点、二维）、计算几何（用复数表示点、多边形面积、距离函数），以及扫描线算法（求交点、最近点对、凸包）。

写法与特点。

• 紧扣竞赛实战。 第一章就把竞赛编程概括为「算法设计」与「算法实现」两件事，并指出它与传统软件工程的区别：程序短小，通常不超过几百行，比赛结束后无需维护，所以代码风格追求直接、简洁、写得快。书里专门有一节教你用 typedef、宏来缩短代码，比如把 long long 简写成 ll。这一点后来也成为 HN 评论中的争议焦点。
• 以 C++ 为主。 书中引用 2017 年 Google Code Jam 前 3000 名的数据：79% 用 C++，16% 用 Python，8% 用 Java。作者因此以 C++ 及其标准库为主要示范语言，但也建议掌握多门语言，比如需要大整数时 Python 更方便。
• 重视复杂度估算。 书中给出了一张实用的经验表：在 1 秒时限下，根据输入规模 n 反推所需的复杂度，比如 n ≤ 10 可以接受 O(n!)，n ≤ 20 可以接受 O(2ⁿ)，n ≤ 5000 大约需要 O(n²)，n 达到 10⁶ 则需要 O(n log n) 或 O(n)。同时也提醒读者，复杂度隐藏了常数因子。
• 概念清楚、篇幅克制。 每个主题通常从一个具体问题出发，配图讲解思路，再给出简短的参考实现，不追求百科全书式的完整。作者称书中几乎覆盖了 IOI 大纲的全部主题。第一章末尾还介绍了 IOI、ICPC、Codeforces、AtCoder 等赛事和平台，并推荐了《挑战编程》、Halim 兄弟的《Competitive Programming 3》以及《算法导论》等延伸读物。
• 配套题库。 CSES 网站上有与本书配套的题集，HN 评论中也有人指出这一点。此外，这本书后来经过修订，由 Springer 正式出版为《Guide to Competitive Programming》。

总体来看，这是一本免费、紧凑、体系完整的算法竞赛入门到进阶教材，也常被当作算法速查手册和面试准备材料。

HN 评论精华

帖子获得约 320 分、85 条评论。dang 列出了此前的多次讨论（2017、2018 年各有百余条评论的帖子）。值得一提的是，评论区一开始就被一条关于「职业把关」的争议性评论带偏，后面相当一部分讨论围绕 LLM 时代刷题还有没有意义、竞赛编程与面试的关系展开，真正讨论书本身的内容不算多。

开局争议：要不要「把关」这个行业

• 置顶的 dominotw 说，他希望 LeetCode 面试继续存在，并表示自己的立场来了个 180 度大转弯：后悔为开源做贡献，现在主张闭源、文凭主义和严格把关。JSR_FDED 给出善意解读：编程岗位应该留给真正愿意深入理解的人，而不是只会敲提示词的人；hex4def6 给出不那么善意的解读：开源被拿去训练了取代自己的模型，于是想把编程变成行会式职业。dominotw 反驳说，其他职业都在把关，却没人反感。shahbaby 感叹，没有哪个行业像软件业这样急于让自己被淘汰。

关于这本书

• Keegs 是这本书的忠实粉丝，认为它既是很好的算法参考书，也适合准备面试。BeetleB 则说读它准备面试其实没太大帮助，真正有用的是大量练习；读过《Cracking the Coding Interview》、上过本科算法课，应付 LeetCode 类题目就足够了，不过他依然推荐这本书，「写得很好」。他还提到续作《Beyond Cracking the Coding Interview》里的技巧比原书好得多。
• xendo 觉得这本书偏难，为了巧妙和简洁牺牲了一些可读性，他更推荐 Zingaro 的《Algorithmic Thinking》。gwbas1c 回应说，只要缩写习惯始终一致就不难读，毕竟这些都是一次性程序。当过几届 ICPC 裁判的 yuye 证实，书中这种代码风格在高水平竞赛队伍里极其常见。
• ExciteByte 指出这本书有更完善的 Springer 出版版本，以及配套的 CSES 题库。delis-thumbs-7e 说 Antti 是他的老师，课程很难、深入到计算机科学最基础的部分，但每次上完都觉得理解提升了十倍，并提到作者在 Springer 出了新书。HEX4AGON 说自己是电子工程专业，大二时靠这本书补齐算法、通过软件面试拿到实习，并一并推荐了 OSTEP 和 Harris & Harris 的《数字设计和计算机体系结构》。ricardobayes、oleggromov 认为即使不打比赛，它也是一本实用的算法入门书。

LLM 时代还要刷题吗

• lifeisloving 说自己业余做 Codeforces、Rosalind、Codewars 和 LeetCode，用来给高强度使用 AI 代理的日常「排毒」，找回了冥思苦想后解出题目的感觉，希望人类不要失去这种渴望。yuye 则认为 LLM 的兴起恰恰证明，大多数人并不在乎这些，只有少数人一直有这种渴望。由此引出一段长讨论：locknitpicker 把它类比为人们不再关心编译器生成的机器码，ebiederm 反驳说仍有人会经常检查生成的机器码。
• sashank_1509 认为，过去练竞赛多少能让你成为更好的程序员，但如果我们已经到了「还读不读代码」的阶段，它就只剩下兴趣爱好的意义。tudorconstantin 说最近的面试几乎都有现场编码，甚至面后端岗也会出 hard 级别的 LeetCode 题，所以他每周专门留几个小时练算法。0xpgm 提醒，人们低估了 LLM 出现之前的手写代码经验对驾驭 LLM 有多大帮助；jmfldn 把刷题看作「思维健身房」。

竞赛编程与面试文化

• 0x20cowboy 措辞尖锐，称竞赛编程是个「愚蠢的概念」，并认为它催生了 LeetCode 式面试，「毁了这个行业」。Shorel、anta40、sparkilyshpark 认为它只是一种智力游戏和兴趣爱好，与日常工作无关。TrackerFF 的看法比较中肯：竞技本身没有问题，问题在于有人把这项「运动」当成相关领域的筛选标准，并赋予过高的权重。menaerus 则认为 LeetCode 文化天然偏向没有家庭负担、可以全身心投入的年轻人。