内容简介
《算法竞赛黄金法则：提高算法和思考力的77项技巧》是算法竞赛**教程，由IOI三届金牌获得者倾力打造，系统讲解算法竞赛中的77个核心技巧和解题思路，旨在帮助读者提升算法设计能力与逻辑思维。
《算法竞赛黄金法则：提高算法和思考力的77项技巧》共分10章，内容包括算法与时间复杂度、前缀和、二分查找、动态规划、数学问题、思维技巧、启发式、数据结构和查询处理、图算法、综合问题。书后配有20道精选的综合测试题，可帮助读者检验和巩固所学知识。300余幅全彩插图，将抽象概念转化为视觉化表达，即使零基础读者也能轻松领悟精髓；153道例题与应用问题均为原创设计，剔除非核心要素，示例代码精简高效，特别适合通过“代码临摹”方式学习的读者。
精彩书摘
算法竞赛入门
序章
算法竞赛入门
序1什么是算法竞赛？
序2有哪些竞赛？
序3算法竞赛的核心竞争力是什么？
序4本书的使用方法
序1 什么是算法竞赛?
算法竞赛是一种在限定时间内运用算法和数据结构解决给定问题的比赛。通过参与此类竞赛，参赛者能够锻炼程序设计能力，提升算法思维及问题解决能力。
算法竞赛不仅是技术的较量，更是智慧与耐心的比拼。参赛者需要在短时间内快速构思并实现解决问题的策略，这要求参赛者具备良好的逻辑思维能力。同时，参赛者还需要对各种数据结构和算法有深人的理解和熟练的应用，这对于提升个人技术水平至关重要。
算法竞赛在日本虽仅有短短十五载的发展历程，却已迸发出蓬勃生机：目前日本参赛者已突破3万人u，从怀揣梦想的初高中生，到追求技术突破的职业开发者，不同背景、不同年龄的编程爱好者都能在这里找到属于自己的舞台。
值得注意的是，算法竞赛的价值已远超单纯的比赛范畴。如今，它正日益成为提升编程能力的有效训练方式，并在计算机教育领域发挥着重要作用。许多企业和教育机构都开始将算法竞赛纳人人才培养体系，足见其*特的实践价值。
竞赛流程
在算法竞赛中，赛事流程通常遵循下图所示的标准模式。值得关注的是，当前主流竞赛平台都采用了分级题目设置机制：除了面向高阶选手的挑战题外，每场赛事都会专门设置适合初学者的人门题型。因此，当您以本书为起点踏上算法竞赛之旅时，完全不必有“起步门槛”的顾虑一循序渐进的学习路径和科学分级的题目设置，将确保您获得*佳的学习体验。
序2 有哪些竞赛？
接下来，将介绍几种具有代表性的算法竞赛（信息截至2022年8月）
AtCoder
AtCoder是日本规模*大的算法竞赛平台，提供在线比赛、过往比赛提交、在线评测等服务。AtCode支持英语和日语两种语言，赛题难度从ABC到ARC再到AGC逐渐增大，其中ABC的题目比较简单，适合初学者。AtCoder比赛每周六21点（日本时间）在线举行，吸引全球超过5000名选手同时参与。竞赛免费开放，参赛者涵盖小学生至职场人士，无年龄或职业限制。
AtCoder*具特色的是其竞赛评分系统，如下图所示，该评分客观反映选手的编程实力，常被用于技术兼职或求职时的能力证明。其中，评分达到2800以上的**选手被称为“红色程序员”（Red Coder），是众多参赛者仰慕的目标。
日本信息学奥林匹克竞赛（JOI）
日本信息学奥林匹克竞赛是一项面向高中生的计算机科学竞赛，旨在培养学生的算法与编程能力。该赛事每年吸引约1500名选手参与，经过层层选拔后，*终脱颖而出的前4名选手将获得代表日本参加国际信息学奥林匹克竞赛（IOI）的资格。作者本人正是通过这项赛事开启了算法竞赛的旅程。值得一提的是，JOI不仅完全免费参赛，其初赛仅考察基础编程能力，因此即便是编程初学者也能轻松参与其中。
国际大学生程序设计竞赛（ICPC）
国际大学生程序设计竞赛由ICPC基金会（ICPC Foundation）主办，是一项面向大学生的国际性编程竞赛，旨在展示大学生创新能力、团队精神、在压力下运用计算机来分析和解决问题的能力。与AtCoder等个人赛不同，ICPC采用3人团队赛制，不仅考验算法能力，更注重团队协作与战术策略。参赛队伍须先通过日本国内预选赛，再晋级亚洲区域赛，*终**团队将获得全球总决赛的参赛资格。此外，赛事全程免费参与，为选手提供了高水平的竞技平台。
谷歌全球编程挑战赛（Google Code Jam）
谷歌全球编程挑战赛是由谷歌（Google）主办的一项年度国际编程竞赛（免费参与）。该赛事规模盛大，自2003年诞生以来，以其*特的魅力，迅速成为全球信息学爱好者的盛宴。每年吸引全球超过150个国家的近10万名选手报名参赛。预赛采用线上形式，选手需在2.5小时内完成3~4道编程题目。经过三轮预赛的激烈角逐，*终排名前25的选手将获得总决赛资格。值得一提的是，自2020年起总决赛改为线上形式举行。
算法实践测试（PAST）
这是日本*个专门评估算法设计与实现能力的标准化认证考试。该测试由知名算法竞赛平台AtCoder公司主办，考试费用为8800日元。通过考试并获得认证的考生将被认定为“具备算法能力的专业人才”，此举能显著提升持证者在就业市场中的竞争力。
序3 算法竞赛的核心竞争力是什么?
在算法竞赛中取得优异成绩需要哪些关键能力？笔者认为主要包含三大核心要素：编程能力、算法知识和思考力。
编程能力
算法竞赛*先考验的是将解题思路转化为实际代码的能力，这要求参赛者必须：
（1）熟练掌握至少一门编程语言的基础语法，包括标准输人输出、流程控制（条件分支与循环结构）等核心要素。
（2）具备高效的代码实现速度
目录
目录
算法竞赛入门
序 章
序1 什么是算法竞赛？ 2
序2 有哪些竞赛？ 3
序3 算法竞赛的核心竞争力是什么？ 5
序4 本书的使用方法 6
算法与时间复杂度
第1章
1.1 导入问题 17
1.2 枚举（1） 20
1.3 枚举（2） 23
1.4 二进制 26
1.5 挑战问题 30
总结 37
前缀和
第2章
2.1 一维前缀和（1） 42
2.2 一维前缀和（2） 46
2.3 二维前缀和（1） 50
2.4 二维前缀和（2） 56
2.5 挑战问题 61
总结 68
二分查找
第3章
3.1 数组的二分查找 72
3.2 根据答案进行二分查找 77
3.3 双指针法 81
3.4 折半枚举 85
3.5 挑战问题 90
总结 93
第4章 动态规划
4.1 动态规划的基础 98
4.2 动态规划的回溯 101
4.3 二维DP（1）：部分和问题 105
4.4 二维DP（2）：背包问题 109
4.5 二维DP（3）：*长公共子序列问题 114
4.6 二维DP（4）：区间DP 119
4.7 优化技巧 123
4.8 状态压缩DP 128
4.9 *长递增子序列问题 133
4.10 挑战问题 138
总结 141
第5章 数学问题
5.1 素数判定 145
5.2 *大公约数 150
5.3 取模运算（1）：基础 154
5.4 取模运算（2）：幂 158
5.5 取模运算（3）：除法 161
5.6 容斥原理 164
5.7 游戏（1）：必胜法 168
5.8 游戏（2）：Nim理论 172
5.9 游戏（3）：Grundy数 177
5.10 挑战问题 181
总结 184
第6章 思维技巧
6.1 思考奇偶性 189
6.2 计数贡献法 192
6.3 思考上限值 196
6.4 思考下一步 199
6.5 思考个数 205
6.6 逆向思维 209
6.7 固定并枚举 213
6.8 重新表述问题 217
6.9 改进保存数据的方式 220
6.10 关注不变量 224
总结 227
第7章 启发式
7.1 贪心算法 231
7.2 局部搜索算法 235
7.3 模拟退火算法 240
7.4 集束搜索 243
7.5 挑战问题 251
总结 265
第8章 数据结构和查询处理
8.1 栈 270
8.2 队 列 274
8.3 优先队列 278
8.4 关联数组 282
8.5 集合管理（仅限C++） 286
8.6 哈希字符串 290
8.7 倍增法 295
8.8 线段树：RMQ 299
8.9 线段树：RSQ 308
8.10 挑战问题 312
总结 317
第9章 图算法
9.1 图的实现方法 326
9.2 深度优先搜索 329
9.3 广度优先搜索 333
9.4 Dijkstra算法 338
9.5 树的动态规划 346
9.6 Union-Find树 350
9.7 *小生成树问题 358
9.8 *大流问题 362
9.9 二分图匹配问题 372
9.10 挑战问题 376
总结 383
第10章 综合问题
10.1 综合问题（1） 388
10.2 综合问题（2） 392
10.3 综合问题（3） 396
10.4 综合问题（4） 400
10.5 综合问题（5） 404
10.6 综合问题（6） 408
10.7 综合问题（7） 412
本书总结 417
能力测试题 419
终章 能力提升之道
终1 积极参加各种比赛 426
终2 刷真题 427
终3 准备库 428
终4 “算法竞赛**90问”挑战指南 429
终5 从挫折到金牌的成长之路 430
参考文献 433
试读
算法竞赛入门
序章
算法竞赛入门
序1什么是算法竞赛？
序2有哪些竞赛？
序3算法竞赛的核心竞争力是什么？
序4本书的使用方法
序1 什么是算法竞赛?
算法竞赛是一种在限定时间内运用算法和数据结构解决给定问题的比赛。通过参与此类竞赛，参赛者能够锻炼程序设计能力，提升算法思维及问题解决能力。
算法竞赛不仅是技术的较量，更是智慧与耐心的比拼。参赛者需要在短时间内快速构思并实现解决问题的策略，这要求参赛者具备良好的逻辑思维能力。同时，参赛者还需要对各种数据结构和算法有深人的理解和熟练的应用，这对于提升个人技术水平至关重要。
算法竞赛在日本虽仅有短短十五载的发展历程，却已迸发出蓬勃生机：目前日本参赛者已突破3万人u，从怀揣梦想的初高中生，到追求技术突破的职业开发者，不同背景、不同年龄的编程爱好者都能在这里找到属于自己的舞台。
值得注意的是，算法竞赛的价值已远超单纯的比赛范畴。如今，它正日益成为提升编程能力的有效训练方式，并在计算机教育领域发挥着重要作用。许多企业和教育机构都开始将算法竞赛纳人人才培养体系，足见其*特的实践价值。
竞赛流程
在算法竞赛中，赛事流程通常遵循下图所示的标准模式。值得关注的是，当前主流竞赛平台都采用了分级题目设置机制：除了面向高阶选手的挑战题外，每场赛事都会专门设置适合初学者的人门题型。因此，当您以本书为起点踏上算法竞赛之旅时，完全不必有“起步门槛”的顾虑一循序渐进的学习路径和科学分级的题目设置，将确保您获得*佳的学习体验。
序2 有哪些竞赛？
接下来，将介绍几种具有代表性的算法竞赛（信息截至2022年8月）
AtCoder
AtCoder是日本规模*大的算法竞赛平台，提供在线比赛、过往比赛提交、在线评测等服务。AtCode支持英语和日语两种语言，赛题难度从ABC到ARC再到AGC逐渐增大，其中ABC的题目比较简单，适合初学者。AtCoder比赛每周六21点（日本时间）在线举行，吸引全球超过5000名选手同时参与。竞赛免费开放，参赛者涵盖小学生至职场人士，无年龄或职业限制。
AtCoder*具特色的是其竞赛评分系统，如下图所示，该评分客观反映选手的编程实力，常被用于技术兼职或求职时的能力证明。其中，评分达到2800以上的**选手被称为“红色程序员”（Red Coder），是众多参赛者仰慕的目标。
日本信息学奥林匹克竞赛（JOI）
日本信息学奥林匹克竞赛是一项面向高中生的计算机科学竞赛，旨在培养学生的算法与编程能力。该赛事每年吸引约1500名选手参与，经过层层选拔后，*终脱颖而出的前4名选手将获得代表日本参加国际信息学奥林匹克竞赛（IOI）的资格。作者本人正是通过这项赛事开启了算法竞赛的旅程。值得一提的是，JOI不仅完全免费参赛，其初赛仅考察基础编程能力，因此即便是编程初学者也能轻松参与其中。
国际大学生程序设计竞赛（ICPC）
国际大学生程序设计竞赛由ICPC基金会（ICPC Foundation）主办，是一项面向大学生的国际性编程竞赛，旨在展示大学生创新能力、团队精神、在压力下运用计算机来分析和解决问题的能力。与AtCoder等个人赛不同，ICPC采用3人团队赛制，不仅考验算法能力，更注重团队协作与战术策略。参赛队伍须先通过日本国内预选赛，再晋级亚洲区域赛，*终**团队将获得全球总决赛的参赛资格。此外，赛事全程免费参与，为选手提供了高水平的竞技平台。
谷歌全球编程挑战赛（Google Code Jam）
谷歌全球编程挑战赛是由谷歌（Google）主办的一项年度国际编程竞赛（免费参与）。该赛事规模盛大，自2003年诞生以来，以其*特的魅力，迅速成为全球信息学爱好者的盛宴。每年吸引全球超过150个国家的近10万名选手报名参赛。预赛采用线上形式，选手需在2.5小时内完成3~4道编程题目。经过三轮预赛的激烈角逐，*终排名前25的选手将获得总决赛资格。值得一提的是，自2020年起总决赛改为线上形式举行。
算法实践测试（PAST）
这是日本*个专门评估算法设计与实现能力的标准化认证考试。该测试由知名算法竞赛平台AtCoder公司主办，考试费用为8800日元。通过考试并获得认证的考生将被认定为“具备算法能力的专业人才”，此举能显著提升持证者在就业市场中的竞争力。
序3 算法竞赛的核心竞争力是什么?
在算法竞赛中取得优异成绩需要哪些关键能力？笔者认为主要包含三大核心要素：编程能力、算法知识和思考力。
编程能力
算法竞赛*先考验的是将解题思路转化为实际代码的能力，这要求参赛者必须：
（1）熟练掌握至少一门编程语言的基础语法，包括标准输人输出、流程控制（条件分支与循环结构）等核心要素。
（2）具备高效的代码实现速度
