算法竞赛入门经典

章节摘录

插图：本章介绍一些常见的图论模型和算法，包括最小生成树、单源最短路、每对结点的最短路、最大流、最小费用最大流等。限于篇幅，很多算法都没有给出完整的正确性证明（很容易在其他参考资料中找到相关内容），但给出了简单、易懂的完整代码，方便读者参考。在第6章中，我们第一次接触到二叉树；后来，又接触到了其他树状结构，如解答树、BFS树。本节将继续讨论“树”这一话题。有，？个顶点的树具有以下3个特点：连通、不含圈、恰好包含n-1条边。有意思的是，具备上述3个特点中的任意两个，就可以推导出第3个，有兴趣的读者不妨试着证明一下。1 1．1．1无根树转有根树输入一个，z个结点的无根树的各条边，并指定一个根结点，要求把该树转化为有根树，输出各个结点的父亲编号。

前言

“听说你最近在写一本关于算法竞赛入门的书？”朋友问我。“是的。”我微笑道。“这是怎样的一本书呢？”朋友很好奇。“C语言、算法和题解。”我回答。“什么？几样东西混着吗？”朋友很吃惊。“对。”我笑了，“这是我思考许久后做出的决定。”大学之前的我12年前，当我翻开Sam A.Abolrous所著《C语言三日通》的第一页时，我不会想到自己会有机会编写一本讲解C语言的书籍。当时，我真的只花了3天就学完了这本书，并且自信满满：“我学会C语言啦！我要用它写出各种有趣、有用的程序！”但渐渐地，我认识到了：虽然浅显易懂，但书中的内容只是语言入门，离实际应用还有较大差距，就好比小学生学会造句以后还要下很大功夫才能写出像样的作文。第二本对我影响很大的书是Sun公司的Peter van der Linden（PvdL）所著的《C程序设计奥秘》。作者称该书应该是每一个程序员“在C语言方面的第二本书”，因为“书中绝大部分内容、技巧和技术在其他任何书中都找不到”。原先我只是把自己当成是程序员，但在阅读的过程中，我开始渐渐了解到硬件设计者、编译程序开发者、操作系统编写者和标准制定者是怎么想的。继续的阅读增强了我的领悟：要学好C语言，绝非熟悉语法和语义这么简单。后来，我自学了数据结构，懂得了编程处理数据的基本原则和方法，然后又学习了8086汇编语言，甚至曾没日没夜地用SoftICE调试《仙剑奇侠传》，并把学到的技巧运用到自己开发的游戏引擎中。再后来，我通过《电脑爱好者》杂志上的一则不起眼的广告了解到了全国信息学奥林匹克联赛（当时称为分区联赛，NOIP是后来的称谓）。“学了这么久编程，要不参加个比赛试试？”想到这里，我拉着学校里另外一个自学编程的同学，找老师带我们参加了1997年的联赛——在这之前，学校并不知道有这个比赛。凭借自己的数学功底和对计算机的认识，我在初赛（笔试）中获得全市第二的成绩，进入了复赛（上机）。可我的上机编程比赛的结果是“惨烈”的：第一题有一个测试点超过了整数的表示范围；第二题看漏了一个条件，一分都没得；第三题使用了穷举法，全部超时。考完之后我原以为能得满分的，结果却只得了100分中的20多分，名落孙山。痛定思痛，我开始反思这个比赛。一个偶然的机会，我拿到了一本联赛培训教材。书上说，比赛的核心是算法（Algorithm），并且推荐使用Pascal语言，因为它适合描述算法。我从别人那里复制来了Turbo Pascal 7.0（那时网络并不发达），开始研究起来。由于先学的是C语言，所以我刚开始学习Pascal时感到有些不习惯：赋值不是“=”而是“:=”，简洁的花括号变成了累赘的begin和end，if之后要加个then，而且和else之间不允许写分号……但很快我就发现，这些都不是本质问题。在编写竞赛题的程序时，我并不会用到太多的高级语法。Pascal的语法虽然稍微啰嗦一点，但总体来说是很清晰的。就这样，我只花了不到一天时间就把语法习惯从C转到了Pascal，剩下的知识就是在不断编程中慢慢地学习和熟练——学习C语言的过程是痛苦的，但收益也是巨大的，“轻松转到Pascal”只是其中一个小小的例子。我学习计算机，从一开始就不是为了参加竞赛，因此，在编写算法程序之余，我几乎总是使用熟悉的C语言，有时还会用点汇编，并没有觉得有何不妥。随着编写应用程序的经验逐渐丰富，我开始庆幸自己先学的是C语言——在我购买的各类技术书籍中，几乎全部使用的是C语言而不是Pascal语言，尽管偶尔有用Delphi的文章，但这种语言似乎除了构建漂亮的界面比较方便之外，并没有太多的“技术含量”。我始终保持着对C语言的熟悉，而事实证明这对我的职业生涯发挥了巨大的作用。

内容概要

刘汝佳，1982年12月生，高中毕业于重庆市外国语学校。



    2000年3月获得NOI2000全国青少年信息学奥林匹克竞赛一等奖第四名，进入国家集训队，并因此保送到清华大学计算机科学与技术系。大一时获2001年ACM／ICPC国际大学生程序设计竞赛亚洲一上海赛区冠军和2002年世界总决赛银牌(世界第四)，2005年获学士学位，2008年获硕士学位。



    学生时代曾为中国计算机学会NOI科学委员会学生委员，担任IOI2002-2008中国国家队教练，并为NOI系列比赛命题十余道。现为NOI竞赛委员会委员，并在NOI 25周年时获得中国计算机学会颁发的“特别贡献奖”。



    2004年至今共为ACM／ICPC亚洲赛区命题二十余道，担任6次裁判和2次命题总监，并应邀参加IOI和ACM／lCPC相关国际研讨会，发表论文两篇。



    2004年初作为第一作者出版专著《算法艺术与信息学竞赛》，2009年出版译著《编程挑战》。



    多年来在全国二十余个城市进行中学生竞赛培训工作，为北京、上海、吉隆坡等地的著名高校授课与宣讲，并多次与TopCodet、百度和网易有道等知名企业合作举办比赛，让更多的IT人才获得展示自我的平台。

书籍目录

第1部分 语言篇

第1章 程序设计入门 1

1.1 算术表达式 1

1.2 变量及其输入 3

1.3 顺序结构程序设计 6

1.4 分支结构程序设计 9

1.5 小结与习题 13

1.5.1 数据类型实验 13

1.5.2 scanf输入格式实验 13

1.5.3 printf语句输出实验 13

1.5.4 测测你的实践能力 14

1.5.5 小结 14

1.5.6 上机练习 15

第2章 循环结构程序设计 16

2.1 for循环 16

2.2 循环结构程序设计 19

2.3 文件操作 23

2.4 小结与习题 27

2.4.1 输出技巧 28

2.4.2 浮点数陷阱 28

2.4.3 64位整数 28

2.4.4 C++中的输入输出 29

2.4.5 小结 30

2.4.6 上机练习 31

第3章 数组和字符串 33

3.1 数组 33

3.2 字符数组 37

3.3 最长回文子串 41

3.4 小结与习题 45

3.4.1 必要的存储量 45

3.4.2 用ASCII编码表示字符 45

3.4.3 补码表示法 46

3.4.4 重新实现库函数 47

3.4.5 字符串处理的常见问题 47

3.4.6 关于输入输出 47

3.4.7 I/O的效率 47

3.4.8 小结 49

3.4.9 上机练习 50

第4章 函数和递归 51

4.1 数学函数 51

4.1.1 简单函数的编写 51

4.1.2 使用结构体的函数 52

4.1.3 应用举例 53

4.2 地址和指针 56

4.2.1 变量交换 56

4.2.2 调用栈 57

4.2.3 用指针实现变量交换 59

4.2.4 初学者易犯的错误 61

4.3 递归 62

4.3.1 递归定义 62

4.3.2 递归函数 63

4.3.3 C语言对递归的支持 64

4.3.4 段错误与栈溢出 66

4.4 本章小结 67

4.4.1 小问题集锦 67

4.4.2 小结 68

第2部分 算法篇

第5章 基础题目选解 69

5.1 字符串 69

5.1.1 WERTYU 69

5.1.2 TeX括号 70

5.1.3 周期串 71

5.2 高精度运算 71

5.2.1 小学生算术 72

5.2.2 阶乘的精确值 72

5.2.3 高精度运算类bign 73

5.2.4 重载bign的常用运算符 75

5.3 排序与检索 77

5.3.1 6174问题 77

5.3.2 字母重排 78

5.4 数学基础 81

5.4.1 Cantor的数表 81

5.4.2 因子和阶乘 82

5.4.3 果园里的树 84

5.4.4 多少块土地 86

5.5 训练参考 86

5.5.1 黑盒测试 86

5.5.2 在线评测系统 87

5.5.3 推荐题目 88

第6章 数据结构基础 89

6.1 栈和队列 89

6.1.1 卡片游戏 89

6.1.2 铁轨 91

6.2 链表 93

6.2.1 初步分析 93

6.2.2 链式结构 95

6.2.3 对比测试 96

6.2.4 随机数发生器 98

6.3 二叉树 99

6.3.1 小球下落 99

6.3.2 层次遍历 101

6.3.3 二叉树重建 105

6.4 图 106

6.4.1 黑白图像 107

6.4.2 走迷宫 108

6.4.3 拓扑排序 110

6.4.4 欧拉回路 111

6.5 训练参考 112

第7章 暴力求解法 114

7.1 简单枚举 114

7.1.1 除法 114

7.1.2 最大乘积 115

7.1.3 分数拆分 115

7.1.4 双基回文数 116

7.2 枚举排列 116

7.2.1 生成1～n的排列 116

7.2.2 生成可重集的排列 118

7.2.3 解答树 118

7.2.4 下一个排列 119

7.3 子集生成 120

7.3.1 增量构造法 120

7.3.2 位向量法 121

7.3.3 二进制法 122

7.4 回溯法 123

7.4.1 八皇后问题 123

7.4.2 素数环 126

7.4.3 困难的串 127

7.4.4 带宽 128

7.5 隐式图搜索 129

7.5.1 隐式树的遍历 129

7.5.2 一般隐式图的遍历 130

7.5.3 八数码问题 131

7.5.4 结点查找表 133

7.6 训练参考 136

第8章 高效算法设计 138

8.1 算法分析初步 138

8.1.1 渐进时间复杂度 138

8.1.2 上界分析 140

8.1.3 分治法 140

8.1.4 正确对待算法分析结果 142

8.2 再谈排序与检索 143

8.2.1 归并排序 143

8.2.2 快速排序 145

8.2.3 二分查找 145

8.3 递归与分治 148

8.3.1 棋盘覆盖问题 148

8.3.2 循环日程表问题 149

8.3.3 巨人与鬼 149

8.3.4 非线性方程求根 150

8.3.5 最大值最小化 151

8.4 贪心法 151

8.4.1 最优装载问题 151

8.4.2 部分背包问题 152

8.4.3 乘船问题 152

8.4.4 选择不相交区间 152

8.4.5 区间选点问题 153

8.4.6 区间覆盖问题 154

8.4.7 Huffman编码 154

8.5 训练参考 156

第3部分 竞赛篇

第9章 动态规划初步 158

9.1 数字三角形 158

9.1.1 问题描述与状态定义 158

9.1.2 记忆化搜索与递推 159

9.2 DAG上的动态规划 161

9.2.1 DAG模型 161

9.2.2 最长路及其字典序 162

9.2.3 固定终点的最长路和最短路 163

9.3 0-1背包问题 167

9.3.1 多阶段决策问题 167

9.3.2 规划方向 168

9.3.3 滚动数组 169

9.4 递归结构中的动态规划 170

9.4.1 表达式上的动态规划 170

9.4.2 凸多边形上的动态规划 171

9.4.3 树上的动态规划 171

9.5 集合上的动态规划 172

9.5.1 状态及其转移 173

9.5.2 隐含的阶段 173

9.6 训练参考 174

第10章 数学概念与方法 176

10.1 数论初步 176

10.1.1 除法表达式 176

10.1.2 无平方因子的数 178

10.1.3 直线上的点 179

10.1.4 同余与模算术 180

10.2 排列与组合 182

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

10.2.2 数论中的计数问题 184

10.2.3 编码与解码 186

10.2.4 离散概率初步 187

10.3 递推关系 188

10.3.1 汉诺塔 188

10.3.2 Fibonacci数列 189

10.3.3 Catalan数 191

10.3.4 危险的组合 192

10.3.5 统计n-k特殊集的数目 193

10.4 训练参考 194

第11章 图论模型与算法 196

11.1 再谈树 196

11.1.1 无根树转有根树 196

11.1.2 表达式树 197

11.1.3 最小生成树 199

11.1.4 并查集 200

11.2 最短路问题 201

11.2.1 Dijkstra算法 202

11.2.2 稀疏图的邻接表 203

11.2.3 使用优先队列的Dijkstra算法 204

11.2.4 Bellman-Ford算法 205

11.2.5 Floyd算法 206

11.3 网络流初步 207

11.3.1 最大流问题 207

11.3.2 增广路算法 208

11.3.3 最小割最大流定理 210

11.3.4 最小费用最大流问题 211

11.4 进一步学习的参考 212

11.4.1 编程语言 213

11.4.2 数据结构 213

11.4.3 算法设计 213

11.4.4 数学 214

11.4.5 参赛指南 214

11.5 训练参考 215

附录A 开发环境与方法 216

A.1 命令行 216

A.1.1 文件系统 216

A.1.2 进程 217

A.1.3 程序的执行 217

A.1.4 重定向和管道 218

A.1.5 常见命令 218

A.2 操作系统脚本编程入门 219

A.2.1 Windows下的批处理 219

A.2.2 Linux下的Bash脚本 220

A.2.3 再谈随机数 221

A.3 编译器和调试器 221

A.3.1 gcc的安装和测试 221

A.3.2 常见编译选项 222

A.3.3 gdb简介 223

A.3.4 gdb的高级功能 224

A.4 浅谈IDE 225

编辑推荐

《算法竞赛入门经典》分为三部分：语言篇、算法篇和竞赛篇。首先以实践导向的方式讲解了C／C++的基本语法，然后介绍了算法和数据结构的基础知识，最后是动态规划、数学和图论三大专题。全书短小精悍，但内容全面，既可作为教材，又方便自学。算法在计算机科学乃至于整个科学界的作用日益明显。它们不仅具有重要的理论意义，而且解决了生产生活中的很多实际问题。程序设计竞赛就是这样一类以算法为核心但是偏重实用性的比赛。随着各类比赛规模的逐渐扩大，程序设计竞赛在各高校、IT公司和其他社会各界中越来越受到认可和重视。很多研究工作者和从事IT行业的人尽管不参加这类竞赛，但也希望具有这方面的能力，受到这方面的专业训练。本丛书的前身是5年前的同名图书《算法艺术与信息学竞赛》。5年来，更多的人加入到参赛、命题和组织的队伍中来，各类竞赛的参赛和命题水平也有了长足的进步。作者深知当年的经典之作开始显得题目陈旧，知识的广度和深度也无法达到当今高水平比赛的要求了。因此，将原书的内容扩充、完善后分成三本，以丛书的形式依次展现给读者。这三本书循序渐进，从零语言基础开始讲起，直到超越竞赛本身，真正把算法当成“艺术”。适合语言零基础的初学者涵盖算法竞赛的主要知识点大量经验教训与比赛技巧简洁、清晰、高效的示例代码丰富的辅助教学资源与配套习题

作者简介

《算法竞赛入门经典》是一本算法竞赛的入门教材，把C/C++语言、算法和解题有机地结合在了一起，淡化理论，注重学习方法和实践技巧。全书内容分为11章，包括程序设计入门、循环结构程序设计、数组和字符串、函数和递归、基础题目选解、数据结构基础、暴力求解法、高效算法设计、动态规划初步、数学概念与方法、图论模型与算法，覆盖了算法竞赛入门所需的主要知识点，并附有大量习题。书中的代码规范、简洁、易懂，不仅能帮助读者理解算法原理，还能教会读者很多实用的编程技巧。另外，书中包含的各种开发、测试和调试技巧也是在传统的语言、算法类书籍中难以见到的。

《算法竞赛入门经典》可作为全国青少年信息学奥林匹克联赛（NOIP）的复赛教材及ACM国际大学。

图书封面

---

 算法竞赛入门经典下载 精选章节试读 更多精彩书评

---