算法竞赛入门经典pdf完整第二版|百度网盘下载

编辑评论：

如果你是程序员，如果你参加过NOIP、NOI、ACM/ICPC比赛，只要你对算法感兴趣，那就来吧！这本经典的算法竞赛书，深受大多数程序员的喜爱，被很多学校广泛用作教材！

简介

本书是算法竞赛的入门和改进教材。将C/C语言、算法和问题解决有机结合，淡化理论，注重学习方法和实践技能。本书内容分为12章，包括编程概论、循环结构编程、数组和字符串、函数和递归、C和STL概论、数据结构基础、蛮力求解、高效算法设计、初步动态程序设计、数学概念与方法、图论模型与算法、进阶专题等，涵盖了算法竞赛入门和提高所需的主要知识点，并包含大量实例和练习。书中代码规范、简洁、通俗易懂，不仅可以帮助读者理解算法原理，还可以教会读者很多实用的编程技巧；书中包含的各种开发、测试和调试技巧，在传统语言和算法书籍中也有。很难看到。

本书可作为全国青少年信息学奥林匹克（NOIP）复赛的教材，全国青少年信息学奥林匹克（NOI）和ACM国际大学生程序设计大赛（ACM/ICPC）的培训教材。研究人员参考书。

关于作者

刘汝佳，1982年12月出生，重庆外国语学校高中毕业。 2000年3月，获得NOI2000全国青年信息学奥林匹克竞赛一等奖第四名，进入国家集训队。因此，他被派往清华大学计算机科学与技术系。大一时获得2001年ACM/ICPC国际大学生程序设计大赛亚洲-上海赛区冠军和2002年世界总决赛银牌（世界第4）。 2005年获学士学位，2008年获硕士学位。

在校期间，他是中国计算机学会NOI科学委员会学生委员，曾担任IOI2002-2008中国国家队教练，为NOI系列比赛提出十余项命题。现任NOI竞赛委员会委员，荣获中国计算机学会NOI 25周年“特别贡献奖”。

自2004年以来，他为ACM/ICPC亚洲赛区提交了20多项命题，担任过6名裁判员和2名命题主任，并应邀参加IOI和ACM/ICPC相关国际研讨会并发表论文两篇。

2004年初以第一作者出版专着《算法艺术与信息学竞赛》，2009年出版翻译著作《编程挑战》，2009年出版《算法竞赛导论》，出版《算法导论》比赛”在 2012 年。培训指南。

多年来在全国20多个城市为中学生进行竞赛训练，在北京、上海、吉隆坡等地著名大学任教传教，并与知名企业合作比如TopCoder、百度、网易有道等多次。 ，让更多的IT人才获得展示自我的平台。

前言

第二版前言

《算法竞赛经典》第一版出版至今已有四年。过去四年发生了许多变化。比如NOI系列比赛终于“解禁”了STL，比如引入了C11和C 11标准，g编译器升级（直接导致了本书第一版和>?运算符的正式使用）未编译通过），如《经典算法竞赛入门-训练指南》的出版，弥补了本书第一版的诸多不足，ACM/ICPC的蓬勃发展，让更多的大学生能够了解并参与算法竞赛... ...

看来是时候“升级”这本书了。

重大变化

我本来打算只加一章专门讲C和STL的，改写部分代码符合新的语言规范，顺便加一些例子和练习。翻了一番。第一版写的时候，220页的篇幅是和一线中学教师协商决定的，因为书太厚了，对初学者来说会很吓人。不过这几年读者的反馈让我意识到，由于篇幅所限，读者不满意的东西太多了，不如多写一些。虽然《算法竞赛入门-训练指南》后来出版了，但那本书的主要目的是补充知识点，即扩大知识的广度，我更喜欢在知识的广度上增加深度。几乎不变——我眼中的竞争应该主要是与思维和实践能力相比，而不是主要与知识相比。

简单来说，我继续扩大篇幅，用大量的例子（包括标题和代码）来表达我想传达给读者的信息。一位试读的朋友在收到第一个手稿片段时惊呼：“标题质量比第一版提高了很多！”这是我这次修改的主要目的。

具体来说，本次修订包括以下更改：

q 通过前 4 章中的一些更实用的语言技能取得进步，直接使用竞赛问题作为示例。

q 全新的第 5 章，涵盖竞赛中最常用的 C 语法，包括 STL 算法和容器。

q 第6～7章作为基础篇，增加代码和技巧的比例，适当增加例题。

q 第8-11章，作为中篇文章，添加各种例子，重点训练思维能力。

q全新的第12章为进阶篇，在《经典算法大赛入门-训练指南》的基础上补充少量知识点和大量精彩示例。

特别说明是第12章出现的原因。本章内容难度较大，要求读者掌握《算法竞赛经典入门-训练指南》的主要内容，这似乎与“入门”二字相矛盾。事实上，这本书虽然叫《经典概论》，但它不仅适合入门读者。根据近几年读者的反馈，也有相当多有经验的玩家购买了这本书。原因是：很多有经验的玩家都是“自学成才”的，总觉得自己可能漏掉了一些基础知识。同理：本书中提到的许多编码和分析技术在传统教科书中是看不到的，对很多有经验的玩家来说都是“新的”，而且可以比初学者更快更好。将这些知识应用到游戏中。本书的第 12 章是为这些读者准备的。如果这个解释不够直观，可以把第 12 章当作通关后的额外困难模式！

阅读说明

由于内容变化很大，所以阅读方式也需要再次说明。首先，与本书的第一版一样，最好有老师、教练或学长等人陪同学习。随着互联网的发展，这个条件越来越容易满足——即使没有指导，也可以在别人的博客上留言，或者在贴吧寻求帮助。

一定要注意书中的“提示”。书中有很多“提示”，是非常重要的知识点或技能。有些提示看似普通，但如果不注意，在场上丢分，你会后悔的。

接下来是关于添加第 5 章。让我首先说明这一章不是 C 的速成课程——不可能使 C 速成。本章并不是说你从头到尾阅读它然后掌握了 C，但它提供了一个大纲，概述了算法比赛中最常用的东西，以及应该如何使用它们。你可以找另外一本书（或者看网上的文章）学习C，然后读这本书的第5章（目的是摆脱你头脑中那些头晕目眩、没那么有用的知识），也可以直接阅读这本书的第5章，每次遇到不懂的或者觉得不够详细的时候，就去找其他的参考书学习吧。顺便说一句，即使您已经非常熟悉 C，看看第 5 章（尤其是代码！）也是一个好主意。这不会花费太多时间，但它可能会学到一些有用的东西。

忍不住说点题外话。有时学习算法的最佳方法不是编写程序，而是手工完成。 “手算”这个词听上去有点无聊，改成“玩游戏”怎么样？比如《雷顿教授与不可思议的小镇》就是一个不错的选择——它包括过河问题（谜题7、93）、寻找权重（谜题6、131）、一笔画（谜题30、39）、Queen n （谜题80~83、130）、倒水题（谜题23、24、78）、魔方（谜题95）、华融路（谜题97、132、135）等诸多经典题。

谢谢

算法竞赛经典pdf预览介绍

目录

第 1 部分语言

第 1 章编程简介...

1.1 算术表达式

1.2 变量及其输入

1.3 顺序结构编程

1.4 分支结构编程

1.5 笔记和练习

1.5.1 C、C99、C11 等

1.5.2 数据类型和输入格式

1.5.3 练习

1.5.4 总结

第 2 章循环结构编程...

2.1 for 循环

2.2 while循环和do-while循环

2.3 循环的代价

2.4 算法竞赛中的输入输出框架

2.5 笔记和练习

2.5.1 练习

2.5.2 总结

第 3 章数组和字符串...

3.1 数组

3.2 字符数组

3.3 竞赛选题讲座

3.4 笔记和练习

3.4.1 基系统和整数表示

3.4.2 思考题

3.4.3 黑盒测试和在线评估系统

3.4.4 示例问题和练习列表

3.4.5 总结

第 4 章函数和递归...

4.1 自定义函数和结构

4.2 函数调用和参数传递

4.2.1 表单参与参数

4.2.2 调用栈

4.2.3 使用指针作为参数

4.2.4 初学者常犯的错误

4.2.5 数组作为参数和返回值

4.2.6 使用函数作为函数参数

4.3 递归

4.3.1 递归定义

4.3.2 递归函数

4.3.3 C 语言对递归的支持

4.3.4 分段错误和堆栈溢出

4.4 竞赛题目选讲

4.5 笔记和练习

4.5.1 头文件、副作用等

4.5.2 示例问题和练习列表

4.5.3 总结

第 5 章 C 和 STL 简介...

5.1 从 C 到 C

5.1.1 C 框架

5.1.2 参考文献

5.1.3 字符串

5.1.4 再来说说结构

5.1.5 模板

5.2 初步 STL

5.2.1 排序和检索

5.2.2 不定长数组：向量

5.2.3 集合：集合

5.2.4 映射：地图

5.2.5 堆栈、队列和优先级队列

5.2.6 测试 STL

5.3 应用：大整数类

5.3.1 大整数

5.3.2 四种算术运算

5.3.3 比较运算符

5.4 竞赛题目示例

5.5 练习

第 2 部分基础知识

第 6 章数据结构基础...

6.1 再谈栈和队列

6.2 链表

6.3 树和二叉树

6.3.1 二叉树的编号

6.3.2 二叉树的层次遍历

6.3.3 二叉树的递归遍历

6.3.4 非二叉树

6.4 图

6.4.1 使用 DFS 查找连接块

6.4.2 使用BFS寻找最短路径

6.4.3 拓扑排序

6.4.4 欧拉电路

6.5 竞赛题目选讲

6.6 训练参考

第7章蛮力解法……

7.1 简单枚举

7.2 枚举排列

7.2.1 生成1~n的排列

7.2.2 生成可重新设置的排列

7.2.3 解决方案树

7.2.4 下一步安排

7.3 子集生成

7.3.1 增量构造

7.3.2 位向量法

7.3.3 二元法

7.4 回溯

7.4.1 八皇后问题

7.4.2 其他应用示例

7.5 寻路问题

7.6 迭代深化搜索

7.7 竞赛题目选讲

7.8 训练参考

第三部分比赛

第 8 章高效算法设计...

8.1 初步算法分析

8.1.1 渐近时间复杂度

8.1.2 上限分析

8.1.3 分而治之

8.1.4 正确对待算法分析结果

8.2 再谈排序和检索

8.2.1 合并排序

8.2.2 快速排序

8.2.3 二分查找

8.3 递归与分治

8.4 贪婪法则

8.4.1 背包相关问题

8.4.2 区间相关问题

8.4.3 霍夫曼编码

8.5 算法设计与优化策略

8.6 竞赛题目选讲

8.7 训练参考

第 9 章动态规划预备...

9.1 数字三角

9.1.1 问题描述和状态定义

9.1.2 记忆搜索和递归

9.2 DAG 上的动态规划

9.2.1 DAG 模型

9.2.2 最长路径及其字典顺序

9.2.3 具有固定端点的最长和最短路径

9.2.4 总结及应用实例

9.3 多阶段决策问题

9.3.1 多段图的最短路径

9.3.2 0-1 背包问题

9.4 更多经典机型

9.4.1 线性结构的动态规划

9.4.2 树上的动态规划

9.4.3 复杂状态的动态规划

9.5 竞赛题目选讲

9.6 训练参考

第 10 章数学概念和方法...

10.1 初步数论

10.1.1 欧几里得算法和唯一分解定理

10.1.2 埃拉托色尼筛

10.1.3 扩展欧几里得算法

10.1.4 同余和模运算

10.1.5 应用示例

10.2 计数和概率基础

10.2.1 杨辉三角形与二项式定理

10.2.2 数论中的计数问题

10.2.3 编码和解码

10.2.4 初步离散概率

10.3 数学中的其他主题

10.3.1 递归

10.3.2 数学期望

10.3.3 连续概率

10.4 竞赛题目选讲

10.5 训练参考

第 11 章图论模型和算法...

11.1 我们再来谈谈树

11.1.1 无根树到有根树

11.1.2 表达式树

11.2 最小生成树

11.2.1 克鲁斯卡尔算法

11.2.2 竞赛题目的选择

11.3 最短路径问题

11.3.1 Dijkstra 算法

11.3.2 贝尔曼-福特算法

11.3.3 弗洛伊德算法

11.3.4 竞赛题目选讲

11.4 初步网络流程

11.4.1 最大流量问题

11.4.2 增广路径算法

11.4.3 最小割最大流量定理

11.4.4 最小成本和最大流量问题

11.4.5 应用示例

11.5 竞赛题目选讲

11.6 训练参考

11.7 总结与展望

第 12 章高级主题...

12.1 知识讲座精选

12.1.1 自动机

12.1.2 树的经典问题和方法

12.1.3 持久数据结构

12.1.4 多边形的布尔运算

12.2 问题选择

12.2.1 数据结构

12.2.2 网络流

12.2.3 数学

12.2.4 几何

12.2.5 不完美算法

12.2.6 杂项专题讲座

12.3 总结与练习

附录 A 开发环境和方法...

A.1 命令行

A.1.1 文件系统

A.1.2 流程

A.1.3 程序执行

A.1.4 重定向和管道

A.1.5 常用命令

A.2 操作系统脚本编程简介

A.2.1 Windows下的批处理

A.2.2 Linux 下的 Bash 脚本

A.2.3 再来说说随机数

A.3 编译器和调试器

A.3.1 gcc安装与测试

A.3.2 常用编译选项

A.3.3 gdb简介

A.3.4 gdb 的高级特性

A.4 谈 IDE

主要参考书目

在线试读

第 9 章动态规划预备课

学习目标

理解状态和状态转移方程

了解最优子结构和重叠子问题

熟练使用递归和记忆搜索来解决数字三角形问题

熟悉DAG上动态规划的常用思路，两种状态定义方法和刷表法

掌握memoized search的实现注意事项

掌握记忆化搜索和递归中输出方案的方法

掌握递归中滚动数组的使用

精通解决经典动态规划问题

动态规划既有理论又有实践。一方面，要理解“状态”、“状态转移”、“最优子结构”、“重叠子问题”等概念。灵活设计算法的条件。可以说，动态规划的掌握在很大程度上可以直接影响一个玩家的分析和建模能力。

9.1 数字三角

动态规划是一种非常通用的问题解决方法。它不是一个特定的算法本身，而是一种思想和一种方法。下面通过一个主题来描述动态规划的基本思想和特点。

9.1.1 问题描述和状态定义

数字三角问题。有一个由非负整数组成的三角形，第一行只有一个数，除最下面一行外，每个数的左下角一个数，右下角一个数，如图 9-1 所示。

(a) 数字三角形 (b) 格数

图 9-1 数字三角问题

从第一行的数字开始，你可以一次到左下或右下一个空格，直到你到达最下面一行，然后将一路上传递的所有数字相加。我怎样才能使这个和尽可能大？

【分析】

如果您熟悉回溯，您可能会立即发现这是一个动态决策问题：一次有两个选择 - 左下角或右下角。如果采用回溯法寻找所有可能的路线，则可以从中选出最优路线。但是像往常一样，回溯法效率太低：一个n级数字三角形有2n-1条完整的路线，当n很大时，回溯法的速度快得让人难以忍受。

为了得到一个高效的算法，你需要以抽象的方式来思考这个问题：将当前位置（i，j）视为一个状态（还记得吗？），然后定义指标函数 d(i, j)是从格(i,j)开始时可以得到的最大和（包括格(i,j)本身的值）。在这个状态定义下，原始问题的解是 d(1, 1)。

让我们看看不同状态之间的转换是如何完成的。从格子 (i, j) 开始，有两个决定。如果向左走，走到(i 1, j)后需要问“从(i 1, j)出发后能得到的最大和”的问题，即d(i 1, j) .同理，d(i 1, j 1) 需要右转后求解。由于这两个决策之间可以自由选择，因此应选择 d(i 1,j) 和 d(i 1,j 1) 中的较大者。也就是说，得到了所谓的状态转移方程：

如果你向左走，那么最好的情况是等于 (i, j) 网格中的值 a(i, j) 与“从 (i 1, j) 开始的最大和”之和，你这里要注意“最大”这个词。如果“从(i 1, j)开始到底部”之和不是最大的，那么加上a(i, j)后肯定不是最大的。这种性质称为最优子结构，也可以描述为“全局最优解包含局部最优解”。无论如何，状态和状态转移方程一起充分描述了具体算法。

提示 9-1：动态规划的核心是状态和状态转移方程。

9.1.2 记忆搜索和递归

有了状态转移方程后，我们应该如何计算呢？