当前位置:首页 >> 学科竞赛 >>

NOIP复习资料(C++版)


前 言

NOIP 复习资料
(C++版)





葫芦岛市一高中

李思洋

完成日期

2012 年 8 月 27 日

0

前 言

前 言
有一

天,我整理了 NOIP 的笔记,并收集了一些经典算法。不过我感觉到笔记比较凌乱,并且有很多需要 修改和补充的内容,于是我又搜集一些资料,包括一些经典习题,在几个月的时间内编写出了《NOIP 复习资 料》。 由于急于在假期之前打印出来并分发给同校同学(我们学校既没有竞赛班,又没有懂竞赛的老师。我们大 家都是自学党),《NOIP 复习资料》有很多的错误,还有一些想收录而未收录的内容。 在“减负”的背景下,暑期放了四十多天的假。于是我又有机会认真地修订《NOIP 复习资料》。 我编写资料的目的有两个:总结我学过(包括没学会)的算法、数据结构等知识;与同学共享 NOIP 知识, 同时使我和大家的 RP++。 大家要清醒地认识到,《NOIP 复习资料》页数多,是因为程序代码占了很大篇幅。这里的内容只是信息 学的皮毛。对于我们来说,未来学习的路还很漫长。 基本假设 作为自学党,大家应该具有以下知识和能力: ① 能够熟练地运用 C++语言编写程序(或熟练地把 C++语言“翻译”成 Pascal 语言); ② 能够阅读代码,理解代码含义,并尝试运用; ③ 对各种算法和数据结构有一定了解,熟悉相关的概念; ④ 学习了高中数学的算法、数列、计数原理,对初等数论有一些了解; ⑤ 有较强的自学能力。 代码约定 N、M、MAX、INF 是事先定义好的常数(不会在代码中再次定义,除非代码是完整的程序)。N、M、MAX 针对数据规模而言,比实际最大数据规模大;INF 针对取值而言,是一个非常大,但又与 int 的最大值有一定 差距的数,如 100000000。 对于不同程序,数组下标的下限也是不同的,有的程序是 0,有的程序是 1。阅读程序时要注意。 阅读顺序和方法 没听说过 NOIP,或对 NOIP 不甚了解的同学,应该先阅读附录 E,以加强对竞赛的了解。 如果不能顺利通过初赛,你就应该先补习初赛知识。这本《NOIP 复习资料》总结的是复赛知识。 如果没有学过 C++语言,应该先选择一本 C++语言教材。一般情况下,看到“面向对象编程”一章的前一 页就足够了(NOIP 不用“面向对象编程”,更不用摆弄窗口对话框)。 附录 G 介绍了一些书籍和网站。你应该选择一本书,认真地学习。再选择一个网站,作为练习的题库。 第一单元对竞赛中常用的操作和简单的算法分析进行了总结,算作对 C++语言的巩固。同时,阅读这一单 元之后,你应该选择一个合适的 C++代码编辑器。 第二到第六单元介绍了竞赛常用的算法。阅读每一章时,应该先阅读“小结”——名曰“小结”,实际上 是“导读”。 这五个单元除了经典习题,还有某些思想和算法的具体实现方法。这些信息可能在明处,也可能在暗处, 阅读时要注意挖掘和体会。如果有时间,应该在不看解析和代码的前提下独立完成这些题。 第七单元是第六单元的一个部分,由于它的内容来自《背包九讲》,所以单独放在一个单元。 从第八单元开始,到第十三单元,基本上就没有习题了。换句话说,该“背课文”了。 第八单元介绍了常用的排序算法。你可以有选择地学习,但一定要掌握“STL 算法”和“快速排序”。 第九单元介绍了基本数据结构,你一定要掌握第九单元前五小节的内容(本单元也有应该优先阅读的“小 结”)。有余力的话,第六小节的并查集也应该掌握。 1

前 言 第十单元介绍了与查找、检索有关的数据结构和算法。你也可以有选择地学习。 第十一单元与数学有关。数学对于信息学来说具有举足轻重的地位。标有“!”的应该背下来,至于其他 内容,如果出题,你应该能把它解决。 第十二单元仍与数学有关。 第十三单元是图论。学习时要先阅读“小结”,把概念弄清楚。之后要掌握图的实现方法。接下来要掌握 一些经典图论算法:Kruskal 算法、Dijkstra 算法、SPFA、Floyd 算法、拓扑排序。 附录 F 总结了 2004 年以来 NOIP 考察的知识点,可以作为选择性学习的参考。 在学习算法和数据结构的同时,应该阅读和学习附录 A。 如果你还有余力,你应该学习第十四单元。第十四单元的内容不是必须要掌握的,但是一旦学会,可以发 挥 C++语言的优势,降低编程复杂度。 临近竞赛时,应该阅读附录 B 和附录 C,以增加经验,减少失误。 面临的问题 1. 这是复赛复习资料——需要有人能用心总结、整理初赛的知识,就像这份资料一样。 2. 潜在的问题还是相当多的,只是时间不够长,问题尚未暴露。 3. 部分代码缺少解说,或解说混乱。 4. 个人语文水平较差,《资料》也是如此。 5. 没有对应的 Pascal 语言版本。 如果有人能为 P 党写一个 Pascal 版的 STL,他的 RP 一定会爆增!
AT X整理《资料》,并以自由文档形式发布。 6. 希望有人能用 L E

最后,欢迎大家以交流、分享和提高为目的修改、复制、分发本《资料》,同时欢迎大家将《资料》翻译 成 Pascal 语言版供更多 OIer 阅读! 谢谢大家的支持! 葫芦岛市一高中 李思洋 2012 年 8 月 27 日

2





目 录
标题上的符号: 1. !:表示读者应该熟练掌握这些内容,并且在竞赛时能很快地写出来。换句话说就是应该背下来。 2. *:表示内容在 NOIP 中很少涉及,或者不完全适合 NOIP 的难度。 3. #:表示代码存在未更正的错误,或算法本身存在缺陷。

前 言 ........................... 1 目 录 ........................... I 第一单元
1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10

第五单元
5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10

分治算法 ................ 51
一元三次方程求解 .............. 快速幂 ...................... 排序 ........................ 最长非降子序列................ 循环赛日程表问题 .............. 棋盘覆盖..................... 删除多余括号 ................. 聪明的质监员 ................. 模板 ........................ 小结 ....................... 导例:数字三角形 .............. 区间问题:石子合并 ............ 坐标问题..................... 背包问题..................... 编号问题..................... 递归结构问题 ................. DAG 上的最短路径 .............. 树形动态规划* ................ 状态压缩类问题:过河 ........... Bitonic 旅行 ............... 小结 ....................... 部分背包问题 ................. 0/1 背包问题! ................ 完全背包问题 ................. 多重背包问题 ................. 二维费用的背包问题 ............ 分组的背包问题................ 有依赖的背包问题 .............. 泛化物品..................... 混合背包问题 ................. 特殊要求.................... 背包问题的搜索解法 ........... 子集和问题 .................. 常用排序算法 ................. 简单排序算法 ................. 线性时间排序 ................. 使用二叉树的排序算法* .......... 小结 ........................ 51 51 51 53 53 54 55 56 58 59 60 63 65 67 67 68 71 72 74 76 77 78 78 79 79 80 81 81 81 82 82 83 84 85 87 88 89 90

C++语言基础 .............. 1
程序结构 ...................... 1 数据类型 ...................... 4 运算符 ........................ 6 函数 .......................... 8 输入和输出! .................... 9 其他常用操作! ................. 10 字符串操作! ................... 13 文件操作! .................... 13 简单的算法分析和优化 ........... 14 代码编辑器 ................... 16

第六单元
6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 6.10 6.11

动态规划 ................ 60

第二单元
2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9

基础算法 ................ 17
经典枚举问题 .................. 17 火柴棒等式 .................... 18 梵塔问题 ..................... 19 斐波那契数列 .................. 19 常见的递推关系! ............... 20 选择客栈 ..................... 22 2k 进制数 ..................... 23 Healthy Holsteins ........... 24 小结 ......................... 25

第三单元
3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9

搜索 ................... 27
N 皇后问题 .................... 27 走迷宫 ....................... 29 8 数码问题 .................... 31 埃及分数 ..................... 34 Mayan 游戏 ................... 36 预处理和优化 .................. 40 代码模板 ..................... 41 搜索题的一些调试技巧 ........... 43 小结 ......................... 44

第七单元
7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9 7.10 7.11 7.12

背包专题 ................ 78

第四单元
4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9

贪心算法 ................ 46
装载问题 ..................... 46 区间问题 ..................... 46 删数问题 ..................... 47 工序问题 ..................... 47 种树问题 ..................... 47 马的哈密尔顿链 ................ 47 三值的排序 .................... 49 田忌赛马 ..................... 50 小结 ......................... 50

第八单元
8.1 8.2 8.3 8.4 8.5

排序算法 ................ 85

第九单元

基本数据结构 ............ 91
I

目 录 9.1 9.2 9.3 9.4 9.5 9.6 9.7 线性表(顺序结构) ............. 91 线性表(链式结构) ............. 91 栈 .......................... 93 队列 ......................... 94 二叉树 ....................... 95 并查集! ...................... 99 小结 ........................ 102 14.6 示例:合并果子.............. 175

附录 A

思想和技巧 ............... 177
时间/空间权衡 ............... 试验、猜想及归纳 ............. 模型化 ..................... 随机化* .................... 动态化静态 .................. 前序和! .................... 状态压缩*................... 抽样测试法* ................. 离散化* .................... Flood Fill* .............. 常见错误类型 ................ 调试过程.................... 调试功能.................... 符号 DEBUG 的应用 ............ 代码审查表 .................. 故障检查表 .................. 命令行和批处理*.............. 赛前两星期 .................. 赛前 30 分钟 ................. 解题表 ..................... 测试数据.................... 交卷前 5 分钟 ................ 避免偶然错误 ................ 骗分 ....................... 177 177 177 178 178 179 180 182 183 184 185 185 185 186 186 187 188 192 192 193 195 196 196 197

第十单元
10.1 10.2 10.3 10.4 10.5 10.6 10.7 11.1 11.2 11.3 11.4 11.5 11.6 11.7 11.8 11.9 11.10 12.1 12.2 12.3 12.4 12.5 12.6 13.1 13.2 13.3 13.4 13.5 13.6 13.7 13.8 13.9 13.10 13.11 14.1 14.2 14.3 14.4 14.5 II

查找与检索 ............. 104
顺序查找 ................... 104 二分查找! .................. 104 查找第 k 小元素! ............. 105 二叉排序树 .................. 106 堆和优先队列* ............... 108 哈夫曼(Huffman)树 ......... 110 哈希(Hash)表 .............. 111

A.1 A.2 A.3 A.4 A.5 A.6 A.7 A.8 A.9 A.10

附录 B
B.1 B.2 B.3 B.4 B.5 B.6 B.7

调试 .................... 185

第十一单元

数学基础 ............. 116

组合数学 ................... 116 组合数的计算! ............... 117 排列和组合的产生(无重集元素)! 117 排列和组合的产生(有重集元素) . 120 秦九韶算法 .................. 122 进制转换(正整数) ........... 123 高精度算法(压位存储)! ....... 123 快速幂! .................... 128 表达式求值 .................. 129 解线性方程组* .............. 133

附录 C
C.1 C.2 C.3 C.4 C.5 C.6 C.7

竞赛经验和教训 ............ 192

第十二单元

数论算法 ............. 135

同余的性质! ................. 135 最大公约数、最小公倍数! ....... 135 解不定方程 ax+by=c!* ....... 135 同余问题* .................. 136 素数和素数表 ................ 136 分解质因数 .................. 137

附录 D

学习建议 ................. 198

D.1 学习方法.................... 198 D.2 学习能力.................... 198 D.3 关于清北学堂 ................ 198

第十三单元

图与图论算法 .......... 139

附录 E
E.1 E.2 E.3 E.4

竞赛简介 ................. 199
从 NOIP 到 IOI ............... NOIP 简介 .................. 常用语 ..................... 第一次参加复赛…… ........... 199 199 201 202

图的实现 ................... 139 图的遍历 ................... 141 连通性问题 .................. 142 欧拉回路 [邻接矩阵] ......... 146 最小生成树(MST) ........... 147 单源最短路问题(SSSP 问题) ... 148 每两点间最短路问题(APSP 问题)!152 拓扑排序 ................... 152 关键路径 ................... 155 二分图初步 ................. 157 小结 ...................... 160

附录 F 附录 G

NOIP 复赛知识点分布 ....... 204 资料推荐 ................. 205

G.1 书籍 ....................... 205 G.2 网站 ....................... 205

参考文献 ....................... 206 计算机专业是朝阳还是夕阳? ........ 207 杜子德在 CCF NOI2012 开幕式上的讲话 209 多数奥赛金牌得主为何难成大器 ...... 210

第十四单元

STL 简介 ............. 164

STL 概述 ................... 164 常用容器 ................... 164 容器适配器 .................. 170 常用算法 ................... 171 迭代器 ..................... 175

第一单元 C++语言基础

第一单元 C++语言基础
1.1 程序结构
(1) 程序框架
? ? ? ? ? 注释:注释有两种,一种是“//”,另一种是“/* ? */”。“//”必须单独放置一行,或代码所在行 的后面;而“/*”、“*/”成对存在,可以插入到代码的任意位置。 引用头文件:在代码开头写“#include <头文件名>”。如果想引用自己的头文件,需要把尖括号(表 示只从系统目录搜索头文件)换成双引号(表示先从 cpp 所在文件夹搜索,然后再到系统文件夹搜索)。 命名空间:很多 C++的东西都要引用 std 命名空间,所以代码中会有“using namespace std;”。 main():所有程序都要从 main()开始。 在所有的算法竞赛中,main()的返回值必须是 0,否则视为程序异常结束,得分为 0 分。 语句和语句块: 1. 语句:一般情况下,一条语句要用一个分号“;”结束。为了美观和可读性,可以把一条语句扩展成 几行,也可以把多个语句写到同一行上。 2. 语句块:用“{”和“}”包围的代码是语句块。无论里面有多少代码,在原则上,语句块所在的整体 都视为一条语句。

(2) 选择结构
1. if 语句: if 表示判断。 如果条件为真, 就执行接在 if 后的语句 (语句块) , 否则执行 else 后的语句 (语 句块)。如果没有 else,就直接跳过。if 有以下几种格式: if (条件) // 如果条件成立,就执行if后面的语句或语句块。 语句或语句块 if (条件) 语句或语句块A else 语句或语句块B if (条件1) 语句或语句块A else if (条件2) 语句或语句块B ?? else // 实际上,这是if语句内的if语句,即if的嵌套。所以else和if中间要有空格。 // 如果条件成立,就执行if后面的A,否则执行B。

语句或语句块N 2. switch 语句:switch 表示选择。它根据条件的不同取值来执行不同的语句。格式如下: switch (表达式) { case 值1: 代码段A break; case 值2: 代码段B break; 1

第一单元 C++语言基础 ?? default: 代码段N break; }; 如果表达式的值是值 1, 就执行代码段 A; 如果表达式的值是值 2, 就执行代码段 B??否则执行代码段 N。 注意: ? default 一部分可以省略。 ? 如果不使用 break,那么紧随其后的 case 部分代码也会被执行,直到遇到 break 或 switch 语句 结束为止! ? switch 结尾要有一个分号。 3. if、switch 都可以嵌套使用。 【问题描述】输入一个日期,判断它所在年份是否为闰年,并输出所在月份的天数。闰年的判断方法:四年一 闰,百年不闰,四百年又闰。 int year,month,day; bool b=false; cin>>year>>month>>day; // 判断是否为闰年 if (n%400==0) b=true; else if (n%100!=0 && n%4==0) b=true; if (b) cout<<y<<"是闰年。"<<endl; else cout<<y<<"不是闰年。"<<endl; // 判断所在月份的天数 switch (month) { case 1: case 3: case 5: case 7: case 8: case 10: case 12: cout<<"这个月有31天。"<<endl; break; case 4: case 6: case 9: case 11: cout<<"这个月有30天。"<<endl; break; case 2: cout<<"这个月有"<<(b ? 29 : 28)<<"天。"<<endl; break; };

(3) 循环结构
1. while 语句:如果条件成立,就继续循环,直到条件不成立为止。格式如下: while (条件) 循环体(语句或语句块) 2

第一单元 C++语言基础 2. do?while 语句: 如果条件成立, 就继续循环, 直到条件不成立为止。 它与 while 的最大区别在于, do? while 循环中的语句会被执行至少一次,而 while 中的语句可能一次都没有被执行。格式如下: do { 循环体 } while (条件); // 注意分号 4. for 语句:for 分四部分,有初始条件、继续循环的条件、状态转移的条件和循环体。格式如下: for (初始条件; 继续循环的条件; 状态转移的条件) 循环体 转换成 while 循环,即: 初始条件 while (继续循环的条件) { 循环体 状态转移 } for 后三个条件不是必需的,可以省略不写,但分号必须保留。 5. 在循环语句内部使用 break,可以跳出循环;使用 continue,可以忽略它后面的代码,马上进入下一轮 循环。 注意,这两个语句只对它所在的一层循环有效。 6. 写 for 循环时,一定要注意: ? 不要把计数器的字母打错,尤其是在复制/粘贴一段代码的时候。 ? 根据算法要明确不等号是“<”、“>”,还是“<=”、“>=”。 ? 逆序循环时,不要把自减“--”写成自增“++”! 【问题描述】输入 n,输出 n!(n!=1×2×3×4×??×n)。结果保证小于 long long 的范围。当输入值 为负数时结束程序。 int n; long long r=1; cin>>n; while (n>-1) { r=1; for (int i=1; i<=n; i++) r*=i; cout<<n<<"! = "<<r<<endl; cin>>n; }

(4) goto 语句
goto 语句用于无条件跳转。要想跳转,首先要定义标签(在代码开头的一段标识符,后面紧跟冒号), 然后才能 goto 那个标签。 很多教程不提倡使用无条件跳转,因为它破坏了程序结构,还容易给代码阅读者带来麻烦。不过,这不代 表 goto 没有使用价值。goto 的一个用途是跳出多层循环: for (int i=0; i<9; i++) for (int j=0; j<9; j++) 3

第一单元 C++语言基础 for (int k=0; k<9; k++) { if (满足某种条件) goto __exited; ?? } __exited:

(5) C 与 C++的区别
C++语言是以 C 语言为基础开发出来的,C 语言的大多数内容被保留了下来。在信息学竞赛领域,很多情 况下 C 和 C++可以互相转化,甚至不用对代码进行任何修改。 下面是信息学竞赛领域中 C 和 C++的重要区别: ? C++支持用流输入输出,而 C 只能用 scanf 和 printf——再见了,%d! ? C++非常支持面向对象编程,而 C 已经“out”了。 《资料》中的“高精度算法”就只能用 C++完成,因为在 struct 内定义了成员函数。 C++可以用更强大的 string 类处理字符串,而不必担心发生某些低级错误。 ? C++有强大的 STL,而 C 没有(有一个小小的 qsort 和 bsearch 算是补偿了) 。 STL 是很多人从 C 转到 C++的重要原因。 ? C 的头文件名仍然可以用在 C++中,不过可能会收到警报——应该去掉“.h” ,前面再加一个“c” 。 如<stdio.h>应该改成<cstdio>。 ? C 程序运行速度稍优于 C++。不过也没快多少。 总之,C 能做的一切事情,C++也能做;C++能做的一切事情,C 不一定能做。

1.2 数据类型
(1) 基本数据类型
名称 int unsigned int① char unsigned char short


占用空间 4 4 1 1 2 2 8 8 1 1 1

别名 signed, signed int, long, long int unsigned, unsigned long,unsigned long int char unsigned char short int, signed short int unsigned short int signed long long

数据范围 –2,147,483,648~2,147,483,647 0~4,294,967,295 –128~127 0~255 –32,768~32,767 0~65,535 –9,223,372,036,854,775,808~ 9,223,372,036,854,775,807④ 0~18,446,744,073,709,551,615 true 或 false –128~127 –128~127

unsigned short long long


unsigned long long bool char signed char

① ② ③ ④

一般都使用有符号整数,除非范围不够大,或者你确定你的减法运算不会出现―小数减大数‖。 一般来说,使用 int、long long 更保险一些,除非内存不够用。 不要使用“__int64”!它是 Visual C++特有的关键字。 假如 a 是 long long 类型,把超过 231 的值赋给它时要使用字面值 LL(ULL):a=123456789012345LL。

4

第一单元 C++语言基础 unsigned char float double 1 4 8 long double 0~255 3.4E +/- 38 (7 位有效数字) 1.7E +/- 308 (15 位有效数字)

(2) 变量与常量
1. 定义变量:“变量类型 标识符”,如“int i;”定义了一个名字为 i 的整型变量。 注意,此时 i 并未初始化,所以 i 的值是不确定的。 2. 定义常量:“const 变量类型 标识符=初始值”,如:const int N=90; 3. 合法的标识符: ? 标识符不能和关键字(在 IDE 中会变色的词语)相同。 ? 标识符只能包括字母、数字和下划线“_”,并且开头只能是字母或下划线。 ? 标识符必须先定义后使用。 ? 在同一作用域内,标识符不能重复定义(即使在不同作用域内也不应重复,否则容易产生歧义)。 ? C++区分大小写。所以 A 和 a 是两个不同的标识符。

(3) 数组
1. 定义一个一维数组:int a[10]; 这个数组一共 10 个元素,下标分别为 0~9。访问某个元素时,直接用 a 加方括号,如 a[5]。 2. 定义一个二维数组:int b[5][3]; 这个数组一共 5×3=15 个元素,分别是 b[0][0]、b[0][1]、b[0][2]、b[1][0]??b[4][2]。 访问某个元素时要用两个方括号,如 b[2][1]。 多维数组的定义和使用方法与此类似。 3. 数组名和元素的寻址:以上面的 a、b 为例 ? 数组名是一个指针,指向整个数组第一个元素所在的地址。如 a 就是&a[0]、b 就是&b[0][0]。 ? 多维数组的本质是数组的数组,所以 b[0]实际上是 b[0][0]、b[0][1]??的数组名,b[0]就是 &b[0][0]。 ? 在内存中, 数组中每个元素都是紧挨着的, 所以可以直接进行指针的运算。 如 a+3 就是&a[3], **(b+1) 就是 b[1][0],*(*(b+3)+2)就是 b[3][2]。 ? 在竞赛中要尽可能回避这些功能。 4. 字符串: ? 字符串实际上是 char 的数组。 ? 字符串最后一位必须是'\0',否则会在进行输出、使用字符串函数时发生意外。 ? 数组, 包括字符串, 不可以整体地赋值和比较。 如果需要, 应使用 memcpy 和 memcmp (字符串是 strcpy 和 strcmp)。 5. C++中数组的下标只能从 0 开始(当然可以闲置不用),并且 int a[10]中 a 的最后一个元素是 a[9], 不是 a[10]! 6. C++不检查数组下标是否越界!如果下标越界,程序很有可能会崩溃!

(4) 指针
1. 取地址运算符和取值运算符: ? 取地址运算符“&”:返回变量所在的地址。一般用于变量。(而数组名本身就是指针,无需“&”) ? 取值运算符“*”:返回地址对应的值,或用于改变指针所指内存空间的值。只能用于指针。 2. 指针的意义:保存另一个变量的内存地址。 3. 定义指针:int *p; 5

第一单元 C++语言基础 定义多个指针时,每个字母的前面都要有“*”。 注意,如果 p 没有被初始化,它就会指向一个未知的内存空间,而错误地操作内存会导致程序崩溃! 4. 指针使用实例: int a = 0, b = 1; int c[] = {1,2,3,4,5,6,7,8,9,10}; int *p; // 定义一个指针 p=&a; // 让p指向a (*p)=3; // 相当于a=3 (*p)=b; // 相当于a=b,此时a等于1 // p=b; // 非法操作,左边是int *,右边是int,类型不匹配。 p=&b; // 让p指向b,从此p和a没关系了 p=c+6; // 让p指向c[6],p和b又没关系了 cout<<*p; // 输出p指向的变量的值,即c[6] p++; // 现在p指向了c[7]; p=NULL; // 表示p没有指向任何变量 cout<<*p; // 由于NULL(0)是一段无意义的地址,所以程序极有可能崩溃。 为了不在竞赛中把自己搞晕,请回避指针,对其敬而远之。

(5) 引用
通俗地讲,引用是某个变量的别名。下面定义了一个叫 p 的引用,它实际上是 f[0][2]。无论是改变 p 的值,还是改变 f[0][2]的值,结果都是一样的。 int &p = f[0][2]; 使用引用的好处是,在函数的形参中定义引用类型,可以直接修改变量的值,而不用考虑“&”和“*”运 算符。像上面一行代码一样,如果频繁调用 f[0][2],也可以用引用节省篇幅,提高代码可读性。 引用与指针不同。引用被创建的同时也必须被初始化,并且必须与合法的存储单元关联。一旦引用被初始 化,就不能改变引用的关系。而指针可以不立刻初始化,也可以改变所指向的内存空间。

(6) 结构体
? 结构体用 struct 定义。例如下面代码定义了一个叫 pack 的结构体,它有两个成员,一个叫 value,另 一个叫 weight。 struct pack { int value, weight; }; ? ? ? ? 变量可以定义成上面的 pack 类型:pack p; // 不必写成 struct pack p; 访问 pack 的成员时,用“.”运算符(指针变量用“->”):p.value、(&p)->value C++中结构体可以像类一样建立自己的构造函数、成员函数,也可以重载运算符。 对于 pack 这个结构体,它的内部不允许再有 pack 类型的成员,但是可以有 pack 类型的指针。

1.3 运算符
(1) 运算符的优先级
运算符 :: .(对象成员) ->(指针) [](数组下标) ()(函数调用) 6 结合方式 无 从左向右

第一单元 C++语言基础 运算符 ++ -- (typecast)(强制类型转换) sizeof ~ ! +(一元) -(一元) *(取值运算符) &(取地址运算符) new delete .* ->* * + / %(取余数) 结合方式 从右向左 从左向右 从左向右 从左向右 从左向右 从左向右 从左向右 从左向右 从左向右 从左向右 从左向右 从左向右 从右向左 从右向左 从左向右

<<(左移) >>(右移) < <= > >= ==(判断相等) !=(判断不等) &(按位与) ^(异或) |(按位或) &&(条件与) ||(条件或) ?:(条件运算符) = *= /= %= += -= &= ^= >>= <<= ,

(2) 常用运算符的作用
1. 算术运算符:+、-、*、/、%分别表示加、减、乘、除、取余。 两个整数做除法时,如果除不开,程序将把小数部分直接截断(不是四舍五入)。即:整数/整数=整数, 浮点数/浮点数=浮点数。 学习过其他语言的同学要注意,C++中没有乘方运算符,“^”也不是乘方运算符。 2. 比较运算符: ? >、>=、<、<=、==(相等)、!=(不等)用来判断不等关系,返回值是 true 或 false。 小心,千万不要把“==”写成“=”! ? 永远不要对浮点数使用==和!=运算符!正确的做法是: const double eps = 0.000001; // 自己控制精度 …… if (d>=2-eps && d<=2+eps) …… // 相当于 if (d==2) ? 不应该判断一个变量的值是否等于 true。安全的做法是判断它是否不等于 false。 位运算: ? &、|、^分别表示按位与、按位或、按位异或,即两个操作数上每一个二进制位都要进行运算。 ? ~表示按位求反。 ? <<、>>表示二进制位的移动。当某一位数字移动到二进制位的外面之后,它就直接“消失”了。 a<<n 相当于 a×2n,a>>n 相当于 a÷2n。 逻辑运算符: ? &&、||、^分别表示与、或、异或。!表示非。 ? ?:是条件运算,它是 C++唯一一个三目运算符。它的格式如下:A ? B : C。 如果 A 不为 false,那么返回 B,否则返回 C。 可以将这个运算符理解为一个简化版的 if。 ? ||、&&、?:是短路运算符①。不要在这三种运算符内调用函数或赋值,以免发生难以查出的错误! 比较运算符、位移运算符、逻辑运算符、条件运算符的优先级较低,所以使用时要多加括号,以防出错。 自增(++)、自减(--)运算符:

3.

4.

5. 6.


例如计算“a && b”,如果 a 为 false,那么实际上结果就是 false——不管 b 是什么,程序都不再计算了。

7

第一单元 C++语言基础 ? ? ? 增量分别是 1 和-1。 这两种运算符只能用于数值类型的变量,不能用于非数值类型变量、常量、表达式和函数调用上。 前缀++、--和后缀++、--的作用效果不同: int i=0, j=8, k=5;

j = j + (++i); // i 先自增,变成 1,然后再和 j 相加。执行之后 i=1,j=9。 k = k + (i++); // i 先和 k 相加,使 k=6。然后 i 再自增。执行之后 i=2,k=6。 ? 前缀运算符返回引用类型,后缀运算符返回数值类型。 ? 为了避免错误,不要让++、--和其他能够改变变量的操作在同一行出现! 7. 赋值运算符: ? 在 C++中赋值是一种运算符。所以你会看到 i=j=0、d[x=y]、return c=i+j 之类的代码。 ? +=、-=、*=、??可以简化书写。例如 a*=2+3 相当于 a=a*(2+3)。

(3) 真值表
p true (1) true (1) false (0) false (0) q true (1) false (0) true (1) false (0) p && q (p & q) true (1) false (0) false (0) false (0) p || q (p | q) true (1) true (1) true (1) false (0) p ^ q false (0) true (1) true (1) false (0) !p (~p) false (0) false (0) true (1) true (1)

(4) 类型强制转换
用一对小括号把数据类型包上,则它右侧的变量或常量的值(变量本身不变)就变成了对应的类型。如: int i=2; float c=6.4/(float)i; // 把i的值变成float类型。 两个操作数进行四则运算,如果想保留小数位,那么两个操作数应该都是浮点数。上面的代码就是这样。

1.4 函数
(1) 定义和使用函数
1. 定义和调用函数:下面定义了一个函数,返回值是 double 类型的,其中有两个参数 i、j,分别是 int 和 float 类型的。 double foo(int j, float j) { ?? } 如果函数不需要返回任何值,可定义为 void 类型。 函数的定义必须在函数调用的前面。只有在前面添加了函数定义,才能把具体实现放到调用的后面: double foo(int, float); // 放到调用之前 2. 返回值:return 值; ? 函数是 void 类型的,那么 return 后面除了分号,什么都不跟。 ? 调用之后,函数立刻结束。 ? 不可以直接对函数名赋值(学过 Pascal 或 Basic 语言的同学要特别注意)。 3. 如果你的函数需要返回指针或引用,你必须注意:不要引用函数内部的变量!因为函数一结束,函数内部 的变量就烟消云散,不复存在了。正确做法是引用静态变量(static)或全局变量。 4. 内联函数(inline):当一个函数内部只有寥寥几句时,如“华氏度变摄氏度”,可以考虑将其定义成 8 ? ?

第一单元 C++语言基础 内联函数,通知编译器省略函数入栈等操作,直接展开函数内容,以加快运行速度。 inline int FtoC(int f) { return (f-32)/9*5; }

(2) 传递实参
1. 按值传递:例如 int foo(int n),在调用 foo 时,程序会把参数复制一份给 n。这样,对 n 的任何修 改都不会反映到调用 foo 的参数上面。 对于按值传递数组,一定要慎重。因为复制数组的元素要浪费很多时间。 2. 传递指针:例如 int foo(int *n)。对 n 的修改会反映到调用 foo 的参数上面。 ? 修改 n 的值时要注意,必须用取值运算符,否则改变的是 n 指向的内存空间①。 ? 此外,这种方法可以用于传递数组——调用时只需把数组名作为参数。这时不需要取值运算符。 3. 传递引用:例如 int foo(int &n)。 优点是既可以直接修改调用 foo 的参数,又不会带来指针的麻烦(无需取值运算符)。缺点是不能传入常 数或表达式。

1.5 输入和输出!
(1) 使用标准输入/输出
头文件:<cstdio> 变量约定:FILE *fin, *fout;——fin、fout 分别代表输入文件和输出文件。把它们换成 stdin 和 stdout,就是从屏幕输入和从屏幕输出。“1.5 字符串操作”也使用了同样的变量。 1. 输出字符串或变量的值:printf("格式字符串", ??); 或 fprintf(fout, "格式字符串", ??); 格式字符:“%”后连接一个字母。 字符 d u o x, X 含义 整数


字符 e, E f c s

含义 用科学记数法表示的浮点数 浮点数 字符 字符串(字符数组)

无符号整数 八进制整数 十六进制整数(小写、大写)

常见的修饰符: ? %5d:5 位数,右对齐。不足 5 位用空格补齐,超过 5 位按实际位数输出。 ? %-5d:5 位数,左对齐。不足 5 位用空格补齐,超过 5 位按实际位数输出。 ? %05d:5 位数,右对齐。不足 5 位用'0'补齐,超过 5 位按实际位数输出。 ? %+d:无论是正数还是负数,都要把符号输出。 ? %.2f:保留 2 位小数。如果小数部分超过 2 位就四舍五入,否则用 0 补全。 1. 输入到变量 ? 读取不含空白的内容:scanf("格式字符串", &??); 或 fscanf(fin, "格式字符串", &??); ① 格式字符和 printf 基本一致。 ② 不要忘记“&”!printf 传的是值,scanf 传的是地址! ③ scanf 和 fscanf 的返回值是:成功输入的变量个数。fscanf 返回 EOF,表示文件结束。 ④ scanf 和 fscanf 忽略 TAB、空格、回车。遇到这些字符它们就停止读取。 ? 读取单个字符:fgetc(fin); 首先要判断它是否为 EOF(文件结束)。如果不是,就可以用强制类型转换变成 char。
① ②

使用 const 可防止 n 指向的内存空间发生改变:int foo(const int *n)。这时再写 n=5 之类的语句会被报错。 在 Windows 下调试时,用“%I64d”输出 long long 类型的值。交卷时,由于用 Linux 测试,要改成“%lld”。

9

第一单元 C++语言基础 ? 读取到行末时,要注意对换行符的处理。 Windows、Linux、Mac 的回车字符是不同的。Linux 是'\n',Mac 是'\r',Windows 下是两个 字符——'\r'和'\n'。

(2) 使用流输入/输出
1. 2. 3. 4. 头文件:<iostream> 输入到变量:cin>>n; 输出到屏幕上:cout<<a; 可以连续输入、输出,如 cin>>n>>m; cout<<a<<','<<b<<endl; 换行:cout<<endl; 格式化输出: 头文件:<iomanip> ? 右对齐,长度为 n,不足的部分用空格补齐: cout.width(n); cout.fill(' '); cout<<a; // 如果想用“0”补齐,就可以把空格换成“0”

前两行代码,每次输出之前都要调用。 ? 输出成其他进位制数: 8: cout<<oct<<a; 16: cout<<hex<<a; 其他进位制需要自己转换。 5. 注意,数据规模很大时,流的输入输出速度会变得很慢,甚至数据还没读完就已经超时了。 在进行输入输出之前加入这样一条语句:ios::sync_with_stdio(false); 调用之后,用 cin、cout 输入输出的速度就和 scanf、printf 的速度一样了。

1.6 其他常用操作!
本资料常用的头文件:<iostream>、<cstdlib>、<cstring>、<fstream>以及<algorithm>、 <stack>、<queue>、<vector>等。 C++的流、容器、算法等都需要引用 std 命名空间。所以需要在#include 后面、你的代码前面加上一句: using namespace std;

(1) 库函数
1. 数组的整体操作: 头文件:<cstring> ? 将 a[]初始化:memset(a, 0, sizeof(a)); 第二个参数应该传入 0、-1 或 0x7F。传入 0 或-1 时,a[]中每个元素的值都是 0 或-1;如果传入 0x7F 时,那么 a[]中每个元素的值都是 0x7F7F7F7F(不是 0x7F!),可认为是“无穷大”。 ? 将 a[]整体复制到 b[]中:memcpy(b, a, sizeof(a)); ? 判断 a[]和 b[]是否等价:memcmp(a, b, sizeof(a)); // 返回 0 表示等价 2. 字符操作: 头文件:<cctype> ? tolower(c)、toupper(c):将 c 转化为小写或大写。 ? isdight(c)、isalpha(c)、isupper(c)、islower(c)、isgraph(c)、isalnum(c):分别 判断 c 是否为十进制数字、英文字母、大写英文字母、小写英文字母、非空格、字母或数字。 3. 最大值/最小值: 头文件:<algorithm> 10

第一单元 C++语言基础 max(a,b)返回 a 和 b 中的最小值,min(a,b)返回 a 和 b 中的最大值。 其实我们可以自己写: 交换变量的值:swap(a,b) 头文件:<algorithm> 其实我们可以自己写:inline void swap(int &a, int &b) { int t=a; a=b; b=t; } 执行 DOS 命令或其他程序:system("命令行"); ? 头文件:<cstdlib> ? 暂停屏幕:system("pause"); ? 竞赛交卷或 OJ 提交代码之前必须删除 system, 否则会被视为作弊 (如果是 tyvj 甚至都无法提交) 。 ? 如果使用输入重定向,那么命令提示符不会接受任何键盘输入——直接用文件内容代替键盘了。 立刻退出程序:exit(0); 这种方法常用于深度优先搜索。执行后,程序立刻停止并返回 0,所以在调用前应该输出计算结果。 头文件:<cstdlib> 计时:double a = (double)clock() / (double)CLOCKS_PER_SEC; 上面的 a 对应一个时刻。而将两个时刻相减,就是时间间隔。可用这种方法卡时。 头文件:<ctime> 断言:assert(条件) ? 条件为假时,程序立刻崩溃。 ? 头文件:<cassert> ? 如果定义了 NDEBUG 符号,那么它将不会起任何作用。 ? 断言和错误处理不同:例如出现“人数为负数”的情况,如果责任在于用户,那么应该提示错误并重 新输入,而不是用断言;如果发生在计算过程,应该用断言来使程序崩溃,以帮助改正代码中的错误。 换句话说,错误处理防的是用户的错误,断言防的是代码的错误。 快速排序:qsort(首项的指针, 待排序元素个数, 每个元素所占字节, 比较函数) ? 头文件:<cstdlib> ? 这是留给 C 党的快速排序,它比 STL 的排序算法啰嗦一些。 ? 比较函数返回 int 类型,用于对两个元素的比较。原型如下: int compare(const void *i, const void *j);

4.

5.

6.

7.

8.

9.

如果*i<*j,则应返回一个小于 0 的数;如果*i==*j 则应返回 0,否则返回一个大于 0 的数。 10. 随机数发生器: ? 头文件:<cstdlib> ? 产生随机数: ① 0~32767 的随机数:rand() ② 粗略地控制范围:rand()%范围 注意,这种方法产生的随机数的分布是不均匀的。 ③ 精确地控制范围:(double)rand()/RAND_MAX*范围 ④ 控制在[a, b)之间:a + (int) ((double)rand()/RAND_MAX*(b-a)) ? 初始化随机数种子: ① srand(数字):初始化随机数种子。 ② 注意,这条语句在程序开头使用,并且最多用一次。同一程序、同一平台,srand 中的参数相等, 用 rand()产生的随机数序列相同。 ③ 使随机数更加随机:引用<ctime>,然后这样初始化随机数种子,srand(time(NULL))。 不要在循环中使用这条语句(例如批量产生随机数据),因为 time 只精确到秒。 11. 数学函数: ? 头文件:<cmath> ? abs(x):求 x 的绝对值(该函数同时包含于<cstdlib>)。 ? sin、cos、tan、asin、acos、atan:三角函数,角的单位为弧度。 可用 atan(1)*4 表示 π。 11

第一单元 C++语言基础 ? ? ? ? ? ? sinh、cosh、tanh、asinh、acosh、atanh:双曲函数 sqrt:求平方根 ceil(x)、floor(x):分别返回大于等于 x 的最小整数、小于等于 x 的最大整数。注意,参数和返 回值都是浮点数类型。 exp(x)、log(x)、log10:分别求 ex、lnx、lgx (顺便提一句,指数可以把加法问题转化为乘法问题,对数可以把乘法问题转化为加法问题。) pow(a,b):计算 ab。由于精度问题,你仍然需要学会快速幂。 fmod(a,b):计算 a 除以 b 的余数。当然,这是浮点数的版本。

(2) 宏定义
宏定义是 C 语言的产物。在 C++中,它真的 out 了。 1. 第一种用法——配合条件编译:#define DEBUG 定义一个叫 DEBUG 的标识符。它应该与#ifdef 或#ifndef 配合使用。举例如下: #define DEBUG #ifdef DEBUG void print(int v) { cout << v << endl;} #else void print(int) {} #endif 如果符号 DEBUG 存在,那么编译器会编译上面的、能输出数值的 print,否则编译器编译下面的、什么 事情都不做的 print。 把上面的#ifdef 换成#ifndef,那么编译的代码正好上面所说的相反。 2. 第二种用法——表达式: #define N 5000 编译时,编译器会用类似于“查找和替换”的方法,把代码中的 N 换成 5000。如果需要换成表达式,应 该用括号把它们包围。例如: #define a 1+2 #define b (1+2) c=a*2; d=b*2; 编译时上面一行会变成“c=1+2*2; d=(1+2)*1;”,显然它们的值是不同的。 所以,用 enum 和 const 代替它是明智之举。 此外,要注意表达式末尾不能有分号(除非你需要)。 3. 第三种用法——简易“函数”: #define FtoC(a) (((a)-32)/9*5) 这类似于一个函数。不过,由于编译器只是进行简单替换,所以为了安全,a、b 应该用括号包围,整个表 达式也应该用括号包围。 这种“函数”用法和普通函数一样,且速度更快。然而,它很容易出现难以查出的错误。所以,请用内联 函数(inline)代替宏定义。 注意,不要在“参数”中改变变量的值! 4. 第四种用法——简化一段代码: #define move(dx, dy) if (isfull(dir)) return; \ if (map(x+dx, y+dy)=='0') \ { \ push(dir,x+dx,y+dy,head[dir], dep); \ check(dir); \ } 不要忘记每行后面的“\”,它相当于换行符。这次 move 简化了一大段代码。同样,内联函数也可以。 12

第一单元 C++语言基础

1.7 字符串操作!
头文件:<cstring>。printf 和 scanf 在<cstdio>中,cin 和 cout 在头文件<iostream>中且位于 std 命名空间内。 下面假设待处理的字符串为 str 和 str2,即:char str[MAX], str2[MAX]; 牢记,字符串的最后一个字符一定是'\0'。如果字符串内没有'\0',进行以下操作(输入除外)时可能 会造成意外事故。 1. 输出字符串 str: ? cout<<str; ? printf("%s",str); 2. 输入字符串 str: ? scanf("%s", str); ? cin>>str; // 输出到文件:fprintf(fout, "%s", str); // 输出到文件:fscanf(fin, "%s", str);

? 3. 4.

以上两种方法在输入时会忽略空格、回车、TAB 等字符,并且在一个或多个非空格字符后面输入空格 时,会终止输入。 fgets(str, MAX, fin);

5. 6. 7. 8.

9.

每调用一次,就会读取一行的内容(即不断读取,直到遇到回车停止)。 求字符串 str 的长度:strlen(str) // 这个长度不包括末尾的'\0'。 把字符串 str2 连接到字符串 str 的末尾:strcat(str, str2) ? str 的空间必须足够大,能够容纳连接之后的结果。 ? 连接的结果直接保存到 str 里。函数返回值为&str[0]。 ? strncat(str, str2, n)是把 str2 的前 n 个字符连接到 str 的末尾。 把字符串 str2 复制到字符串 str 中:strcpy(str, str2) 比较 str 和 str2 的大小:strcmp(str, str2) 如果 str>str2,返回 1;如果 str==str2,返回 0;如果 str<str2,返回-1。 在 str 中寻找一个字符 c:strchr(str, c) 返回值是一个指针,表示 c 在 str 中的位置。用 strchr 的返回值减 str,就是具体的索引位置。 在 str 中寻找 str2:strstr(str, str2) ? 返回值是一个指针, 表示 str2 在 str 中的位置。 用 strstr 的返回值减 str, 就是具体的索引位置。 ? 此问题可以用 KMP 算法解决。KMP 算法很复杂,在 NOIP 范围内用途不大。 从 str 中获取数据:sscanf(str, "%d", &i); 格式化字符串:sprintf(str, "%d", i); 它们和 fscanf、fprintf 非常像,用法也类似。可以通过这两个函数进行数值与字符串之间的转换。

1.8 文件操作!
正式竞赛时,数据都从扩展名为“in”的文件读入,并且需要你把结果输出到扩展名为“out”的文件中; 在 OJ(Online Judge,在线测评器)中则不需要文件操作。具体情况要仔细查看题目说明,以免发生悲剧。

(1) 输入/输出重定向
头文件:<fstream>或<cstdio> ? 方法:只需在操作文件之前添加以下两行代码。 freopen("XXXXX.in","r",stdin); freopen("XXXXX.out","w",stdout); ? ? 调用两次 freopen 后,scanf、printf、cin、cout 的用法完全不变,只是操作对象由屏幕变成了指 定的文件。 使用输入重定向之后,“命令提示符”窗口将不再接受任何键盘输入(调用 system 时也是如此),直到 13

第一单元 C++语言基础 程序退出。这时不能再用 system("pause")暂停屏幕。

(2) 文件流
头文件:<fstream> 流的速度比较慢,在输入/输出大量数据的时候,要使用其他文件操作方法。 ? 方法:定义两个全局变量。 ifstream fin("XXXXX.in"); ofstream fout("XXXXX.out"); ? fin、fout 和 cin、cout 一样,也用“<<”、“>>”运算符输入/输出,如:fin>>a; fout<<b; 当然,也可以通过#define 把 fin、fout 变成 cin、cout: #define cin fin #define cout fout

(3) FILE 指针
头文件:<cstdio>或<fstream> ? 方法:定义两个指针。 FILE *fin, *fout; ?? int main() { fin = fopen("XXXXX.in", "r"); fout = fopen("XXXXX.out", "w"); ...... fclose(fin); fclose(fout); return 0; } ? ? 进行输入/输出操作时,要注意函数名的前面有 f,即 fprintf、fscanf、fgets,并且这些函数的第 一个参数不是格式字符串,而是 fin 或 fout,如 fprintf(fout, "%d", ans)。 想改成从屏幕上输入/输出时,不用对代码动手术,只需把含 fopen 和 fclose 的代码注释掉,并改成: fin=stdin; fout=stdout; // 在某些情况下,忘记关闭文件会被认为是没有产生文件。

1.9 简单的算法分析和优化
(1) 复杂度
为了描述一个算法的优劣,我们引入算法时间复杂度和空间复杂度的概念。 时间复杂度:一个算法主要运算的次数,用大 O 表示。通常表示时间复杂度时,我们只保留数量级最大的 项,并忽略该项的系数。 例如某算法,赋值做了 3n3+n2+8 次,则认为它的时间复杂度为 O(n3);另一算法的主要运算是比较,做 了 4×2n+2n4+700 次,则认为它的时间复杂度为 O(2n)。 当然,如果有多个字母对算法的运行时间产生很大影响,就把它们都写进表达式。如对 m×n 的数组遍历 的时间复杂度可以写作 O(mn)。 空间复杂度:一个算法主要占用的内存空间,也用大 O 表示。 在实际应用时,空间的占用是需要特别注意的问题。太大的数组经常是开不出来的,即使开出来了,遍历 的时间消耗也是惊人的。 14

第一单元 C++语言基础

(2) 常用算法的时空复杂度
1s 运算次数约为 5,000,000①。 也就是说, 如果把 n 代入复杂度的表达式, 得数接近或大于 5,000,000, 那么会有超时的危险。 常见的数量级大小:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!) 数量级 O(1) O(logn) O(n) O(nlogn) O(n ) O(n ) O(2 ) O(n!) O(n )
n n 3 2

能承受的大致规模 任意 任意 以百万计(五六百万) 以十万计(三四十万) 以千计数(两千) 不到两百 24 10 8
2 3

常见算法 直接输出结果 二分查找、快速幂 贪心算法、扫描和遍历 带有分治思想的算法,如二分法 枚举、动态规划 动态规划 搜索 产生全排列 暴力法破解密码

O(1)叫常数时间;O(n)、O(n )、O(n )、O(n4)??叫做多项式时间;O(2n)、O(3n)??叫做指数时间。

(3) 简单的优化方法
1. 时间的简单优化方法 时间上的优化在于少做运算、做耗时短的运算等。有几个规律需要注意: ? 整型运算耗时远低于实型运算耗时。 ? 位运算速度极快。 ? 逻辑运算比四则运算快。 ? +、-、*运算都比较快(-、*比+慢一点点,可以忽略不计)。 ? /运算比+、-、*慢得多(甚至慢几十倍)。 ? 取余%和除法运算速度相当。 ? 调用函数要比直接计算慢(因为要入栈和出栈)。 这些规律我们可以从宏观上把握。事实上,究竟做了几步运算、几次赋值、变量在内存还是缓存等多数由 编译器、系统决定。但是,少做运算(尤其在循环体、递归体中)一定能很大程度节省时间。 2. 空间的简单优化方法 空间上的优化主要在于减小数组大小、降低数组维数等。常用的节省内存的方法有: 压缩储存——见 180 页“A.7 状态压缩*”。 覆盖旧数据——例如滚动数组(见 62 页“(5) 使用滚动数组”)。 要注意的是,对空间的优化即使不改变复杂度,只是改变 n 的系数也是极有意义的。空间复杂度有时对时 间也有影响,要想方设法进行优化。 3. 优化的原则 ? 尽量不让程序做已做过的事。 ? 不让程序做显然没有必要的事。 ? 不要解决无用的子问题。 ? 不要对结果进行无意义的引用。



不同资料给出的数值是不同的,不过这不要紧。在 NOIP 中,只要你的算法正确,就不会在运行时间上“打擦边球”。

15

第一单元 C++语言基础

1.10 代码编辑器
为了学习信息学,你需要一台带有 C++编译器的计算机。 为了方便编程,你还需要 IDE(集成开发环境)或具有编程特性的代码编辑器,否则你需要自己从命令行 编译程序。 常见的 IDE 和编辑器如下: 名称 DEV-C++ Code::Blocks Anjuta C/C++ IDE GUIDE Vim(Linux 自带) Eclipse**** 记事本+命令提示符 gedit+终端 Visual C++ Qt Creator 适用操作系统 Windows Linux、Windows Linux Windows、Linux Linux、Windows Windows、Linux Windows Linux Windows Windows、Linux 代码编辑功能 一般 好 好 一般 好 好 好 × 差 好 好 编译器 自备 × × × × × × × × 自备* 自备 调试功能 差 好 好 一般 好 gdb** 好 gdb gdb 好 好 单文件编译 √ √(调试除外) × √ √ g++*** × g++ g++ × ×

Emacs(Linux 自带) Linux、Windows

* 不是 GCC,而是微软自己的编译器。 ** gdb 调试功能的好坏取决于你使用的熟练程度。 *** 会用就能编译。 **** 需要安装 CDT 插件才能编写 C++的程序。

Windows 不预备 C++编译器,你需要自己下载并安装,下载地址 www.mingw.org。Linux 自备 GCC, 无需再安装编译器。

16

第二单元 基础算法

第二单元

基础算法

2.1 经典枚举问题
(1) 韩信点兵
【问题描述】正整数 x 除以 3 余 1,除以 5 余 2,除以 7 余 3。问符合条件的最小 x。 // 当x比较大时,更合适的做法是解同余式组,具体做法见136页。 int x; for (x=1; ;x++) if (x%3==1 && x%5==2 && x%7==3) break; cout<<x;

(2) 百鸡问题
【问题描述】1 只公鸡 5 文钱,1 只母鸡 3 文钱,3 只小鸡 1 文钱。如果正好花 100 文钱,可以买几只公鸡、 几只母鸡、几只小鸡? for (int x=0; x<=20; x++) for (int y=0; y<=33; y++) { // 公鸡 // 母鸡

int z=3*(100-5*x-3*y); // 小鸡 if (z>=0) cout<<x<<" "<<y<<" "<<z<<endl; }

(3) 求水仙花数
【问题描述】请输出所有的水仙花数。水仙花数是一个三位数,每一位数字的立方相加,得到的总和是它本身, 如 143=13+43+33。 for (int i=1; i<=9; i++) for (int j=0; j<=9; j++) for (int k=0; k<=9; k++) { int p=i*100+j*10+k, q=i*i*i + j*j*j + k*k*k; if (p==q) cout<<p<<endl; }

(4) 砝码称重
【问题描述】给你若干个 1g、2g、5g、10g、20g、50g 的砝码,数量分别为 a[1]、a[2]??a[6],问用 这些砝码可以称量出多少种重量(重量大于 0,小于等于 1000)。 int count=0, weight[1001], a[7]; memset(weight, 0, sizeof(weight)); for (int x1=0; x1<=a[1]; x1++) 17

第二单元 基础算法 for (int x2=0; x2<=a[2]; x2++) for (int x3=0; x3<=a[3]; x3++) for (int x4=0; x4<=a[4]; x4++) for (int x5=0; x5<=a[5]; x5++) for (int x6=0; x6<=a[6]; x6++) { int w=1*x1+2*x2+5*x3+10*x4+20*x5+50*x6; weight[w]++; } for (int i=1; i<=1000; i++) if (weight[i]>0) count++; cout<<count; 上面的代码看起来似乎很“笨拙”,但实际上它已经能顺利地解决问题了。

2.2 火柴棒等式①
【问题简述】给你 n(n?24)根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的 A、B、C 是 用火柴棍拼出的整数(若该数非零,则最高位不能是 0),数字的形状和电子表上的一样。 注意: 1. 加号与等号各自需要两根火柴棍。 2. 如果 A≠B,则 A+B=C 与 B+A=C 视为不同的等式(A,B,C?0) 。 3. n 根火柴棍必须全部用上。 【分析】 直接枚举 A 和 B(事实证明只到 3 位数) 。为了加快速度,事先把 222 以内各个数所用的火柴数算出来。 #include <iostream> using namespace std; int matches[223], n; void getmatches(); int count=0; int main() { getmatches(); cin>>n; for (int i=0;i<=111;i++) for (int j=0;j<=111;j++) { int k=i+j; if(matches[i]+matches[j]+matches[k]+4==n) count++; } cout<<count;


// 把火柴棍事先算好

题目来源:NOIP2008 第二题

18

第二单元 基础算法 return 0; } void getmatches() { matches[0]=6; matches[1]=2; matches[2]=5; ?? matches[222]=15; } // 事先编一个程序来产生这一部分代码。

2.3 梵塔问题
【问题描述】已知有三根针分别用 1、2、3 表示。在一号针中从小到大放 n 个盘子,现要求把所有的盘子从 1 针全部移到 3 针。移动规则是:使用 2 针作为过渡针,每次只移动一块盘子,且每根针上不能出现大盘压小盘, 找出移动次数最小的方案。 【分析】 这是一个经典的递归问题。 递归的思路:如果想把 n 个盘子放到 3 针上,就应该先把 n-1 个盘子放到 2 针上。然后把 1 针最底部的盘 子移动到 3 针,再把 2 针上的 n-1 个盘子移动到 3 针上。 void move(int n, int a, int b, int c) // a是盘子来源,b是暂存区、c是目标 { if (n==1) cout<<a<<"->"<<c<<endl; else { move(n-1,a,c,b); cout<<a<<"->"<<c<<endl; move(n-1,b,a,c); } } 调用:move(n,1,2,3); 时间复杂度:O(2n)。n 层梵塔至少要移动 2n-1 步。 // 只有一根针时直接移动

// 先把n-1个盘子移动到#2上 // 把n-1个盘子移动到#3上

2.4 斐波那契数列
斐波那契数列为 1,1,2,3,5,8,??
?1 很明显,斐波那契数的递推公式是 f(n)=? ?f(n-2)+f(n-1)

(n?2) (n>2)

(1) 递归
int f(int n) { if (n<=2) return 1; else 19

第二单元 基础算法 return f(n-2)+f(n-1); }

(2) 记忆化搜索
当 n 很大时,递归的运行速度会明显变慢。根本原因在于递归算法进行了大量的重复运算。所以可以开一 个数组,记录每个被计算过的函数值。每次调用 f 时,如果函数值被计算过,就直接调用计算好的结果。 int F[MAX] = {0}; // 初始化为0表明没有计算过 int f(int n) { if (F[n]!=0) return F[n]; if (n<=2) return F[n]=1; else return F[n]=f(n-2)+f(n-1); } // 直接调用记录的值

// 计算,同时记录计算结果

(3) for 循环
尽管记忆化快了很多,但仍然不是最好的。本问题递推顺序明显,用一个 for 循环就可以解决问题了。 int t1, t2, r; // int f[MAX] = {0, 1, 1}; t1=t2=r=1; for (int i=3; i<=n; i++) { r=t1+t2; // f[i]=f[i-2]+f[i-1]; t1=t2, t2=r; } // cout<<r; // 使用f后这一行代码就没有意义了。 // cout<<f[n];

2.5 常见的递推关系!
1. 前序和:设 Si 表示数列中首项①到第 i 项的和。 ? Si 的递推公式:Si=Si-1+ai ? 第 i 项到第 j 项中所有元素的和:S=Sj-Si-1 2. 等差数列 ? 递推公式:设首项为 a0,公差为 d,则 an=an-1+d ? 通项公式②:an=a0+nd ? 1 1 前 n 项和:Sn=2(a0+an)(n+1)=(n+1)a0+2dn(n+1)

3. 等比数列 ? 递推公式:设首项为 a0,公比为 q,则 an=qan-1 ? 通项公式:an=a0qn ? a0(1-qn+1) 前 n 项和:Sn= 1-q

4. 斐波那契(Fibonacci)数列

① ②

在本节若无特殊说明,n 都是从 0 开始的,当然“n 条直线”、“n 个物品”是例外。 这里的通项公式、求和公式和高中数学的略有不同,原因是首项的下标不同。

20

第二单元 基础算法 ? ? ? ?
?1 递推公式:fn=? ?fn-1+fn-2

n=0或n=1 n?2
n+1? ?1- 5? ? ? 2 ? ?

前 n 项和:Sn=fn+2-1 5??1+ 5? 通项公式(不能用于编程!):fn= 5 ? 2 ? ??
n+1



实例: ① 楼梯有 n 阶台阶,上楼可以一步上 1 阶,也可以一步上 2 阶,计算共有多少种不同的走法。 ② 有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问 n 个月后共有多少对兔子? ③ 有 n*2 的一个长方形方格,用一个 1*2 的骨牌铺满方格。求铺法总数。 5. 第二类 Stirling 数 ? s(n,k)表示含 n 个元素的集合划分为 k 个集合的情况数。 ? 递推公式:s(n,k)=s(n-1,k-1)+k· s(n-1,k),1?k<n 6. 错位排列 ? 示例:在书架上放有编号为 1,2,?,n 的 n 本书。现将 n 本书全部取下然后再放回去,当放回去时 要求每本书都不能放在原来的位置上。求满足以上条件的放法共有多少种? ? 错位排列数列为 0,1,2,9,44,265,? ?

? ?0 第一种递推公式:dn=?1 ?(n-1)(dn-2+dn-1) ?
第二种递推公式:dn=?
?0
n-2 ?ndn-1+(-1)

n= 1 n= 2 n? 3

? ?

n=1 n?2

1 1 1 1 1 1 通项公式:dn=n!?0!-1!+2!-3!+4!-?+(-1)n ? n!? ?

7. 分平面的最大区域数 ? n 条直线分平面的最大区域数的序列为:2,4,7,11,? 递推公式:fn=fn-1+n 通项公式:fn=n(n+1)/2+1 ? n 条折线分平面的最大区域数的序列为:2,7,16,29,? 递推公式:fn=fn-1+4n-3 通项公式:fn=(n-1)(2n-1)+2n ? n 条封闭曲线(如一般位置上的圆)分平面的最大区域数的序列为:2,4,8,14,? 递推公式:fn=fn-1+2(n-1) 通项公式:fn=n2-n+2 8. 组合数 ? ? ? n(n-1)(n-2)??(n-m+1) n! Am n 通项公式:Cm = = = n m! m! m!(n-m)!
m-1 m 第一种递推公式:Cm n =C n-1 +Cn-1 n (边界条件C0 n =Cn=1)

n-m+1 m-1 第二种递推公式:Cm C n (边界条件C0 n= n =1,必须先乘后除) m n n- m 优化:m>2时,可利用Cm n =C n 来减少计算次数。

9. 卡塔兰(Catalan)数列 ? 序列:1,2,5,14,42,132,429,1430,4862,16796? ? ?
n C2 n 通项公式:hn= n+1

?1 第一种递推公式(基于公式意义):hn=? ?h1hn-1+h2hn-2+...+hn-1h1

n= 1 n? 2 21

第二单元 基础算法 ? ? 1 ? ? 第二种递推公式(基于组合数性质):hn=?2(2n-1) h- ? n+1 n 1 ? n=1 n?2

实例: ① 有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票,另外 n 人只有 10 元钞票, 剧院无其它钞票, 问有多少中方法使得只要有 10 元的人买票, 售票处就有 5 元的钞票找零? ② 一位大城市的律师在她住所以北 n 个街区和以东 n 个街区处工作。每天她走 2n 个街区去上班。如 果他从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路? ③ 在圆上选择 2n 个点,将这些点成对连接起来使得所得到的 n 条线段不相交的方法数? ④ n 个结点可构造多少个不同的二叉树? ⑤ 一个栈(无穷大)的进栈序列为 1,2,3,?n,有多少个不同的出栈序列? ⑥ 将一个凸多边形区域分成三角形区域的方法数? ⑦ 一个乘法算式 P=a1a2a3?an, 在保证表达式合法的前提下 (某个数不会被括号括两次, 如 “((a))” 是错误的),有多少种添加括号的方法?

2.6 选择客栈①
【问题描述】 丽江河边有 n 家(2?n?200,000)很有特色的客栈,客栈按照其位置顺序从 1 到 n 编号。每家客栈都按 照某一种色调进行装饰(总共 k 种,用整数 0~k-1 表示,且 0<k?50),且每家客栈都设有一家咖啡店,每 家咖啡店均有各自的最低消费。 两位游客一起去丽江旅游,他们喜欢相同的色调,又想尝试两个不同的客栈,因此决定分别住在色调相同 的两家客栈中。晚上,他们打算选择一家咖啡店喝咖啡,要求咖啡店位于两人住的两家客栈之间(包括他们住 的客栈),且咖啡店的最低消费不超过 p(0?p,最低消费?100)。 他们想知道总共有多少种选择住宿的方案,保证晚上可以找到一家最低消费不超过 p 元的咖啡店小聚。 【分析】 首先考虑 30%(n?100)的数据。很明显,本题需要用枚举法解决。 枚举法的思路很明显:枚举区间[i, j](i≠j,且 i、j 色调相同) ,再判断区间内是否有最低消费不超过 p 3 的咖啡店。时间复杂度为 O(n )。 现在开始优化算法。可以看到,判断区间内咖啡店的时间为 O(n),有减少的余地。令 c[i]表示[1, i]之 间最低消费不超过 p 的咖啡店个数②,那么可以看出, 如果 c[j]-c[i]>0,说明 i、j 之间有符合要求的咖啡店。 这样判断区间的时间就降到了 O(1)。 有这一步做基础,为了使思路清晰,就可以把不同颜色的客栈分开了。 在处理 j 时,我们要统计 1~j-1 与 j 的解的个数。处理 j+1 时又要处理 1~j-1,造成了重复计算。 设 sum[j]为[1, j]到[i, j]中解的个数。 如果 j+1 无法消费, 那么由于 j 的存在, 有 sum[j+1]=sum[j]; 如果 j+1 可以消费,那么 j+1 可以和 1 到 j 中任何一个客栈组合,那么 sum[j+1]=j。 最后将每种颜色的所有 sum 相加,就可以在 O(n)的时间内得出答案了。 #include <iostream> #include <cstring> using namespace std; int n,k,p; int c[51][200001], top[51]; long long total=0;

① ②

题目来源:NOIP2011 day1 第二题 事实上不是咖啡店个数。如果 i、j 并列出现“√×”的情况,那么 c[j]-c[i]也应该大于 0。

22

第二单元 基础算法 int main() { memset(top,-1,sizeof(top)); memset(c,0,sizeof(c)); ios::sync_with_stdio(false); cin>>n>>k>>p; int cnt=0; bool P=false; for (int i=0; i<n; i++) { int x,y; cin>>x>>y; int t=++top[x]; if (y<=p || P) cnt++; c[x][t]=cnt; P = y<=p; } for (int color=0; color<k; color++) { int prev=c[color][0]; long long sum=0; for (int i=0; i<=top[color]; i++) { if (c[color][i]-prev>0) sum=i; total+=sum; prev=c[color][i]; } } cout<<total<<endl; return 0; }

2.7

2k 进制数①

【问题描述】 设 r 是个 2k 进制数(1?k?9) ,并满足以下条件: k (1) r 至少是个 2 位的 2 进制数。 (2) 作为 2k 进制数,除最后一位外,r 的每一位严格小于它右边相邻的一位。


题目来源:NOIP2006 第四题

23

第二单元 基础算法 (3) 将 r 转换为 2 进制数 q 后,则 q 的总位数不超过 w(k<w?30000) 。 输入 k 和 W,请满足上述条件的不同 r 的数量。 【分析】 本题不可能直接枚举——答案不超过 200 位,说明用到了高精度算法! 先不考虑 w。对于一个 m 位数来讲,m 个数字的顺序是确定的。所以只需直接从 n(n=2k-1)个数中取 n m 个数,组成 m 位数。所以符合条件的 m 位数有Cm 个。 现在考虑 w 存在的情况。这里有一个明显的事实:2k 进制数,除首位外,每一位转化为二进制后都是 k 个 二进制位。现在最大的问题就是 2k 进制数的首位。 二进制不超过 w 位的数,在 2k 进制下就是 a=[w/k]+1 位(w 能被 k 整除时,认为首位有 0 个数字) 。此 b k 时首位剩下 b=w%k 个二进制位,即最大可以取 2 -1。接下来只需针对 2 进制下位数不足 a 和恰好为 a 两种 情况分别进行枚举。

? ??C 所以,符合条件的 2 进制数个数为 f(k,w)= ? C+ C ? ?? ?
n i=2 i n k a-1 i=2 i n 2b-1 i=1

w?kn
a n-i

k<w<kn

其中 n=2k-1,a=[w/k]+1,b=w mod k。 通过排列组合,我们间接地枚举了所有符合条件的解。

2.8

Healthy Holsteins①

【问题描述】 农民约翰以他有世界上最健康的奶牛为骄傲。他知道每种饲料的各种维生素的含量,以及一头牛每天需要 最少的维生素的量。请你帮助约翰喂养这些奶牛,使得它们能够保持健康,并且消耗的饲料种类最少。 【输入格式】 第一行:一个数 V(1?V?25) ,表示维生素的种类数。 第二行:V 个整数,表示一头牛一天需要的维生素量。一个整数对应一种维生素。 第三行:一个数 G(1?G?15) ,表示饲料的种类数。 第四行:G 个整数,表示每种饲料的各种维生素的含量。 【输出格式】 输出共一行。第一个数是需要的最少的饲料种类数。从第二个数开始,输出所需的饲料种类序号。请输出 字典序最小的解。 【分析】 本题最多只有 15 种饲料。如果尝试所有取法,也只有 215=32768 种状态,因此完全可以枚举所有方案。 考虑一种饲料,它要么用来喂牛,要么扔到一边去。用来喂牛可以用“1”表示,放到一边用“0”表示。 于是,G 种饲料的状态可以转化成一个 G 位的二进制数。这样,枚举 0 到 2G-1 的数,就枚举了所有状态。 当然这只是一种思路。如果不能熟练使用位运算,这种做法的编程复杂度会比 DFS 高很多。 【代码】 #include <iostream> using namespace std; int v, req[26];


题目来源:USACO Training Gateway

24

第二单元 基础算法 int g, vitamin[16][26]; int Min=100, minstat=0; int count(int stat) { int r=0; while (stat) { r+=stat & 1; stat>>=1; } return r; } // Min表示需要最少饲料数,minstat表示目前的最优状态 // 统计stat中“1”的个数

int main() { cin>>v; for (int i=1; i<=v; i++) cin>>req[i]; cin>>g; for (int i=1; i<=g; i++) for (int j=1; j<=v; j++) cin>>vitamin[i][j]; for (int stat=0; stat < (1<<g); stat++) { int r[26] = {0}; // 尝试所有组合

for (int i=1; i<=g; i++) // 计算组合中每种维生素的量 if (stat & (1<<(i-1))) for (int j=1; j<=v; j++) r[j]+=vitamin[i][j]; bool no=false; for (int i=1; i<=v; i++) if (r[i]<req[i]) no=true; // 判断维生素是否达标 if (no) continue; int c=count(stat); if (c<Min && c>0) Min=c, minstat=stat; } cout<<Min<<" "; for (int i=1; i<=g; i++) if (minstat & (1<<(i-1))) cout<<i<<" "; return 0; }

2.9 小结
本单元总结了三种基本算法:枚举、递归和递推。 25

第二单元 基础算法 1. 枚举 所谓枚举,就是将所有的可能一一遍历出来,在遍历中逐个检查答案的正确性,从而确定最终结果。因此, 枚举法适合解决“是否有解”和“有多少个解”的问题。搜索的本质就是枚举。 应用枚举法搜索答案之前,要确定枚举的对象和状态的表示方式。 常见的枚举方法有三种:第一种是使用 for 循环,第二种是利用排列组合,第三种是顺序化(比如把状态 与二进制数对应)。 由于枚举法产生了大量的无用解,所以规模稍大的时候要进行优化。优化时要从两方面入手,一是减少状 态量,二是降低单个状态的考察代价。优化过程要从以下几个方面考虑:枚举对象的选取、枚举方法的确定、 采用局部枚举或引进其他算法。 (在这里附上次短路的求法:先求出最短路,枚举最短路上的每一条边,对于每一条边都删除然后重新求 最短路。几个新的“最短路”的最小值就是次短路。) 2. 递归 递归,即自己调用自己。递归法将较复杂的大问题分解成较简单的小问题,然后一层一层地得出最终答案。 递归是实现许多重要算法的基础。深度优先搜索、记忆化搜索、分治算法和输出动态规划的中间过程等都 需要用递归实现。 有一些数据结构也是递归定义的,如二叉树。使用此类数据结构时,也要递归地思考问题。 写递归要从两方面入手:分解问题的方式、边界条件。 注意,没有边界条件会引发无限递归,从而导致程序崩溃! 3. 递推 递推指利用数列中前面一项或几项,通过递推公式来求出当前项的解。 递推与递归不同。一般情况下,递推用循环语句完成,而递归必须定义函数。递推也可以转化为递归,即 记忆化搜索,这常用于递推顺序不明显的情况。 解决递推问题要从以下几方面入手:状态表示、递推关系、边界条件。 按照计算顺序,递推可以分为顺退和逆推。对于某些问题,递推顺序甚至直接影响编码的复杂度。 动态规划必须使用递推或记忆化搜索来解决。动态规划的状态转移方程一定是递推式。但动态规划与纯粹 的递推不同,前者有明显的阶段,而后者的数学性更强。 我们已经在数学课上学习了数列的通项公式和递推公式。高中数学喜欢通项公式,而信息学更喜欢递推公 式。下次遇到类似问题,就去寻找递推式吧。 4. 递归和递推的比较 递归 1. 问题本身是递归定义的,或者问题所涉及 到的数据结构是递归定义的, 或者是问题的解 决方法是递归形式的。 2. 需要利用分治思想解决的问题。 3. 回溯、深度优先搜索 4. 输出动态规划的中间过程。 结构清晰、可读性强 目的性强 在函数中调用自己 问题的性质不同,改写的方法也不同。 ① 有的问题可以根据程序本身的特点,使用 栈来模拟递归调用。 ② 有的问题可以改写成递推或迭代算法。 递推

适合解决 的问题

1. 能够用递推式计算的数学题。 2. 动态规划(必须使用递推或记忆化搜索)

特点 编码方式

速度较快、比较灵活 思路不易想到 迭代(使用 for 循环等)

替代方法

在拓扑关系不明显时,可以采用记忆化搜索。

26

第三单元 搜索

第三单元
3.1

搜索

N 皇后问题

【问题描述】在国际象棋中,皇后可以攻击与她在同一条水平线、垂直线和对角线的棋子。现在有一张 N×N 的国际象棋棋盘,在上面放置 N 个皇后。有多少种使皇后不能互相攻击的方案?(N?13)

(1) 深度优先搜索(DFS)
逐列(行)搜索。每测试一个位置,就检查它是否与其他皇后冲突,如果冲突,回溯①。 每放置一个皇后,就要记录——所在列、 “/”对角线和“\”对角线都不能放皇后了。 #include <iostream> #include <cstring> using namespace std; bool column[20],cross1[50],cross2[50]; int pos[20]; int n, sum=0; void dfs(int row) { if (row==n) { sum++; return; } for (int i=0;i<n;i++) if (!(column[i] || cross1[row-i+n] || cross2[row+i])) // 判断是否可以放置皇后 { // 对皇后已经控制的列和对角线做标记 column[i]=cross1[row-i+n]=cross2[row+i]=true; pos[row]=i; dfs(row+1); // 解除标记,这样才能在新位置上放置皇后。 column[i]=cross1[row-i+n]=cross2[row+i]=false; } } int main() { cin>>n; memset(column,0,sizeof(column)); memset(cross1,0,sizeof(cross1));


一般情况下,深度优先搜索要使用回溯法。

27

第三单元 搜索 memset(cross2,0,sizeof(cross2)); dfs(0); cout<<sum<<endl; return 0; }

(2) 状态压缩*
把状态放在一个 4 字节的 int 整型变量中,并且使用位运算——这样,速度会比朴素算法的快很多。 #include <iostream> using namespace std; // sum用来记录皇后放置成功的不同布局数;upperlim用来标记所有列都已经放置好了皇后。 int n, sum = 0, upperlim = 1; // 搜索算法,从最右边的列开始。 void test(long row, long ld, long rd) { if (row != upperlim) { /* row,ld,rd进行“或”运算,求得所有可以放置皇后的列,对应位为0, 然后再取反后“与”上全1的数,来求得当前所有可以放置皇后的位置,对应列改为1。 也就是求取当前哪些列可以放置皇后。 */ long pos = upperlim & ~(row | ld | rd); while (pos) // 0 -- 皇后没有地方可放,回溯。 { /* 拷贝pos最右边为1的bit,其余bit置0。 也就是取得可以放皇后的最右边的列。 */ long p = pos & -pos; /* 将pos最右边为1的bit清零。 也就是为获取下一次的最右可用列使用做准备, 程序将来会回溯到这个位置继续试探。 */ pos -= p; /* row + p,将当前列置1,表示记录这次皇后放置的列。 (ld + p) << 1,标记当前皇后左边相邻的列不允许下一个皇后放置。 (ld + p) >> 1,标记当前皇后右边相邻的列不允许下一个皇后放置。 */ 28

第三单元 搜索 /* 此处的移位操作实际上是记录对角线上的限制,只是因为问题都化归 到一行网格上来解决,所以表示为列的限制就可以了。显然,随着移位 在每次选择列之前进行,原来N×N网格中某个已放置的皇后针对其对角线 上产生的限制都被记录下来了。 */ test(row + p, (ld + p) << 1, (rd + p) >> 1); } } else sum++; } int main() { cin>>n; // N个皇后只需N位存储,N列中某列有皇后则对应bit置1。 upperlim = (upperlim << n) - 1; test(0, 0, 0); cout<<sum; return 0; } // row的所有位都为1,即找到了一个成功的布局,回溯。

3.2 走迷宫
【问题描述】从文件 map.txt 中读入一个 m 行 n 列的迷宫,其中 0 代表可以通过,1 代表不可通过(墙)。 请给出一条从(1,1)出发到(m,n)的路径。如果不能到达,输出“Failed”。例如: 10 8 0001000000 0101011110 0111000100 0001010111 0100010001 0111011100 1101010101 0000010000

(1) 预处理
为了防止在搜索时发生下标越界,我们需要做一个小处理:在迷宫的外圈圈上一层围墙,即 111111111111 100010000001 101010111101 101110001001 100010101111 29

第三单元 搜索 101000100011 101110111001 111010101011 100000100001 111111111111 以下是一些定义: char map[110][110]; bool visited[110][110]; point prev[110][110]; struct point {int r,c;}; int n,m;

// 先行后列。 // 记录路径的方法:从A结点扩展到B结点时,将prev[B]设为A。

void flag(int r, int c) // 追踪结点,在经过的路径上画箭头。 { point &t=prev[r][c]; if (!(r==1&&c==1)) flag(t.r,t.c); if (t.r==r && t.c<c) map[r][c]='v'; else if (t.r==r && t.c>c) map[r][c]='^'; else if (t.r>r && t.c==c) map[r][c]='<'; else if (t.r<r && t.c==c) map[r][c]='>'; }

(2) 深度优先搜索(DFS)
搜索方法叫做“一条道走到黑”。 #define isok(a,b) (Map[a][b]!='1')&&(visited[a][b]==false) #define expand(a,b) {prev[a][b]=p;DFS(a,b);} void DFS(int r,int c) { if (r==m&&c==n) { flag(m,n); for (int i=0;i<=m+1;i++) cout<<map[i]<<endl; exit(0); } visited[r][c]=true; point p; p.r=r; p.c=c; if (isok(r-1,c)) expand(r-1,c) if (isok(r,c-1)) expand(r,c-1) if (isok(r+1,c)) expand(r+1,c) if (isok(r,c+1)) expand(r,c+1) } // 该语句会使程序立即退出。

30

第三单元 搜索

(3) 广度优先搜索(BFS)
搜索过程像墨水的扩散。 queue<point> q; #define isok(a,b) (map[a][b]!='1')&&(visited[a][b]==false) #define expand(a,b) {prev[a][b]=p;t.r=a;t.c=b;q.push(t);} void BFS() { point t,p; p.r=p.c=1; q.push(p); while (!q.empty()) { p=q.front(); q.pop(); int &r=p.r, &c=p.c; visited[r][c]=true; if (r==m&&c==n) { flag(m,n); for (int i=0;i<=m+1;i++) cout<<map[i]<<endl; return; } if if if if (isok(r-1,c)) (isok(r,c-1)) (isok(r+1,c)) (isok(r,c+1)) expand(r-1,c) expand(r,c-1) expand(r+1,c) expand(r,c+1) // 判断能否扩展 // 扩展结点

} cout<<"No Way."<<endl; } 正常形态的迷宫由于道路“狭窄”,能扩展的结点很少,所以 DFS、BFS、双向搜索和启发式搜索都能承 受。但是,如果换成畸形迷宫(比如 100×100 的“0”),DFS 和 BFS 将无法忍受。

3.3

8 数码问题
1 → 4 7 2 5 8 3 6

【问题描述】用最少的步数实现(空格用 0 表示): 2 8 3 1 7 6 4 5

(1) BFS①
typedef int state[9];


以下代码直接摘自刘汝佳的《算法竞赛入门经典》。

31

第三单元 搜索 const int N=1000000; state st[N],goal; int dist[N],parent[N]; const int dx[]={-1,1,0,0}, dy[]={0,0,-1,1}; void print(int p) { if (parent[p]!=-1) print(parent[p]); // 输出st[p] state &s=st[p]; cout<<s[0]<<" "<<s[1]<<" "<<s[2]<<endl; cout<<s[3]<<" "<<s[4]<<" "<<s[5]<<endl; cout<<s[6]<<" "<<s[7]<<" "<<s[8]<<endl; cout<<endl; } int BFS() { // 返回目标状态在st[]中的下标

init_lookup_table(); // 初始化查找表(判重用) int front=1, rear=2; parent[front]=-1; while (front<rear) { state &s=st[front]; if (memcmp(goal, s, sizeof(s))==0) return front; int z; for (z=0; z<9; z++) if (s[z]==0) break; // 找“零” int x=z/3, y=z%3; // “0”的行列编号 for (int d=0; d<4; d++) { int newx=x+dx[d]; int newy=y+dy[d]; int newz=newx*3+newy; if (newx>=0 && newx<3 && newy>=0 && newy<3) { state &t=st[rear]; memcpy(&t, &s, sizeof(s)); t[newz]=s[z]; t[z]=s[newz]; dist[rear]=dist[front]+1; parent[rear]=front; if (try_to_insert(rear)) rear++; } } front++; } 32 // 扩展结点

第三单元 搜索 return 0; }

(2) 顺序化*
下面的代码把 0~8 的全排列和 0~362879(9!-1)的整数一一对应起来。 bool visited[362880]; int fact[9]; void init_lookup_table() { fact[0]=1; for (int i=1;i<9;i++) fact[i]=fact[i-1]*i; } bool try_to_insert(int s) { int code=0; // 把st[s]映射到整数code state &p = st[s]; for (int i=0; i<9; i++) { int cnt=0; for (int j=i+1; j<9; j++) if (p[j]<p[i]) code+=fact[8-i]*cnt; } if (visited[code]) return false; else return visited[code]=true; }

(3) 使用哈希表判重
上面的编码法时间效率很高,但是毕竟不是通用的方法。如果结点数非常大,编码也是无法承受的。 const int MAXSIZE = 1000003; int head[MAXSIZE], next[MAXSIZE]; void init_lookup_table() {memset(head,0,sizeof(head));} int h(state &s) { // 散列函数:把每个格子里数连接成一个九位数,并将它除以MAXSIZE的余数作为哈希函数值。 int v=0; for (int i=0; i<9; i++) v=v*10+s[i]; return v%MAXSIZE; } bool try_to_insert(int s) { int h=hash(st[s]); int u=head[h]; while (u) 33

第三单元 搜索 { if (memcmp(st[u],st[s],sizeof(st[s]))==0) return false; u=next[u]; } next[s]=head[h]; head[h]=s; return true; }

3.4 埃及分数
【问题描述】在古埃及,人们使用单位分数的和(形如 1/a,其中 a 是自然数)表示一切有理数。 如:2/3=1/2+1/6,但不允许 2/3=1/3+1/3,因为加数中有相同的。 对于一个分数 a/b,表示方法有很多种,但是哪种最好呢?首先,加数少的比加数多的好;其次,加数个 数相同的,最小的分数越大越好。如: 19/45=1/3+1/12+1/180 19/45=1/3+1/15+1/45 19/45=1/3+1/18+1/30 19/45=1/4+1/6+1/180 19/45=1/5+1/6+1/18 最好的是最后一种,因为 1/18 比 1/180,1/45,1/30,1/180 都大。 给出 a,b(0<a<b<1000),编程计算最好的表达方式(输入 a,b,按从小到大顺序输出所有分母)。 【分析】 1. 迭代加深搜索:本题由于搜索层数不明,用深搜极易陷入死胡同,用广搜空间又吃不消,这时迭代加深搜 索就成了考虑的对象。 1 a 1 1 1 2. 有序化:枚举的对象为分母, = + + +?+ ,输出又要求有序,所以,不妨设 a1<a2<?<an。 b a1 a2 a3 an 3. 定界法:设限定的搜索层数为 depth ,当前搜到第 k 层,当前正要枚举分母 ak ,还需枚举总和为 x/y 的分数。answer[d]表示当前最优解中的第 d 个分母,如果还没有得到解则表示正无穷。则必然有: max{y/x,ak-1}+1?ak?min{(D-C+1)*y/x,Maxlongint①/x,answer[depth]-1} 枚举的初值容易得出,但终值的确定则要用到我们一开始对分母有序性的假设了。值得注意的是,直接限 界避免了搜索过程中屡次使用可行性剪枝,在一定程度上可以提高了程序的运行速度。 #include <iostream> #include <cstring> #include <algorithm> using namespace std; const int MAXDEPTH=10, maxlongint=2147483647; int depth; bool found; int answer[MAXDEPTH], d[MAXDEPTH]; int gcd(int a, int b) { int t=a%b;


maxlongint 是 Pascal 语言中的常数,它等于 2147483647L,即 int 类型可以取到的最大值。

34

第三单元 搜索 while(t) { a=b; b=t; t=a%b; } return b; } void search(int a, int b, int k) { int i,m,s,t; if (k==depth+1) return; else if (b%a==0 && b/a>d[k-1]) { d[k]=b/a; if (!found || d[k]<answer[k]) memcpy(answer,d,sizeof(d)); found = true; return; } // 确定上下界 s = max(b/a, d[k-1]) + 1; t=(depth-k+1)*b/a; t=min(t, maxlongint/b); if (found) t=min(t,answer[depth]-1); for (i=s; i<=t; i++) { // 从a/b中减去那个埃及分数 d[k]=i; m=gcd(i*a-b, b*i); search((i*a-b)/m, b*i/m, k+1); } } int main() { int a,b; int i; found = false; d[0] = 1; cin>>a>>b; 35 // 更新最优解

第三单元 搜索 for (depth=1; depth<=MAXDEPTH; depth++) { search(a,b,1); if (found) { for(i=1;i<=depth;i++) cout<<answer[i]<<" "; cout<<endl; break; } } return 0; }

3.5

Mayan 游戏①

由于题目很长,这里不再描述。大家可以“百度一下” ,或在百度文库中查 NOIP2011 试题。 【分析】 问题的性质加上 3s 的运行时间告诉我们:这个世界需要暴力。 一个块向右交换,与它右边的块向左交换是等价的,但前者的字典序更小,所以不必考虑后者。 此外,如果一种颜色的数量在 1~2 之间,就可以直接剪枝。 与其说本题在考察搜索,不如说本题在考察选手的编程习惯和心理素质。很多人没有清晰明确的思路和良 好的编码习惯,结果“投降” ,输出了“-1” ,或者写了数 KB 代码却没有得到多少分。所以大家要养成好的编 程习惯,包括变量的命名、代码缩进、注释等,同时要发扬敢于使用暴力的精神。 【代码】 下面代码没有任何剪枝,但已经测试通过了。 #include <iostream> #include <cstring> using namespace std; inline void swap(int &a, int &b) { int t=a; a=b; b=t; } // 程序中使用横向棋盘,5行7列,水平移动变竖直移动,竖直移动变水平运动。 int n; int map[7][6][9]; int a[6],b[6],c[6]; // 方块下落 void fall(int depth) { for (int i=1; i<=5; i++) { int *m=map[depth][i];


// 每一步的变化,a是棋盘倒放之后的行,b是列

题目来源:NOIP2011 day1 第三题。

36

第三单元 搜索 // 在第i行中,寻找第一个0,然后再寻找非0,接下来移动。不过不一定正确?? int j=1,k=0; while (m[j]) j++; if (j==8) continue; k=j+1; while (m[k]==0 && k<8) k++; while (k<8) swap(m[j++],m[k++]); } } // 检查是否可以消除方块。如果可以,就消除方块。 bool mark[6][8]; // 消除方块时用 bool check(int depth) { bool changed=false; memset(mark,0,sizeof(mark)); // 检查是否可以消除 // 水平方向 for (int i=1; i<=5; i++) for (int delta=7; delta>=3; delta--) // 连通的方块数 for (int j=1; j<=8-delta; j++) { int a=map[depth][i][j]; for (int k=j+1; k<=j+delta-1; k++) if (map[depth][i][k]!=a) { a=0; break; } if (a) for (int k=j; k<=j+delta-1; k++) mark[i][k]=true; } // 竖直方向 for (int j=1; j<=7; j++) for (int delta=5; delta>=3; delta--) for (int i=1; i<=6-delta; i++) { int a=map[depth][i][j]; for (int k=i+1; k<=i+delta-1; k++) if (map[depth][k][j]!=a) { a=0; 37

第三单元 搜索 break; } if (a) for (int k=i; k<=i+delta-1; k++) mark[k][j]=true; } // 消除 for (int i=1; i<=5; i++) for (int j=1; j<=7; j++) if (mark[i][j]) map[depth][i][j]=0, changed=true; return changed; } // 进行搜索,如果有解则返回true,否则返回false。 bool DFS(int depth) { if (depth>n) { for (int i=1; i<=5; i++) if (map[n+1][i][1]) return false; return true; } for (int i=1; i<=5; i++) for (int j=1; j<=7; j++) { /* 移动一种方块。分四种情况: ① 方块本身就是0,那么直接跳过; ② 在左边界,只能向右移动; ③ 在右边界,只能向左移动。如果左边有方块,那么可以忽略这一步, 因为那个方块右移和这个方块左移效果相同,但字典序更小。 也就是说,在右边界时,如果左边为空,则向左移动,否则不移动。 ④ 不在边界,如果左边为空,就既向左又向右(特殊考虑,因为要多一段代码); 如果左边不为空,那么不管右边是什么都向右移动。 */ if (map[depth][i][j]==0) continue; a[depth]=i; b[depth]=j; int &dir=c[depth]; if (i<5) dir=1; else if (i==5 && map[depth][4][j]==0) dir=-1; else 38 // 移动方向 // 第②种情况+第④种情况的第一部分 // 第③种情况

第三单元 搜索 continue; memcpy(map[depth+1], map[depth], sizeof(map[depth])); swap(map[depth+1][i][j], map[depth+1][i+dir][j]); // 下落与消除方块 do { fall(depth+1); } while (check(depth+1)); // 继续搜索 if (DFS(depth+1)) return true; if (i>1 && i<5 && map[depth][i-1][j]==0) // 第④种情况的第二部分 { a[depth]=i; b[depth]=j; dir=-1; memcpy(map[depth+1], map[depth], sizeof(map[depth])); swap(map[depth+1][i][j], map[depth+1][i+dir][j]); // 和上面一样 do { fall(depth+1); } while (check(depth+1)); if (DFS(depth+1)) return true; } } return false; } int main() { memset(map,0,sizeof(map)); cin>>n; for (int i=1; i<=5; i++) { int temp, j=1; do { cin>>temp; map[1][i][j++]=temp; } while (temp); } 39

第三单元 搜索 if (DFS(1)) for (int i=1; i<=n; i++) cout<<(a[i]-1)<<" "<<(b[i]-1)<<" "<<c[i]<<endl; else cout<<"-1"<<endl; return 0; }

3.6 预处理和优化
(1) 预处理
1. 数学性分析,找出一定规律,减少搜索范围。 【问题描述】在 IOI98①的节日宴会上,我们有 N(10?N?100)盏彩色灯,他们分别从 1 到 N 被标上号码。 这些灯都连接到四个按钮。 按钮 1:当按下此按钮,将改变所有的灯,使本来亮着的灯熄灭,本来是关着的灯被点亮。 按钮 2:当按下此按钮,将改变所有奇数号的灯。 按钮 3:当按下此按钮,将改变所有偶数号的灯。 按钮 4:当按下此按钮,将改变所有序号是 3k+1(k?0)的灯,例如 1,4,7?? 此外一个计数器 C 记录按钮被按下的次数。当宴会开始,所有的灯都亮着,此时计数器 C 为 0。 你将得到计数器 C(0?C?10000)上的数值和经过若干操作后所有灯的状态。写一个程序去找出所有灯 最后可能的与所给出信息相符的状态,并且没有重复。 【分析】 灯的状态多达 2100 个,似乎无法枚举。 为了找到按钮之间的联系和控制规律,我们不妨列个表说明一下( “√”表示能被按钮控制) : 1 #1 #2 #3 #4 √ √ √ √ 2 √ 3 √ √ √ √ 4 √ 5 √ √ √ √ 6 √ 7 √ √ √ 8 √ 9 √ √ √ √ 10 √ 11 √ √ √ √ 12 √ 13 √ √ √ 14 √ 15 √ √ √ √ 16 √ 17 √ √ √ √ 18 √ 19 √ √ √ 20 √ ? ? ? ? ?

我们发现,控制情况是“循环”的,每 6 个灯为一个周期。1、7、13、19??,2、8、14、20??灯的 状态是相同的。所以只需枚举前 6 个灯的状态,至于后面的灯,直接对 6 取模即可。 2. 保存一些运算结果。如记忆化搜索。 3. 优先在更小的搜索树中搜索,减少搜索量。 【问题描述】②输出 a 到 b(5?a?b?100000000)之间既是质数,又是回文数的数。 【分析】 有两种判断方法:一种是先找质数后找回文数,另一种方法是先找回文数然后找质数。 应用素数定理可以估算,100000000 以内约有 540 万个素数,所以显然不能先找质数。 即使是先找回文数,也不能全找。
① ②

这是 IOI98 的一道题,名为 Party Lamps(派对灯)。 题目名称为 Prime Palindromes(回文质数),题目来源:USACO Training Gateway。

40

第三单元 搜索 仔细分析,由于质数的末位不能是 2、4、5、6、8、0(数字 5 本身要特殊考虑) ,所以只需搜尾数为 1、 3、7、9 的回文数。 如果数学基础牢固,你还会发现,由偶数个数字组成的回文数可以被 11 整除。于是搜索树又小了许多。 4. 有序化处理。 常见的做法是把输入数据排序或分类。有序化搜索往往可以简化问题,帮助分析问题的本质。

(2) 通用优化方法
1. DFS ? ? ? 2. BFS ? 用散列表来判重:为了避免重复扩展结点,可以使用散列表存储已经扩展的状态,并在扩展结点之前 进行判重。如果散列表中找到了对应的状态,就不要再入队了。对于图的遍历,判重可以很大程度地 提升速度,减少空间的浪费。 对于有些问题,布尔数组、二叉排序树等也能起到相同的作用。 双向搜索:由于代码比较复杂,这种搜索方法在竞赛时不推荐使用。 启发式搜索:如果能够构造出好的估价函数,就可以大大减少搜索量。 状态压缩 剪枝:可行性剪枝、最优化剪枝 记忆化:这种方法常用于动态规划的动态转移方程中。 状态压缩

? ? ?

(3) 剪枝
剪枝主要有两种,一种是可行性剪枝,另一种是最优化剪枝。它们都可以帮助程序不做“无用功”。 举一个可行性剪枝的例子:在 N 皇后问题中,放置第 i 个皇后时,要进行判断。如果这个皇后和已有的皇 后发生冲突,回溯。 如果不进行剪枝,那么就应该继续放置这个皇后,继续搜索。继续搜索的结果是可想而知的。 举一个最优化剪枝的例子:在解决某类最值问题时,如果搜索到一个较优的方案,可以把这个方案记录下 来。接下来再进行搜索时,每扩展一个结点,就用估价函数判断一下是否能达到已记录的最优值。如果不能, 果断剪枝。 合理的估价函数是最优化剪枝的关键。当然,解最小值问题时可以不用估价函数。

3.7 代码模板
(1) DFS(递归实现)!
void DFS(int depth) { if (depth==n) { // 深度超过范围,说明找到了一个解。

// 找到了一个解,对这个解进行处理,如:输出、解的数量加1、更新目前搜索到的最优值等 return; } // 扩展结点,如 41

第三单元 搜索 for (int i=0; i<n; i++) { // 处理结点 ? // 继续搜索 DFS(depth+1); // 部分问题需要恢复状态,如N皇后问题 ? } } 非递归版本见 93 页“(2) DFS 和栈” 。稳妥的做法是先写递归版本,如果有空闲时间和改写的可能,再 把递归版本改写成非递归版本。

(2) BFS!
BFS 占用存储空间比较大,尤其是在状态比较复杂的时候。 树的 BFS 不用判重,因为不会重复。但对于图来说,如果不判重,时间和空间会造成极大的浪费。 queue <int> q; // 存储状态 // bool try_to_insert(int state); // 结点入队前判断状态是否重复,以免重复搜索 // 使用散列表可以提高查找的效率。 // void init_lookup_table(); void BFS() { // init_lookup_table(); q.push(?); while (!q.empty()) { int s = q.front(); q.pop(); // 处理结点 if (s达到某种条件) { // 输出,或做些什么 ? return; } // 扩展状态 for (i=0;i<n;i++) { int s; // if (try_to_insert(s)) q.push(s); q.push(s); } } // 如果运行到这里,说明无解。 42 // 判重之前的初始化 // 初始状态入队

// 获取状态

第三单元 搜索 }

(3) 迭代加深搜索
void search(int depth) { if (得到了合适的解) { // 已经得到了合适的解,接下来输出或解的数量加1 return; } if (depth == 0) return; // 扩展结点,如 for (int i=0; i<n; i++) { // 处理结点 ? // 继续搜索 search(depth-1, ?); // 部分问题需要恢复状态,如N皇后问题 ? } } const int maxdepth = 10; // 限定的最大搜索深度 void IDS() { for (int i=1; i<=maxdepth; i++) search(i, ?); } // 无解 // depth表示深度

3.8 搜索题的一些调试技巧①
如果决定用 DFS 做一道题,那么: ? 如果能套用模板或经典的 DFS 模型,就直接套用。 ? 如果不能套用,就先写爆搜,并命名为#0 版本。 ? 对于每一个版本,调试正确之后,再进行剪枝,并且每次只加一个剪枝,调试正确后再继续。 ? 每次加剪枝都应该开一个新的版本,不能直接修改原版本。 如果时间来不及了,就按照从强到弱或从好写到难写的顺序来加剪枝。 ? 在动态查错之前应该进行一次静态查错。 ? 调试时, 如果出现 RE (运行时错误) 或死循环, 就在出错的状态处停止, 并检查其所有的祖先状态 (显 然这需要记下每次的决策) ,看看这些决策是否合法。


选自 Mato_No1 的博客,有改动。博客的网址为 http://www.cppblog.com/MatoNo1。

43

第三单元 搜索 ? 如果程序正常结束,但结果错误,应该从以下三个角度入手: 1. 明明有解,输出无解:可以把正解的各个决策一步一步代入,看看程序里面是在哪一步出了问题 (明明合法的决策它木有作出) ,从而方便检查; 2. 输出不合法的解:可以把形成这个不合法解的决策一步一步代入,看看是哪一步出了问题; 3. 输出合法但非最优的解:必然是某些最优性剪枝错误或者最优性判断出了问题,可以直接到这些 地方去检查,实在不行也可以把最优解代入检查。 有时也可以用分段检查的方法,即把代码中的各个过程或者片段截取下来,将几组小的输入代入,看 看执行之后,所有在该片段里改变了值的全局变量是否正确,进而发现这里的错误。 千万不要一下子输出全部的状态!这样不仅不容易查出结果,还把容易把自己绕晕。 事实上,只有在状态总数不太多,且相对关系明了、顺序整齐的时候(比如一般的 DP 等) ,可以一下 子输出全部状态来检查,否则就不能这么做。

? ?

对于 BFS,其实它比 DFS 容易调试,因为所有的状态都储存在队列里。因此,可以在状态结点中记下每个 点的前趋,然后,哪里出了问题,就直接把它的前趋状态全部输出。 另外,BFS 一般没有“剪枝”这一说(除了判重) ,且决策过程一般是比较整齐的,因此更容易调试。

3.9 小结
搜索,就要用搜索算法来产生所有可能的答案,并从中筛选出正确的答案。 搜索法常用于求可行解或可行解的个数。在竞赛中,搜索法还是“救命稻草”——大多数问题都可以使用 搜索来谋取部分分数。 搜索的方式有很多种,常见的有:枚举搜索、深度优先搜索、广度优先搜索、迭代加深搜索。 解搜索题时要从以下几方面入手:确定状态、确定结点扩展方式、选用合适的搜索方式、优化。 1. 深度优先搜索和广度优先搜索 将搜索时产生的状态组成一棵树,就成了解答树。深度优先搜索和广度优先搜索的区别在于解答树的遍历 方式。下图是一棵解答树:

深度优先搜索用逐步加层的方法搜索并且适当时回溯,遍历过程如下图所示:

广度优先搜索得名于它的实现方式:每次都先将搜索树某一层的所有结点全部访问完毕后再访问下一层, 再利用先前的那颗搜索树,广度优先搜索以如下顺序遍历: 44

第三单元 搜索

首先访问根结点,而后是搜索树第一层的所有结点,之后第二层、第三层??以此类推。 此外,在使用广度优先搜索时,应小心处理空间问题。 下面是两种搜索算法的比较: DFS 1. 2. 3. 4. 5. 比较适合回溯类搜索 参数传递、状态修改和恢复都比较方便 自顶向下地处理问题 记忆化搜索容易实现 能很快到达解答树的底端 1. 2. 3. 4. BFS 解决“最少步数”、“深度最小”问题 问题的解靠近解答树的根结点 启发式搜索在BFS中更容易实现 能立刻停止搜索

优势

缺点

1. 使用递归算法容易导致栈溢出 2. 有时不容易输出方案 3. 不易立即结束搜索

1. 空间一般比DFS大 2. 状态重复的排除有时耗时多

2. 迭代加深搜索 广度优先搜索可以用迭代加深搜索代替。迭代加深搜索实质是限定下界的深度优先搜索,即首先允许深度 优先搜索搜索 k 层搜索树,若没有发现可行解,再将 k+1 代入后再进行一次以上步骤,直到搜索到可行解。这 个“模仿广度优先搜索”搜索法比起广搜是牺牲了时间,但节约了空间。 在需要做 BFS,但没有足够的空间,时间却很充裕的情况下,可以考虑迭代加深搜索。 迭代加深搜索的时间不会超过等效 BFS 占用时间的两倍,当数据规模增大时,二者的差距还会逐渐减小, 而迭代加深搜索的空间占用和 DFS 一样小。 3. 搜索的优化 没有经过优化的搜索叫“爆搜”或“裸搜”。爆搜能承受的规模不大,原因有二:一是搜索时产生了无用 的结点,二是重复计算。 优化时从以下几方面入手:确定更合适的搜索顺序、剪枝(可行性剪枝、最优化剪枝)、降低考察和扩展 结点的代价,必要时可采用高级的搜索方法,或使用状态压缩。 此外,写搜索程序时应该先从朴素算法入手,逐步优化,以降低编程复杂度、减少不必要的失误。

45

第四单元 贪心算法

第四单元

贪心算法

以下 9 个问题都给出了相应贪心策略,但是为什么这些策略是正确的呢?请自己证明(提示:反证法) 。

4.1 装载问题
(1) 简单的装载问题
【问题描述】有 n 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]。求解将哪些物品装入背包可物品 数量最多。 【贪心策略】将物品重量从小到大进行排序,优先挑重量轻的装入背包。

(2) 部分背包问题
【问题描述】有 n 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i],价值是 v[i]。每个物体可以取 走一部分,价值和重量按比例计算。求解将哪些物品装入背包可使价值总和最大。 【贪心策略】将背包按照单价(价值/重量的比值)排序。从物美价廉(单价尽可能大)的物体开始挑起,直 到背包装满或没有物体可拿。

(3) 乘船问题
【问题描述】有 n 个人,第 i 个人的重量是 wi。每艘船的最大载重量都是 C,且最多能乘两个人。用最少的船 装尽可能多的人。 【贪心策略】让最轻的人和能与他同船的最重的人乘一条船。如果办不到,就一人一条船。

4.2 区间问题
(1) 选择不相交区间
【问题描述】数轴上有 n 个开区间(ai, bi)。选择尽量多的区间,使这些区间两两没有公共点。 【贪心策略】按 bi 从小到大的顺序排序,然后一定选择第一个区间。接下来把所有与第一个区间相交的区间排 除在外。这样在排序后再扫描一遍即可。

(2) 区间选点问题
【问题描述】数轴上有 n 个闭区间[ai, bi]。取尽量少的点,使得每个区间内都至少有一个点(不同区间内含 有的点可以是同一个)。 【贪心策略】把所有区间按 bi 从小到大排序(bi 相同时,a 从大到小排序),然后一定取第一个区间的最后一 个点。

(3) 区间覆盖问题
【问题描述】数轴上有 n 个闭区间[ai, bi]。选择尽量少的区间来覆盖指定线段[s, t]。 46

第四单元 贪心算法 【贪心策略】 1. 预处理:扔掉不能覆盖[s, t]的区间。 2. 把各区间按 a 从小到大排序。如果区间 1 的起点不是 s,无解,否则选择起点在 s 的最长区间。 3. 选择此区间[ai, bi]后,问题转化了覆盖[bi, t],于是返回①,直到[s, t]被完全覆盖为止。

4.3 删数问题
【问题描述】给出一个 N 位的十进制高精度数,要求从中删掉 S 个数字(其余数字相对位置不得改变),使剩 余数字组成的数最小。 【贪心策略】 1. 每次找出最靠前的这样的一对数字——两个数字紧邻,且前面的数字大于后面的数字。 删除这对数字中靠前的一个。 2. 重复步骤 1,直至删去了 S 个数字或找不到这样的一对数。 3. 若还未删够 S 个数字,则舍弃末尾的部分数字,取前 N-S 个。

4.4 工序问题
【问题描述】n 件物品,每件需依次在 A、B 机床上加工。已知第 i 件在 A、B 所需加工时间分别为 Ai、Bi,设 计一加工顺序,使所需加工总时间最短。 【贪心策略】 1. 设置集合 F、M、S:先加工 F 中的,再加工 M 中的,最后加工 S 中的。 2. 对第 i 件,若 Ai>Bi,则归入 S;若 Ai=Bi,则归入 M。否则归入 F(“拉开时间差”)。 3. 对 F 中的元素按 Ai 从小到大排列,S 中的按 Bi 从大到小排列。

4.5 种树问题
【问题描述】一条街道分为 n 个区域(按 1~n 编号),每个都可种一棵树。有 m 户居民,每户会要求在区域 i~j 区间内种至少一棵树。现求一个能满足所有要求且种树最少的方案。 【贪心策略】 1. 对于要求,以区间右端(升序)为首要关键字,左端(升序)为次要关键字排序。 2. 按排好的序依次考察这些要求,若未满足,则在其最右端的区域种树,这时可能会满足多个要求。

4.6 马的哈密尔顿链
【问题描述】在一个 8×8 的国际象棋棋盘上,马(“马走日”)的初始位置(x, y)。怎么走可以不重复地走 过每一个格子?这样输出结果:如果马在第 i 步落在了格子(s, t)上,则在对应位置输出 i。 【贪心策略】每次往出度最小的点上跳。 #include <iostream> #include <iomanip> #include <cstring> using namespace std; // 两个数组存储对应的偏移量 47

第四单元 贪心算法 const int stepRow[8] = {-1,-2,-2,-1,1,2,2,1}; const int stepLine[8] = {-2,-1,1,2,2,1,-1,-2}; int board[8][8]; // 求(i,j)的出口数,各个出口对应的号存在a[]中。 // s表示顺序选择法的开始 int exitn(int i,int j,int s,int *a) { int i1,j1,k,count; for (count=k=0;k<8;k++) { i1 = i + step8[(s + k)% 8]; j1 = j + step8[(s + k)% 8]; if (i1>=0 && i1<8 && j1>=0 && j1<8 && board[i1][j1]==0) a[count++] = (s + k)% 8; } return count; } // 判断选择下个出口,s 是顺序选择法的开始序号 int next(int i,int j,int s) { int m, kk, a[8], b[8], temp; if ((m=exitn(i,j,s,a))==0) return -1; for (int min=9,k=0; k<m; k++) { // 逐个考虑取下一步最少的出口的出口 temp = exitn(i+step8[a[k]], j+step8[a[k]], s, b); if (temp<min) min = temp, kk = a[k]; } return kk; } int main() { int i,j,step,no,start=0; cin>>sx>>sy; do { memset(board,0,sizeof(board)); board[sx][sy] = 1; i = sx, j = sy; for (step=2; step<=64; step++) 48 // 没有出口

第四单元 贪心算法 { no = next(i,j,start) if (no == -1) break; i += step8[no], j += step8[no]; board[i][j] = step; } if (step>64 || no==-1) break; start++; } while(step<=64); if (no != -1) // 输出结果 for (i=0; i<8; i++) { for (j=0; j<8; j++) cout<<setw(4)<<board[i][j]; cout<<endl; } return 0; }

4.7 三值的排序①
【问题描述】 排序是一种很频繁的计算任务。现在考虑最多只有三值的排序问题。一个实际的例子是,当我们给某项竞 赛的优胜者按金银铜牌序的时候。 在这个任务中可能的值只有三种:1,2 和 3。我们用交换的方法把他排成升序的。 写一个程序计算出把给定的一个由 1、2、3 组成的数字序列排成升序所需的最少交换次数。 【分析】 为了使交换次数最小,我们想到了以下贪心策略: ① 能不交换就不交换; ② 如果能只用一次交换就完成归位,就不用两次交换。 由于排序之后是 11??1122??2233??33 的形式,我们不妨按照排序之后的结果对原数据分区。令 w(i,j)表示数字 i 在 j 区的数量。例如 122 312 13 中 w(2,1)=2。 按照①的说法,在一区的 1、二区的 2、三区的 3 就不应该再被交换了。 按照②的说法,在一区的 2 应该和二区的 1 进行交换,1 和 3、2 和 3 类似。 设这一次交换的步数为 A,则 A=min{w(1,2)+w(2,1)}+min{w(1,3)+w(3,1)}+min{w(2,3)+w(3,2)} 接下来已经不能一步恢复两个数字了, 就像 312 一样。 这时只有先让一个数字归位, 然后再交换另外两个。 这样,每三个数字需要用两步完成。 设这一次交换的步数为 B,则 B=(S-2A)÷3×2 其中 S 表示需交换的数字的总个数, 即 S=w(1,2)+w(2,1)+w(2,3)+w(3,2)+w(1,3)+w(3,1)。 最后将 A 和 B 相加,即最终结果。



题目来源:IOI96。但数据规模比原题大。

49

第四单元 贪心算法

4.8 田忌赛马①
【问题描述】 大家都知道 “田忌赛马” 的故事。 现在, 田忌再一次和齐王赛马。 他们各派出 N 匹马 (N?2000) 。 每场比赛,输的一方将要给赢的一方 200 两黄金,如果是平局的话,双方都不必拿出钱。 每匹马的速度值是固定而且已知的,而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去 对抗齐王的马,才能赢最多的钱? 【分析】② 题目本身已经告诉我们怎样用二分图最佳匹配来解决这个问题——把田忌的马放左边, 把齐王的马放右边, 田忌的马 A 和齐王的 B 之间,如果田忌的马胜,则连一条权为 200 的边;如果平局,则连一条权为 0 的边; 如果输,则连一条权为-200 的边。 但是题目告诉我们没有必要这样做,我们也无法这样做(复杂度很高,无法承受 N=2000 的规模) 。 我们不妨用贪心思想来分析一下问题。因为田忌掌握有比赛的“主动权” ,他总是根据齐王所出的马来分配 自己的马,所以这里不妨认为齐王的出马顺序是按马的速度从高到低出的。由这样的假设,我们归纳出如下贪 心策略: 1. 如果田忌剩下的马中最强的马都赢不了齐王剩下的最强的马,那么应该用最差的一匹马去输给齐王最 强的马。 2. 如果田忌剩下的马中最强的马可以赢齐王剩下的最强的马,那就用这匹马去赢齐王剩下的最强的马。 3. 如果田忌剩下的马中最强的马和齐王剩下的最强的马打平,可以选择打平或者用最差的马输掉比赛。 我们发现,第三个贪心策略出现了一个分支:打平或输掉。如果穷举所有的情况,算法的复杂度将比求二分图 最佳匹配还要高;如果一概而论的选择让最强的马去打平比赛或者是让最差的马去输掉比赛,则存在反例。 虽然因为第三个贪心出现了分支,我们不能直接的按照这种方法来设计出一个完全贪心的方法,但是通过 上述的三种贪心策略,我们可以发现,如果齐王的马是按速度排序之后,从高到低被派出的话,田忌一定是将 他马按速度排序之后,从两头取马去和齐王的马比赛。有了这个信息之后,动态规划的模型也就出来了! 设 f(i,j)表示田忌从“头”取了 i 匹较强的马,从“尾”取了 j 匹较弱的马进行比赛所能够得到的最大盈利, 则状态转移方程为:f(i,j)=max{ f(i,j-1)+g[n-(j-1)], f(i-1,j)+g(i)} 其中 g(x)表示田忌的第 x 匹马和齐王的第 i+j 匹马 (此时正是第 i+j 场比赛) 分别按照由强到弱的顺序排 序之后,田忌所能取得的盈利,胜为 200,输为-200,平为 0。

4.9 小结
贪心算法指从问题的初始状态出发,通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。 贪心思想的本质是每次都形成局部最优解,换一种方法说,就是每次都处理出一个最好的方案。 除了本单元的问题,还有一些常见问题也是用贪心算法求解的:建立哈夫曼树、Prim 算法、Kruskal 算 法、拓扑排序等。 如果有贪心性质存在,那么一定要采用贪心算法。因为它容易编写,容易调试,速度极快,并且节约空间。 几乎可以说,它是所有算法中最好的。 然而,贪心算法并不总是正确的,因为并不是每次局部最优解都会与整体最优解之间有联系,往往靠贪心 生成的解不是最优解。一般情况下,构造出贪心策略后要进行证明。 贪心还是一种思想。运用贪心思想,主要是为了分析出问题的一些本质,或者分析出低效算法的一些冗余。 合理地运用贪心思想,可以帮助运用其他算法解决问题。

① ②

题目来源:ACM2004 上海赛区,有删改。 选自黄劲松《贪婪的动态规划》,有改动。

50

第五单元 分治算法

第五单元

分治算法

5.1 一元三次方程求解①
【问题描述】有形如 ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d 均 为实数),并约定该方程存在三个不同实根(根的范围在-100 至 100 之间),且根与根之差的绝对值?1。 要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后 4 位。 【分析】 记方程为 f(x)=0,若存在 2 个数 x1 和 x2,且 x1<x2,f(x1)· f(x2)<0,则在(x1,x2)之间一定有一个根。 如果保留小数点后 2 位,则可以从-100.00 到 100.00 进行枚举,步长 0.01,然后取使 f(x)最接近 0 的三个数。 当已知区间(a,b)内有一个根时,可用二分法求根。若区间(a,b)内有根,则必有 f(a)· f(b)<0。重复执 行如下的过程: 令 m=(a+b)÷2, (1) 若 a+0.0001>b 或 f(m)=0,则可确定根为 m,并退出过程; (2) 若 f(a)· f(m)<0,则根在区间(a,m)中,故对区间重复该过程; (3) 若 f(a)· f(m)>0,则必然有 f(m)· f(b)<0,根在(m,b)中,对此区间重复该过程。 执行完毕,就可以得到精确到 0.0001 的根。 所以,根据“根与根之差的绝对值?1” ,我们先对区间[-100,-99]、[-99,-98]??[99,100]进行枚 举,确定这些区间内是否有解,然后对有解的区间使用上面的二分法。这样就能快速地求出所有的解了。

5.2 快速幂
用朴素算法求 an,时间复杂度为 O(n)。能不能更快一些? 以 a10 为例。我们知道,求一个数的平方是很快的,因为不用循环。那么 a10 能不能转化为谁的平方?没问 题,a10 是 a5 的平方,也就是说,如果 a5 求出来了,那么接下来只需对这个结果平方就能得出结果,并且少做 了 4 次乘法(求平方本身需要一次乘法) ! 5 a 能不能用类似的方法求出来?按照刚才的思想,指数应该能被 2 整除。我们可以先求 a4,然后再乘一个 a 就是 a5。 很明显,a4 是 a2 的平方,而 a2 可以直接求出来。于是我们最终只做了 4 次乘法。 总结刚才的思路,则有
?an/2×an/2 an=? [n/2] ×a[n/2]×a ?a

n是偶数 n是奇数

时间复杂度为 O(logn)。

5.3 排序
(1) 快速排序
快速排序的思路如下:如果序列中只有一个数字,则认为已经排好序了。 在待排序序列中任取一个数(一般取第一个) ,作为“标志” 。扫描序列中的其他数,将比“标志”小的数 放到它的左面,将比“标志”大的数放到它的右面。完成后, “标志”就把序列分成了两部分,一部分的数都比 它小,另一部分的数都比它大。 接下来,对被划分出的两部分分别进行快速排序就可以了。 (因为递归结束后,序列已经有序,所以不需要 对结果进行合并了。 )


题目来源:NOIP2001 第一题。原题要求保留小数点后两位。

51

第五单元 分治算法

(2) 归并排序
归并排序的思路如下:如果序列中只有一个数字,则认为已经排好序了。 划分阶段——将序列分成长度相等或接近的两部分。 递归——对划分后的两部分序列分别进行归并排序。 合并——递归地排序之后,两边的序列都已经有序,接下来需要将这两个有序序列合并。 那么,如何将两个有序序列合并? 首先需要一段临时空间来保存结果,我们不妨叫它“队列” 。 接下来在两个序列的开头放置两个“指针” 。每次都对“指针”所指的值进行比较,把最小值放到“队列” 中,并将那个最小值对应的“指针”向右移动。重复以上步骤,直到所有的数都被放入“队列” 。 最后,将“队列”内的数重新放回待排序的序列中就可以了。

(3) 求逆序对个数
【问题描述】对于一个序列 a1,a2,a3,?,an,如果存在 i<j,使 ai>aj,那么 ai,aj 就是一个逆序对。现在 给你一个有 N 个元素的序列,请求出序列内逆序对的个数。N?100000。 【分析】 可以考虑将序列分成两部分,分别求出子序列的逆序对个数。 横跨两序列的逆序对个数怎么统计?用枚举法行吗?不行,那样做就失去分治的意义了。 如果两区间有序,统计就很容易了,所以我们边统计边排序。由于子序列内逆序对个数的统计是在排序之 前完成的,排序又不影响两序列之间的逆序对个数,所以排序不会影响最终结果。 int cnt=0; // 逆序对个数 int a[100002], c[100002]; void MergeSort(int l, int r) // r=右边界索引+1 { int mid, i, j, tmp; if (r>l+1) { mid = (l+r)/2; MergeSort(l, mid); MergeSort(mid, r); tmp = l; for (i=l,j=mid; i<mid && j<r; ) { if (a[i]>a[j]) { c[tmp++] = a[j++]; cnt += mid-i; } else c[tmp++] = a[i++]; // 使用排序,就可以方便地数跨“分界”的逆序对个数了

} if (j<r) for (; j<r; j++) c[tmp++] = a[j]; else for (; i<mid; i++) c[tmp++] = a[i]; for (i=l; i<r; i++) a[i]=c[i]; 52

第五单元 分治算法 } }

5.4 最长非降子序列
【问题描述】一个序列 a1,a2,a3,?,an 共 N 个元素。现在要求从序列找到一个长度最长、且前面一项不大 于它后面任何一项的子序列。只需算出这个序列的长度。N?100000。 【分析】 用动态规划求解,则状态转移方程为:f(i)=max{f(j)}+1(aj>ai 且 i>j)。时间复杂度为 O(n2),n 很 大时会超时。超时的原因是大部分时间都耗在了寻找 max{f(j)}上面。 根据这一点,我们可以对算法进行改进。假设数组 C[]已经是符合条件的最长非降子序列,C[i]表示序列 中第 i 小的元素,那么我们就可以利用二分查找来确定 f[j]。时间复杂度由 O(n2)降到了 O(nlogn)。 int a[N], C[N], f[N], n; int LIS() { // 最长非降子序列

int min, max; // x的左右指针 for (int i=1; i<=n; i++) C[i]=INF; for (int i=1; i<=n; i++) { min=1, max=i; while (min<max) { int mid=(min+max)/2; if (C[mid]<a[i]) min=mid+1; else max=mid; } f[i]=min; C[min]=a[i]; } return f[n]; }

5.5 循环赛日程表问题
【问题描述】设有 2n(n?6)个球队进行单循环比赛,计划在 2n-1 天内完成,每个队每天进行一场比赛。设 计一个比赛的安排,使在 2n-1 天内每个队都与不同的对手比赛。例如 n=2 时的比赛安排为:
日期 客场 主场

1 2 1 4 3

2 3 4 1 2

3 4 3 2 1

1 2 3 4

【分析】 此题很难直接给出结果,我们先将问题进行分解。 设 m=2n,并将规模减半。假如 n=3(即 m=8) ,8 个球队的比赛,减半后变成 4 个球队的比赛(m=4) 。 4 个球队的比赛的安排方式还不是很明显,再减半到两个球队的比赛(m=2) 。 53

第五单元 分治算法 两个球队的比赛安排方式很简单,只要让两个球队直接进行一场比赛即可:1-2
日期 客场 主场

1 2 1

1 2

分析两个球队的比赛的情况不难发现, 表格主体是一个对称的方阵, 我们把这个方阵分成 4 部分 (即左上、 右上、左下、右下) ,右上部分可由左上部分加 1(即加 m/2)得到,而左上与右下部分、右上与左下部分分 别相等。因此我们也可以把这个方阵看作是由 m=1 的方阵所生成的。同理,可得 m=4 的方阵:
日期 客场 主场

1 2 1 4 3

2 3 4 1 2

3 4 3 2 1

1 2 3 4

同理可由 m=4 方阵生成 m=8 的方阵: 这样就构成了整个比赛的安排表。在算法设计中,用数组 a 记录 2n 个球队的循环比赛表,整个循环比赛表 从最初的 1×1 方阵按上述规则生成 2×2 的方阵,再生成 4×4 的方阵??直到生成出整个循环比赛表为止。
日期 客场 主场

1 2 1 4 3 6 5 8 7

2 3 4 1 2 7 8 5 6

3 4 3 2 1 8 7 6 5

4 5 6 7 8 1 2 3 4

5 6 5 8 7 2 1 4 3

6 7 8 5 6 3 4 1 2

7 8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8

5.6 棋盘覆盖
【问题描述】在一个 2k×2k 方格组成的棋盘中,若恰有一个方格与其他方格不同,则称该方格为一特殊方格, 且称该棋盘为一特殊棋盘。现在要用以下 4 种不同形态的 L 形骨牌覆盖一个给定的特殊棋盘上除特殊方格以外 的所有方格,且任何 2 个 L 型骨牌不得重叠覆盖。求一种覆盖方法。

4 种 L 形骨牌 特殊棋盘, 不能把骨牌放在黑色方格上面。 【分析】 尺寸为 2k×2k,我们可以想到将其分割成四个尺寸为 2k-1×2k-1 的子棋盘。 接下来,将 L 型放置在棋盘的正中央,使四个子棋盘都变成特殊棋盘(一个子棋盘含有特殊方格,另外三 个子棋盘恰好被骨牌覆盖,如下图)。此时问题也变成了四个相同的子问题,只需简单地对四小块区域进行递 归,就可以解决这道问题了。

54

第五单元 分治算法

特殊方格 “L”型骨牌

代码的时间复杂度和空间复杂度都是 O(4k)。 由于覆盖一个 2k×2k 棋盘所需的 L 型骨牌个数为(4k-1)/3, 所以算法已经是最优的了。

5.7 删除多余括号
【问题描述】输入一个表示算式的字符串(含四则运算、乘方、括号),要求去掉可能含有的多余括号,结果 要保持原表达式中变量和运算符的相对位置不变,且与原表达式等价。注意,题目只是要求你去括号,并没有 要求你化简表达式!此外,“+”和“-”不会用作正负号。 【分析】 符合“多余括号”的情况: ① 括号内没有运算符; ② 括号左侧是加法运算符,右侧是加法或减法运算符; ③ 括号左侧是乘法运算符,右侧是乘法或除法运算符。 对于表达式求值的问题,我们常采用这样的思路处理:找出式中最后运算的运算符 A,先递归地求出其左 右两边的值, 再将得到的值进行 A 运算。 当然这次没有必要进行运算, 只需分析括号内的运算符情况就可以了。 #include <iostream> #include <cstring> using namespace std; int a[1024]; char s[1024]; int cal(int st, int stp, int prev) { int t, min=4, min_i; for (int i=st; i<=stp; i++) { switch (s[i]) { case '^': if (min>3) min=3, min_i=i; break; case '*': case '/': if (min>2) min=2, min_i=i; break; case '+': case '-': if (min>1) min=1, min_i=i; break; case '(': i++; for (t=1;t!=0;i++) { 55

第五单元 分治算法 if (s[i]=='(') t++; if (s[i]==')') t--; } i--; break; }; } if (min==4) { if (s[st]=='(' && s[stp]==')') { t=cal(st+1,stp-1,0); if (t>=prev) { a[st]=a[stp]=1; return t; } } return 4; } cal(st,min_i-1,min); if (s[min_i]=='+' || s[min_i]=='*') cal(min_i+1,stp,min); else cal(min_i+1,stp,min+1); return min; } int main() { cin>>s; int sc=strlen(s); cal(0,sc-1,0); for (int i=0;i<sc;i++) if (!a[i]) cout<<s[i]; cout<<endl; return 0; }

5.8 聪明的质监员①
【问题描述】小 T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有 n 个矿石,从 1 到 n 逐一 编号,每个矿石都有自己的重量 wi 以及价值 vi。检验矿产的流程是: 1. 给定 m 个区间[Li,Ri]; 2. 选出一个参数 W;


题目来源:NOIP2011 day2 第二题

56

第五单元 分治算法 3. 对于一个区间[Li,Ri],计算矿石在这个区间上的检验值 Yi: Yi=?1×?vj,其中 j?[Li,Ri]且 wj?W,j 是矿石编号
j j

这批矿产的检验结果 Y 为各个区间的检验值之和。即: Y=?Yi
i=1 m

若这批矿产的检验结果与所给标准值 S 相差太多,就需要再去检验另一批矿产。小 T 不想费时间去检验另 一批矿产,所以他想通过调整参数 W 的值,让检验结果尽可能的靠近标准值 S,即使得 S-Y 的绝对值最小。 请你帮忙求出这个最小值。 【分析】 注意求 Yi 的公式。很明显,随着 W 的增大,符合条件的矿石减少,Yi、Y 都会减小。所以 Y 是一个随 W 变 化而变化的单调函数,也就是说 Y 具有二分性质。利用二分查找就可以找到最接近 S 的 Y。 由于区间很多,Yi 需要用前序和求。具体求法见 179 页“(2) 带条件的区间求和”。 #include <iostream> #include <cstring> using namespace std; inline long long _abs(long long x) { return x>0 ? x : -x; } const int N=200009; int n,m; int w[N],v[N], L[N],R[N]; long long S; int sumN[N]; long long sumV[N]; inline long long Y(int W) { long long result=0; sumN[0]=sumV[0]=0; for (int i=1; i<=n; i++) if (w[i]>=W) { sumN[i]=sumN[i-1]+1; sumV[i]=sumV[i-1]+v[i]; } else { sumN[i]=sumN[i-1]; sumV[i]=sumV[i-1]; } for (int i=1; i<=m; i++) { int &l=L[i], &r=R[i]; result+=(sumN[r]-sumN[l-1]) * (sumV[r]-sumV[l-1]); if (result>10000000000000LL) return 10000000000000LL; // 防溢出 57

第五单元 分治算法 } return result; } int maxW=0; int main() { ios::sync_with_stdio(false); cin>>n>>m>>S; for (int i=1; i<=n; i++) { cin>>w[i]>>v[i]; if (w[i]>maxW) maxW=w[i]; } for (int i=1; i<=m; i++) cin>>L[i]>>R[i]; // 二分查找 int x=0, y=maxW+1, mid; while (x<y) { mid = (x+y)/2; if (Y(mid)>S) x=mid+1; else y=mid; } long long a,b; a=_abs(S-Y(x)); b=_abs(S-Y(x-1)); // 由于Y不一定等于S,所以要判断最接近S的两个数。

if (a>b) cout<<b<<endl; else cout<<a<<endl; return 0; }

5.9 模板
这是分治算法模板的一种,另外一种模板是二分算法。 void solve(p) // p表示问题的范围、规模或别的东西。 { if (p的规模够小) { 用简单的办法解决 } // 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题。 // 一般把问题分成规模大致相同的两个子问题。 for (int i=1;i<=k;i++) 把p分解,第i个子问题为pi // 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题。 for (int i=1;i<=k;i++) solve(pi); 58

第五单元 分治算法 // 合并:将各个子问题的解合并为原问题的解。 ?? }

5.10 小结
分治法:对于一个规模为 n 的问题,若该问题可以容易地解决(比如说规模 n 较小)则直接解决,否则将 其分解为 k 个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各 子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 分治法所能解决的问题一般具有以下几个特征: 1. 该问题的规模缩小到一定的程度就可以容易地解决。 2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。 3. 利用该问题分解出的子问题的解可以合并为该问题的解。 4. 该问题所分解出的各个子问题是相互独立的,即子问题之间没有交集。

59

第六单元 动态规划

第六单元

动态规划

6.1 导例:数字三角形①
【问题简述】有一个层数为 n(n?1000)的数字三角形(如下图)。现有一只蚂蚁从顶层开始向下走,每走 下一级时,可向左下方向或右下方向走。求走到底层后它所经过数字的总和的最大值。 1 6 3 8 2 6 最大值=1+3+6+6+7=23 2 1 6 5 3 2 4 7 6

(1) 数据存储
1 6 8 3 → 2 6 2 1 6 5 3 2 4 7 6 每次往左下或右下方走 0 0 0 0 0 0 0 1 6 8 2 3 0 0 3 2 1 2 0 0 0 6 6 4 0 0 0 0 5 7 0 0 0 0 0 6 边界处理: 1. 最外层有一圈0,可以防止在逆推法中出界。 2. 由于右侧是0,所以决策时不会往那里走。 如果允许负数,可以把0换成一个很小的数,也可 以想其他方法。

每次往下方或右下方走

(2) 递推
1. 划分阶段:按行划分阶段,一行为一个阶段。 2. 状态表示:令 f(i,j)为第 i 行第 j 列上点到起点的最大和。所有下标从 1 开始。 3. 状态转移方程: ?
?f(i+1,j) 逆推:状态转移方程为 f(i,j)=max? +a(i,j)。结果为 f(1,1) ?f(i+1,j+1)

计算顺序:先把 f(i+1)一组算好,然后再计算 f(i)的一组??最后直接输出 f(1,1)。 int a[N][N], f[N][N]; // a是变形的数字三角形,f保存计算结果 ?? for (int i=n;i>0;i--) for (int j=1;j<=i;j++) f[i][j] = max(f[i+1][j], f[i+1][j+1]) + a[i][j]; cout<<f[1][1]; ?
?f(i-1,j) 顺推:状态转移方程为 f(i,j)=max? +a(i,j)。结果是 max{f(n,1), ?, f(n,n)}。 ?f(i-1,j-1)

计算顺序:先把 f[i]一组算好,再计算 f[i+1]的一组??在比较之后输出结果。 int a[N][N], f[N][N], result=0; // result表示计算结果 ?? for (int i=1;i<=n;i++) for (int j=1;j<=i;j++) f[i][j] = max(f[i-1][j], f[i-1][j-1]) + a[i][j]; for (int i=1;i<=n;i++) if (f[n][i]>result) result=f[n][i]; cout<<result;


题目来源:IOI'94

60

第六单元 动态规划

(3) 记忆化搜索——用递归代替递推
如果写出了状态转移方程,却不知道如何递推计算,就可以使用记忆化搜索。 以逆推的状态转移方程为例: bool visited[N][N]; // visited[i][j]表示f[i][j]是否算过。 // 也可以用f[i][j]=-1表示没算过。其实,只要把“算过”和“没算过”区分开就可以。 int a[N][N], f[N][N]; ?? int F(int x, int y) { if (visited[x][y]) return f[x][y]; if (x>n) return 0; // 如果算过,直接返回结果,否则递归计算。 // 边界处理

visited[x][y] = true; return f[x][y] = max(F[i+1][j], F[i+1][j+1]) + a[i][j]; } ?? memset(visited,0,sizeof(visited)); cout<<F(1,1); 它的时间复杂度尽管也是 O(n2),但运行起来要比递推慢得多。

(4) 记录路径
最大值是怎么来的?为了解决这个问题, 可以再开一个数组 g[N][N]来记录每一步的选择。 这样, g[i][j] 就表示“f(i,j)是从哪里来的”,或者说“用状态转移方程中的哪一条”。然后通过递归就可以找到路径上的 数。下面以顺推法为例。 int a[N][N], f[N][N], g[N][N]; // g[i][j]记录着“选择” void printpath(int i, int j) // 输出时务必注意顺序 { if (i==0||j==0) return; else if (g[i][j]==1) printpath(i-1,j); else printpath(i-1,j-1); cout<<a[i][j]<<' '; } int result,p; for (int i=1;i<=n;i++) { result=p=0; for (int j=1;j<=i;j++) { f[i][j] = f[i-1][j] + a[i][j]; g[i][j] = 1; // p表示终点的位置

// 状态转移方程中有两个选择,现在是第一个。 61

第六单元 动态规划 if (f[i][j] > f[i-1][j-1] + a[i][j]) { f[i][j] = f[i-1][j-1] + a[i][j]; g[i][j] = 2; } if (result > f[i][j]) result=f[i][j],p=j; } } cout<<result; printpath(n, p);

(5) 使用滚动数组
“空间换时间”虽然很好,但是有的时候,数组根本开不下! 递推的时候,我们发现尽管 f 有 n 行,但只有两行参与了计算。所以可以把 f 变成 f[1][N]来节省空间。 计算的时候,要让 i 和 i-1 对 2 取模,即 f[i%2][j] = max(f[(i-1)%2][j], f[(i-1)%2][j-1]) + a[i][j]; 如果看着不舒服,可以改成: #define F(i,j) f[(i)%2][j] // 注意括号 ?? F(i,j) = max(F(i-1,j), F(i-1,j-1)) + a[i][j]; 不过,要求输出字典序最小①的解决方案时,最好不要使用滚动数组。

(6) 非完美解法
如果你在竞赛时被动态规划题卡住,你还不想得 0 分,你可以考虑以下几种方法: ① 暴力搜索 int result = 0; void search(int x, int y, int depth, int sum) { if (depth==n) { if (sum>result) result=sum; return; } else { search(x+1,y,depth+1,sum + a[x+1][y]); search(x+1,y+1,depth+1,sum + a[x+1][y+1]); } } 调用 try(1,1,1,a[1][1])即可。时间复杂度 O(2n)。 ② 贪心+搜索 对于某些求最小值的问题,可以先用贪心算法得到较优解。然后开始搜索。搜索时只要计算结果比已求得 的最小值大就剪枝。搜索到顶点时更新最小值。


“字典序最小”:一要保证步骤最少,二要保证在步骤相同的情况下,优先选择序号靠前的决策。

62

第六单元 动态规划 不过,求最大值的问题不能使用此方法。 ③ 随机化 从最顶层开始,让向左走和向右走的概率相等①。当然可以加入贪心思想——让较大值方向的概率大一些。 将这个过程重复若干次,总有可能得到正确答案。 int result=0; srand(time(NULL)); for (int t=1; t<=10000; t++) { int x=0, v=0; for (int i=1; i<=n; i++) { double p=(double)rand()/(double)RAND_MAX; if (p<0.5) x+=0; else x+=1; v+=a[i][x]; } if (v>result) result=v; }

6.2 区间问题:石子合并②
【问题简述】n 堆石子围成一圈,每堆石子的量 a[i]已知。每次可以将相邻两堆合并为一堆,将合并后石子的 总量记为这次合并的得分。 n-1 次合并后石子成为一堆。 求这 n-1 次合并的得分之和可能的最大值和最小值。 (n?100,1?i?n) 示例: 4 4 5 9 4 5 4 9 4 14 18 22 4 4

这种合并方法的总得分=14+18+22=54

(1) 环的处理方法
以某一点作为起点,按顺时针或逆时针的顺序把环上的元素复制两遍。处理时注意起点范围(0~n-1) 和最大长度(n) 。 例如上面的示例,可以变成:5 9 4 4 5 9 4 4,这样就包含了分别以 5、9、4、4 为起点的 4 个环。

(2) 求解
1. 递推思路:计算将第 i 堆至第 j 堆完全合并所能获得的最大得分。这是此题的关键。考虑模拟每种合并后 的具体情形是行不通的。把问题变成这样后就好解决了。 2. 划分阶段:以合并的次数作为标准划分阶段。 3. 确定状态:f1(i,j)表示第 i 堆至第 j 堆合并所能获得的最大价值,f2(i,j)表示第 i 堆至第 j 堆合并所能获得 的最小价值。

① ②

实际上,应该让远离中心的方向的概率大一些,因为在等可能的情况下,层数越多,终点在中间位置的概率越大。 题目来源:NOI'95

63

第六单元 动态规划 4. 状态转移方程: f1(i,j)=max{f1(i,k)+f1(k+1,j)+d(i,j)} f2(i,j)=min{f2(i,k)+f2(k+1,j)+d(i,j)},其中 1?i?k<j?n 边界状态:f1(i,i)=f2(i,i)=0 d(i,j)表示当次合并的得分, 即从 i 到 j 的石子数量, d(i,j)=a[i]+a[i+1]+?+a[j], 可用前序和求出。 5. 递推时注意,循环的最外层不是 i,也不是 j,而是 j-i! 最后从 f1(1,n)到 f1(n,n+n),从 f2(1,n)到 f2(n,n+n),找出最值即可。 #include <cstring> #include <iostream> using namespace std; const int INF = 10000000; inline int d(int i,int j) { return s[j]-s[i-1]; } int f1[101][101],f2[101][101]; int v[201], s[201]; int n; int main() { memset(f1, 0, sizeof(f1)); memset(f2, 0, sizeof(f2)); memset(s, 0, sizeof(s)); cin>>n; for (int i=1;i<=n;i++) { cin>>v[i]; v[n+i]=v[i]; } for (int i=1;i<=n+n;i++) s[i]=s[i-1]+v[i]; // 前序和 // 把环拉成链

for (int p=1;p<n;p++) for (int i=1,j=i+p;(i<n+n)&&j<=(n+n);i++,j=i+p) { f1[i][j]=0; f2[i][j]=INF; for (int k=i;k<j;k++) { f1[i][j] = max(f1[i][j], f1[i][k]+f1[k+1][j]+d(i,j)); f2[i][j] = min(f2[i][j], f2[i][k]+f2[k+1][j]+d(i,j)); } cout<<"f2["<<i<<"]["<<j<<"]="<<f2[i][j]<<endl; } int r1=0, r2=INF; for (int i=1;i<=n;i++) { if (f1[i][i+n-1]>r1) r1=f1[i][i+n-1]; if (f2[i][i+n-1]<r2) r2=f2[i][i+n-1]; } cout<<r1<<" "<<r2<<endl; 64

第六单元 动态规划 return 0; } 时间复杂度:O(n3)

(3) 能量项链①
【问题简述】有一串能量项链,上有 N 颗能量珠。能量珠有头标记与尾标记。并且,对于相邻的两颗珠子,前 一颗珠子的尾标记一定等于后一颗珠子的头标记。如果前一颗能量珠的头标记为 m,尾标记为 r,后一颗能量 珠的头标记为 r,尾标记为 n,则聚合后释放的能量为 m×r×n,新产生的珠子的头标记为 m,尾标记为 n。 现在要把所有的珠子聚合成一个珠子。请你设计一个聚合顺序,使一串项链释放出的总能量最大。 【分析】 思路是相似的——阶段、状态都一样,而得分的方式变了。 1. 设第 i 个珠子的头标记是 value[i],规定所有下标都是从 1 开始。 2. 状态转移方程:设 f(i,j)为从 i 到 j 这一条链的最大值,那么 f(i,j)=max{f(i,k)+f(k,j)+value[i]*value[k+1]*value[j+1]},其中 i?k<j 边界条件 f(k,k)=0。

6.3 坐标问题
(1) 单向取数问题
【问题描述】一个 m×n 的方格,每个格子都有一个数字。现在从方格的左上角出发,到右下角停止。要求只 能往右走或往下走, 且一次只能走一步。 现在使经过的所有数字的和最大, 问最大值是多少? (1?m,n?1000) 1 5 9 8 2 8 7 1 6 2 0 4 5 1 7 1 4 3 6 3

【分析】 很容易想到贪心算法,即每次往数值更大的方向走。不过它是错误的。正确的做法是动态规划: 1. 划分阶段:每走一步为一个阶段。 2. 状态表示:f(r,c)表示从起点出发走到第 r 行第 c 列②时经过数字总和的最大值。
?f(r-1,c) 3. 状态转移方程:f(r,c)=max? +map(r,c) ?f(r,c-1)

边界处理:让方格的下标从 1 开始,这样方格就可以多出一圈——0。

(2) 变式问题
① 必须经过某点 解决方法:将取数过程分成两部分。第一部分的起点是(1,1),终点是这个点;第二部分的起点是这个点, 终点是(m,n)(第 m 行第 n 列) 。比如,要求必须过(3,2),就可以按下图把问题一分为二: 1 8 7
① ②

5 6 2

9 4 5

8 7 1

2 3 6

题目来源:NOIP2006 第一题 也可以按坐标建立状态,不过它不如按行列适合 CPU 的工作方式。

65

第六单元 动态规划 1 0 1 4 3

② 不能经过某点 一个简单的办法是:把那个点的值设置成-INF(负无穷大) 。由于经过此点要“付出巨大的代价” ,所以 状态不会从这点转移而来。 ③ 竖直方向上最多有连续两个点相邻 解决方法:在状态中加一维,表示“已经连续向下走的次数” 。 1. 状态表示:f(r,c,i)表示从起点出发走到第 r 行第 c 列时经过数字总和的最大值,i 表示“已经连续向下走 的次数”。
?f(r,c-1,0) 2. 状态转移方程:f(r,c,0)=max? +map(r,c) ?f(r,c-1,1)

f(r,c,1)=f(r-1,c,0)+map(r,c) 3. 输出:f(m,n,0)和 f(m,n,1)中的最大值。 ④ 传送门#1 到达点(a,b)后,便立刻跳转到(a',b'),其中 b'>b(否则会发生无限传送) 。 解决方法:分两种情况讨论,即经过传送门、不经过传送门。 如下图,传送门的入口为(4,3),出口为(2,5),则整个过程可以分为两个子问题。 1 8 7 1 3 0 5 6 2 9 4 5 1 3 8 2 3 6 3 4 1 1 8 7 1 3 0 5 6 2 0 2 5 9 4 5 1 7 8 1 2 1 8 5 3 3 5 9 2 1 4 8 7 1 4 6 5 2 3 6 3 4 1 2 -∞ 7 1 9 1 2 1 4 4 6 5

0 -∞ 8 2 7 5 5 8 3

不经过传送门

经过传送门

⑤ 传送门#2 到达点(a,b)后,便立刻跳转到(a',b'),反过来也能跳转,其中 a<a',b'>b(否则会发生无限传送) 。 解决方法:分三种情况讨论,即不经过传送门、先经过左侧的传送门、先经过右侧的传送门。 1 8 7 1 3 0 5 6 2 9 4 5 1 3 8 2 3 6 3 4 1 1 8 7 1 3 0 5 6 2 0 2 5 9 4 5 1 7 8 1 2 1 8 5 3 3 5 9 2 1 4 8 7 1 4 6 5 2 3 6 3 4 1 1 8 7 1 3 0 5 6 2 0 2 5 9 4 5 1 7 8 1 2 1 8 5 3 3 5 9 2 1 4 8 7 1 4 6 5 2 3 6 3 4 1 2 -∞ 7 1 9 1 2 1 4 4 6 5

0 -∞ 8 2 7 5 5 8 3

不经过传送门

先进入左侧的传送门

先进入右侧的传送门

(3) 传纸条①
【问题简述】一个 m×n 的方格,每个格子都有一个数字,但左上角和右下角都是 0。现在从方格的左上角引 出两条路径,它们同时出发,都到右下角停止②。要求只能往右走或往下走,一次只能走一步,且两条路径不 能交叉、重合。现在使经过的所有数字的和最大,问最大值是多少?(1?m,n?50)

① ②

题目来源:NOIP2008 第三题 原题是纸条先从左上角走到右下角,然后从右下角再回到左上角。

66

第六单元 动态规划 【分析】 如果还使用(1)的动态转移方程,就很有可能在第一条路径选择完成后,第二条路径无法到达终点!所以 要同时考虑两条路径。 思路 1: 1. 划分阶段:每走一步为一个阶段(一次只移动一张纸条)。 2. 状态表示:设两张纸条分别位于第 r1 行第 c1 列、第 r2 行第 c2 列,那么 f(r1,c1,r2,c2)表示两张纸条从起 点出发,分别到达这两个点时经过的数字和的最大值。 为了保证道路不交叉,应有 x1<r2。 r -1,c ,r ,c )+map(r ,c ) ?ff( (r ,c -1,r ,c )+map(r ,c ) 状态转移方程:f(r ,c ,r ,c )=max? f(r ,c ,r -1,c )+map(r ,c ) ?f(r ,c ,r ,c -1)+map(r ,c )
1 1 1 1 1 2 2 2 2 2 1 1 2 2 1 1 2 2 1 1 1 1 1 2 2 2 2 2

3.

(↓×) (→×) (×↓) (×→)

4. 一个优化:因为 r1+c1=r2+c2,所以可以去掉一维。这样时间可由四次方降到三次方。 5. 输出:f(m, n-1, m-1, n) 思路 2: 可以发现,只要知道移动步数和两个横坐标,那么两个纵坐标就可以计算出来。 1. 划分阶段:每走一步为一个阶段。 与思路 1 不同的是,这一次两张纸条要同时移动。 2. 状态表示:设两张纸条分别位于第 r1 行第 c1 列、第 r2 行第 c2 列,i 为移动步数,那么 f(i,r1,r2)表示两张 纸条从起点出发,经过 i 步分别到达这两个点时经过的数字和的最大值。 为了保证道路不交叉,应有 r1>r2。 i-1,r -1,r -1) ?ff( (i-1,r -1,r ) 状态转移方程:f(i,r ,r )=map(r ,c )+map(r ,c )+max? f(i-1,r ,r -1) ?f(i-1,r ,r )
1 1 1 1 2 2 1 2 1 1 2 2 2 2

3.

(↓↓) (↓→) (→↓) (→→)

c1=i+2-r1,c2=i+2-r2,同时 r1+c1=r2+c2。 4. 输出:f(m+n-3, m, m-1) m+n-3 是从左上角出发,到右下角的移动步数。

6.4 背包问题
参见 78 页“第七单元 背包专题” 。

6.5 编号问题
(1) 最长非降子序列(LIS)
【问题描述】一个序列 a1,a2,a3,?,an 共 N 个元素。现在请用动态规划的方法求出从序列找到一个长度最 长、且前面一项不大于它后面任何一项的子序列。只需输出序列的长度。N?1000。 【分析】 1. 递推思路:f(i)表示对于前 i 个数组成的序列,保留第 i 个数时能取得的非降子序列的最大长度。 2. 状态转移方程:f(i)=max{f(j)}+1(aj>ai 且 i>j) int f[1000]; int LIS(int *a, int n) { int max, k; 67

第六单元 动态规划 f[0]=0; for (int i=1;i<=n;i++) { max=k=0; for (int j=i-1;j>0;j--) if ((a[j]<a[i])&&(f[j]>=max)) max=f[j], k=j; f[i]=f[k]+1; } max=0; for (int i=1;i<=n;i++) if (f[i]>max) max=f[i]; return max; }

(2) 最长公共子序列(LCS)
【问题描述】有两个序列 a 和 b。求一个最长的序列 p,使它既是 a 的子序列,又是 b 的子序列。输出序列 p 的长度。(a、b 长度小于 1000) 【分析】 1. 状态表示:f(i,j)表示 a 的前 i 个元素、b 的前 j 个元素中最长公共子序列的长度。

?f(i-1,j) ? 2. 状态转移方程:f(i,j)=max?f(i,j-1) ?f(i-1,j-1)+(ai==bj?1:0) ?
int f[1001][1001]; int LCS(int *a, int m, int *b, int n) // a中m个元素,b中n个元素 { memset(f,0,sizeof(f)); for (int i=1; i<=m; i++) for (int j=1; j<=n; j++) { if (a[i]==b[j]) f[i][j]=f[i-1][j-1]+1; f[i][j] = max(f[i][j], max(f[i-1][j], f[i][j-1])); } return f[m][n]; }

6.6 递归结构问题
(1) 乘积最大①
【问题简述】在一个长度为 n 的非 0 数字串中插入 k 个乘号,使表达式的值最大。(6?n?40,1?k?6) 【分析】 1. 划分阶段:以一个乘号为一个阶段。 2. 状态表示:f(i,l)表示前 i 个数字插入 l 个乘号之后的最大乘积。


题目来源:NOIP2000 第二题

68

第六单元 动态规划 3. 状态转移方程:f(i,l) = max{f(j, l-1)×s(j+1, n)},l<j<i, l?min{k, i-1} 边界条件:f(i,0) = s(1,i) 其中 s(a,b)表示连接第 a 个数字到第 b 个数字之后表示的整数。 #include <iostream> #include <cstring> using namespace std; struct hp {……}; // 见123页“11.7 高精度算法(压位存储)!”。 int n, k; hp f[51][21], s[51][51]; int main() { char c; long long t; cin>>n>>k; memset(f,0,sizeof(f)); memset(s,0,sizeof(s)); for (int i=1;i<=n;i++) { cin>>c; s[i][i]=c-'0'; t=1; for (int j=i-1;j>0;j--) s[j][i]=s[j][j]*(t*=10)+s[j+1][i]; f[i][0]=s[1][i]; } for (int i=1;i<=n;i++) for (int l=1; l<=min(i-1, k); l++) { f[i][l] = 0; for (int j=l;j<i;j++) f[i][l] = max(f[i][l], f[j][l-1]*s[j+1][i]); } cout<<f[n][k]<<endl; return 0; } // 递推计算s

(2) 加分二叉树①
【问题简述】设一个 n 个结点的二叉树的中序遍历为(1,2,3,?,n),其中数字 1,2,3,?,n 为结点编号。 每个结点都有一个分数(均为正整数),记第 i 个结点的分数为 di,二叉树及它的每个子树都有一个加分,任 一棵子树(也包含二叉树本身)的加分=左子树的加分×右子树的加分+根的分数 若某个子树为主,规定其加分为 1,叶子的加分就是叶结点本身的分数。不考虑它的空子树。


题目来源:NOIP2003 第三题

69

第六单元 动态规划 求一棵符合中序遍历为(1,2,3,?,n)且加分最高的二叉树。要求输出最高加分和前序遍历。 【分析】 本题中的树是无根树,需要枚举节点作为根的情况,重复有根树的动态规划过程。 1. 状态表示:f(i,j)表示由第 i 个元素到第 j 个元素组成的二叉树的最大加分。 2. 状态转移方程:f(i,j) = max{f(i,k-1)×f(k+1,j)+dk},i?k?j(实际上,这里的 k 表示根结点) 边界条件:f(i,i) = di 3. 递推时注意,循环的最外层不是 i,也不是 j,而是 j-i! #include <iostream> #include <cstring> using namespace std; int n, root[31][31]; unsigned int f[31][31], d[31]; void preorder(int i, int j) { int k=root[i][j]; if (k==0) return; cout<<k<<" "; preorder(i, k-1); preorder(k+1, j); } int main() { memset(root, 0, sizeof(root)); memset(f, 0, sizeof(f)); memset(d, 0, sizeof(d)); cin>>n; for (int i=1; i<=n; i++) cin>>d[i]; for (int i=0; i<=n; i++) { f[i][i]=d[i]; root[i][i]=i; f[i+1][i]=1; } // 计算单个结点构成的二叉树的加分,并记录根结点 // 按前序遍历输出最大加分二叉树

for (int p=1; p<n; p++) // 依次计算间距为d的两个结点构成的二叉树的最大加分 for (int i=1; i<=n-p; i++) { int j=i+p; for (int k=i; k<=j; k++) { int temp = f[i][k-1] * f[k+1][j] + d[k]; if (temp > f[i][j]) f[i][j] = temp, root[i][j] = k; } 70

第六单元 动态规划 } cout<<f[1][n]<<endl; preorder(1, n); return 0; }

6.7
(1) 特殊 DAG 的最短路径

DAG 上的最短路径

如果用动态规划求 DAG 上的最短路径,应该先进行拓扑排序。

【问题描述】下图的拓扑排序序列为 0,1,2??n-1,求结点 0 到其他各点的最短路径长。 邻接矩阵(未填充部分为∞) 2 4 5 3 0 1 3 5 5 3 4 5 1 1 6 2 3 1 3 8 6 7 5 4 9 i\j 0 0 1 2 3 4 5 6 7 8 9 1 3 2 4 3 5 2 4 5 5 3 1 3 1 5 1 6 5 4 6 7 8 9

【分析】 1. 状态表示:设 f(x)表示结点 0 到结点 x 的最短路径长度。 2. 状态转移方程:f(x)=min(f(i)+G[i][x]),其中结点 i 是结点 x 的前趋。 边界条件:f(0)=0 int G[N][N], n; int f[N]; f[0]=0; for (int i=1; i<n; i++) f[i]=INF; for (int x=0; x<n; x++) for (int i=0; i<n; i++) f[x] = min(f[x], f[i]+G[i][x]); for (int i=0; i<n; i++) cout<<f[i]<<" ";

(2) 关键工程
参见 152 页“13.8 拓扑排序” 。

71

第六单元 动态规划

(3) 街道
【问题描述】下图是一个 m×n 的街区。每条马路(最短的边算一条马路)上有一个数字。从左上角出发到右 下角,路上只能往右或往下走。问经过的数字的和最大可以达到多少。

【分析】 转化思路:构造出一个 DAG。

由于这道题道路整齐,所以求解起来更容易一些。

6.8 树形动态规划*
(1) 苹果树
【问题描述】有一棵苹果树,如果树枝有分叉,一定是分 2 叉(就是说没有只有 1 个儿子的结点)。这棵树共 有 n 个结点(叶子点或者树枝分叉点),编号为 1~n,树根编号一定是 1。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 4 个树枝的树: 2 5 \ / 3 4 \ / 1 现在这颗树枝条太多了,需要剪枝。但是一些树枝上长有苹果。已知需要保留的树枝数量为 q,求出最多 能留住多少苹果。 数据规模:1<n?100,1?q?n,每个树枝上的苹果数量不超过 30000。 【分析】 1. 状态表示:f(i,n)表示在以 i 为根结点的二叉树中保留 n 个树枝后,留住苹果的最大值。 2. 状态转移方程:f(i,n)=max{f(i 的左儿子, k)+f(i 的右儿子, n-k)+i→num},其中 num 指该结点 与父亲结点连接成的树枝上的苹果数,0?k?j 3. 实现:由于要把儿子的信息传递给父亲,所以用后序遍历(下面的代码是后序遍历,虽然看起来不像)。 struct node { int num; // 指该结点与父亲结点连接成的树枝上的苹果数 node *leftchild, *rightchild; 72

第六单元 动态规划 } mem[N]; int postorder(node *i, int a) { if (i==NULL) return 0; int result=0; for (int k=0; k<=a; k++) result = max(result, postorder(i->leftchild, k) + postorder(i->rightchild, a-k) + i->num); return result; }

(2) 选课①
【问题简述】某大学有 m 门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程 a 是课程 b 的先 修课,那么只有学完了课程 a,才能学习课程 b)。一个学生要从这些课程里选择 n 门课程学习,他能获得的 最大学分是多少? 【输入格式】第一行有两个整数 m,n 用空格隔开。(1?n?m?1000) 接下来的 m 行:第 I+1 行包含两个整数 ki 和 si,ki 表示第 I 门课的直接先修课,si 表示第 I 门课的学分。 若 ki=0 表示没有直接先修课(1?ki?m,1?si?10) 。 【输出格式】只有一个数,是选 n 门课程的最大得分。 【分析】 1. 状态表示:f(i,c)表示在以 i 为根结点的二叉树中取 c 门课程后得到的学分的最大值。 2. 状态转移方程: f(i,c)=max{f(i->leftchild, k-1)+i->v+f(i->rightchild, c-k)},0?k?j 3. 实现: ? 把 0 作为顶点。 ? 需要把多叉树转化为二叉树(左儿子右兄弟)。 ? 后序遍历 #include <iostream> #include <cstring> using namespace std; // -1表示没有结点。 struct node { int value, leftchild, rightchild; } a[1002]; int F[1002][152], parent[1002]; int m,n; #define f(x,y) F[(x)+1][(y)+1] int postorder(int x, int y) { if (f(x,y)>=0) return f(x,y); int m=postorder(a[x].rightchild, y);


// 只有右子树的情况

题目来源:CTSC'97。原题要求输出具体的解。

73

第六单元 动态规划 for (int k=1; k<=y; k++) m = max(m, postorder(a[x].leftchild,k-1) + a[x].value + postorder(a[x].rightchild,y-k)); return f(x,y)=m; } int main() { cin>>m>>n; memset(F,0,sizeof(F)); memset(parent,0,sizeof(parent)); memset(a,-1,sizeof(a)); // 树变二叉树 int k,s; for (int i=1; i<=m; i++) { cin>>k>>s; a[i].value=s; if (parent[k]==0) a[k].leftchild=i; else a[parent[k]].rightchild=i; parent[k]=i; } // 递推的边界处理 for (int i=-1; i<=m; i++) for (int j=-1; j<=n; j++) f(i,j) = (i==-1 || j==0) ? 0: (-1); postorder(a[0].leftchild, n); cout<<f(a[0].leftchild,n); return 0; }

6.9 状态压缩类问题:过河①
【问题简述】一个独木桥,可看做一个数轴,上面每个点的坐标分别为 0、1、2、??、L(L?109)。青蛙 从坐标为 0 的点出发,不停地跳跃,直到跳到或超过 L 点。它一次跳跃的距离最小为 S,最大为 T(包括 S、T, 1?S?T?10)。 独木桥上有 M(M?100)个石子,位置都是已知的,并且不会重叠。青蛙讨厌踩到石子上。问:青蛙若 想通过独木桥,最少要踩几个石子? 【分析】 很容易想出,若 f(i)表示从起点到达 i 坐标点所踩到石子的最小个数,则 f(i)=min{f(i-k)}+f(i),s?k?t


题目来源:NOIP2005 第二题

74

第六单元 动态规划 但是,我们无法开长度为 1000000000 的数组,即使能开,程序也不可能在 1s 内结束。 仔细观察数据规模,就会发现,石子的数量非常稀少!所以,长长的空隙一定可以被压短。 以下代码首先对 stone 进行了排序,然后令 L=stone[i]-stone[i-1]。当 L%t==0 时,令 k=t;当 L%t!=0 时,令 k=L%t。然后令 k 为 k+t。 最后判断如果 k>L,那么 map[]数组中 stone[i]和 stone[i-1]两石头的距离就被等效成为 L;如果 k<=L,那么 map[]数组中 stone[i]和 stone[i-1]两石头的距离就被等效成为 k。 接下来就可以用动态规划了。 #include <iostream> #include <cstring> #include <algorithm> using namespace std; int stone[101], map[100001], f[100001]; int s,t,m,p=0,q; int main() { int l,k,result; memset(stone,0,sizeof(stone)); memset(map,0,sizeof(map)); memset(f,0,sizeof(f)); cin>>l>>s>>t>>m; for(int i=1;i<=m;i++) cin>>stone[i]; sort(stone+1,stone+m+1); for(int i=1;i<=m;i++) { l=stone[i]-stone[i-1]; if(l%t==0) k=t; else k=l%t; k+=t; if(l<k) k=l; p+=k; map[p]=1; } for(int i=1;i<=p+t;i++) { result=200; for(int j=i-t;j<=i-s;j++) if(j>=0 && f[j]<result) result=f[j]; f[i]=result+map[i]; } result=200; // 读入石子坐标

// 缩短数组,p为map[]长度

// 动态规划

for(int i=p+1;i<=p+t;i++) if (f[i]<result) result=f[i]; cout<<result; return 0; }

// 找最小值

75

第六单元 动态规划

6.10

Bitonic 旅行

“货郎担问题”是 NP 问题,只能用搜索解决。后来,J. L. Bentley 提出了的变形——Bitonic Tour 问题(又称双调旅程问题)。这个新问题可以用动态规划解决。 【问题描述】已知地图上 n 个旅行须到达城市的坐标,要求从最西端的城市开始,严格地由西向东到最东端的 城市,再严格地由东向西回到出发点。除出发点外,每个城市经过且只经过一次。给出路程的最短值。(1?n ?1000) 【分析】 可以看出来,如果以城市来表示状态,将与搜索无异! 1. 递推之前的预处理:将地点按从东到西编号(按横坐标大小排序,然后扫描)。 2. 递推思路:从最东端开始,找两条到最西端的路径。每加入一个地点为一个阶段。 3. 状态表示:f(i,j)表示从地点 i 到最东再到地点 j 路程的最小值。假设 i 是走在前面的点,即 i?j。 4. 状态转移方程: ? 如果 i=j,即 i 和 j 处在同一点,那么 f(i,j)=f(i,i)=f(i,i-1)+dist(i,i-1) ? 如果 i=j+1,即 j 在 i 的紧邻的靠后一点,那么 f(i,j)=min{ f(j,k)+dist(i,k) },1?k?j。 ? 如果 i>j+1,即 j 离 i 在后面一个距离的范围以上,那么 f(i,j)=f(i-1,j)+dist(i,i-1) ? 其中 dist(a,b)是 a、b 两点间的距离。 5. 时间复杂度:O(n2) // 需要:<cmath> inline int sqr(int x) { return x*x; } double x[N], y[N]; // 每个点的坐标。假设x、y已经按照从西向东的顺序排列好。 double f[N][N], dist[N][N]; int n; double BitonicTour() { // 计算两点间的距离 for (int i=0;i<n;i++) for (int j=0;j<n;j++) { dist[i][j]=sqrt(sqr(X[i]-X[j])+sqr(Y[i]-Y[j])); f[i][j]=INF; } f[0][0]=0.0; for (int i=1;i<n;i++) for (int j=0;j<i;j++) if (i==j+1) for (int k=0;k<=j;k++) f[i][j] = min(f[i][j], f[j][k]+dist[k][i]); else if (j<i-1) f[i][j]=f[i-1][j]+dist[i][i-1]; else continue; return f[n-1][n-2]; 76

第六单元 动态规划 }

6.11 小结
动态规划:各个阶段采取的决策依赖于当前状态,又随即引起状态的转移,在变化的状态中产生一个决策 序列,这种解决多阶段决策最优化问题的方法为动态规划方法。 1. 动态规划的基本思想 动态规划的基本思想是“空间换时间”,努力避免重复解决相同问题或子问题。由于这个原因,动态规划 的速度比搜索快得多。 2. 动态规划的原理 动态规划满足两个原理:最优化原理、无后效性原则。 最优化原理指无论过去的状态和决策如何,对前面的决策所形成的当前状态而言,余下的诸决策必须构成 最优策略。通俗地说,如果全局最优,那么一定有局部最优。如果问题满足最优化原理,则说该问题具有最优 子结构。 无后效性原则指某阶段的状态一旦确定,则此后过程的演变不再受此前各状态及决策的影响。也就是说, “未来与过去无关”。具体地说,如果一个问题被划分各个阶段之后,阶段 I 中的状态只能由阶段 I+1 中的状 态通过状态转移方程得来,与其他状态没有关系,特别是与未发生的状态没有关系,这就是无后效性。 3. 用动态规划解题的方法 动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到 结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路 线)。如图所示。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。 初始状态→决策 1→决策 2→?→决策 n→结束状态 ① 划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。在划分阶段时,注意划分后的阶段一 定要是有序的或者是可排序的,否则问题就无法求解。 ② 确定状态和状态变量:注意状态必须满足无后效性。 ③ 确定决策: 找到子问题是进行动态规划的重要一步。 动态规划和递推更多应考虑本问题由哪些已解决子 问题构成,而不是考虑本问题对将来哪些问题有贡献。 ④ 确定边界条件,写出状态转移方程。 ⑤ 编程 如果某一个问题是从已知的动态规划问题变形而来的, 你可以考虑在原有的状态转移方程的基础上加一维。 4. 动态规划的实现 动态规划有两种实现方法:递推和记忆化搜索。 使用递推法时要注意计算顺序,题型不同,计算顺序也不同。如果计算顺序不明显,也可采用记忆化搜索。 但是,记忆化搜索要比直接递推慢几倍。 动态规划往往要耗费大量内存空间。在空间紧张时,可以采用滚动数组来优化动态规划。

77

第七单元 背包专题

第七单元 背包专题①
7.1 部分背包问题
参见 46 页“4.1 装载问题” 。部分背包问题是贪心算法问题,其他背包问题都是动态规划问题。

7.2

0/1 背包问题!

【问题描述】有 n 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i],价值是 v[i]。求解将哪些物品 装入背包可使价值总和最大。

(1) 二维数组表示
1. 定义状态:f[i][c]表示前 i 件物品恰放入一个容量为 c 的背包可以获得的最大价值。
?f[i-1][c] 2. 状态转移方程:f[i][c]=max? ?f[i-1][c-w[i]]+v[i]

(不选这件物品) (选择这件物品)

// 注意边界处理 for (int i=1;i<=n;i++) for (int c=0;c<=C;c++) { f[i][c]=f[i-1][c]; if (c>=w[i]) f[i][c] = max(f[i][c], f[i-1][c-w[i]] + v[i]); } 时间复杂度、空间复杂度:都是 O(NC)

(2) 一维数组表示
1. 定义状态:由于递推的过程和雪天环形路上的扫雪车类似,所以可以把 i 省略。 2. 状态转移方程:f[c]=max?
?f[c] ?f[c-w[i]]+v[i]

(不选这件物品) (选择这件物品)

递推时注意 c 要从 C 开始,倒着推。 // 注意边界处理 for (int i=1;i<=n;i++) for (int c=C;c>=0;c--) if (c>=w[i]) f[c] = max(f[c], f[c-w[i]] + v[i]); 时间复杂度:O(NC) 空间复杂度:降到了 O(C)

(3) 一维之下的一个常数优化
其实没有必要让循环下限为 0。 int bound, sumw=0; for (int i=1;i<=n;i++) { sumw+=w[i]; bound = max(C – sumw, w[i]);


本单元内容来自 dd_engi 的《背包九讲》。关于背包问题状态转移方程的具体解释可以在这本书中找到。

78

第七单元 背包专题 for (int c=C;c>=bound;c--) if (c>=w[i]) f[c] = max(f[c], f[c-w[i]] + v[i]); }

(4) 初始化时的细节
如果要求“恰好装满” ,那么初始化时应该让 f[0]=0,其他的 f[i]=-INF。这样就可以知道是否有解了。 如果不用“恰好” ,那么应该让 f 的所有元素都置 0。

7.3 完全背包问题
【问题描述】有 n 种物品和一个容量为 C 的背包。第 i 种物品的重量是 w[i],价值是 v[i],数量无限。求解 将哪些物品装入背包可使价值总和最大。

(1) 基本算法
1. 状态转移方程:f[i][c]=max{f[i-1][c-k×w[i]]+k×v[i]},0?k×w[i]?c 时间复杂度 O(C×

?

C ),比较大。 w[i]

2. 一个简单的优化:如果物品 i、j 满足 w[i]?w[j]且 v[i]?v[j],就可以把物品 j 去掉。 不过它不能改善最坏情况的复杂度(最坏情况:根本没有可以去掉的东西)。 3. 另一种优化:首先将重量大于 C 的物品去掉,然后使用类似桶排序或计数排序的方法,计算出费用相同的 物品中哪个价值最高。

(2) 更优的算法
// 内层的for和外层的for可以互换。 for (int i=1;i<=n;i++) for (int c=0;c<=C;c++) // 这里发生了变化——循环次序变了 if (c>=w[i]) f[c] = max(f[c], f[c-w[i]] + v[i]); 时间复杂度:O(NC)
?f[i-1][c] 转化为二维,状态转移方程就是:f[i][c]=max? (第二行变了) ?f[i][c-w[i]]+v[i]

7.4 多重背包问题
【问题描述】有 n 种物品和一个容量为 C 的背包。第 i 种物品的重量是 w[i],价值是 v[i],数量为 a[i]。求 解将哪些物品装入背包可使价值总和最大。 【分析】 二进制法:按照二进制分割物品。比方说,物品 i 有 13 个,就可以把它分成系数为 1、2、4、6,共 4 个 0/1 背包的物品。 (13=20+21+22+6) for (int i=1;i<n;i++) { if (w[i]*a[i]>C) { for (int c=0;c<=C;c++) // 如果物品够多,问题其实就是完全背包问题 // 完全背包 79

第七单元 背包专题 if (c>=w[i]) f[c] = max(f[c], f[c-w[i]] + v[i]); } else { int k=1, amount=a[i]; while (k<amount) { // 是否取一个重量为k×w[i],价值为k×v[i]的物品? for (int c=k*w[i];c>=0;c--) if (c>=w[i]) f[c] = max(f[c], f[c-w[i]] + k*v[i]); // 继续分割 amount-=k; k+=k; } // 把剩下的作为单独一个物品 for (int c=amount*w[i];c>=0;c--) if (c>=w[i]) f[c] = max(f[c], f[c-w[i]] + amount*v[i]); } } 时间复杂度:O(V×?logw[i])

7.5 二维费用的背包问题
【问题描述】有 n 件物品和一个容量为 C、容积为 U 的背包。第 i 件物品的重量是 w[i],体积是 u[i],价值 是 v[i]。求解将哪些物品装入背包可使价值总和最大。

(1) 0/1 背包的表示方法
费用加了一维,只需把状态也加一维。 1. 状态表示:设 f[i][c][u]为前 i 件物品付出两种代价分别为 c 和 u 时可以获得的最大价值。
?f[i-1][c][u] 2. 状态转移方程:f[i][c][u]=max? ?f[i-1][c-w[i]][u-u[i]]+v[i]

当然,为了节省空间,可以把 i 去掉。 3. 一个启示:当发现由熟悉的动态规划题目变形而来的题目时,在原来的状态中加一维以满足新的限制,这 是一种比较通用的方法。

(2) 限制物品总个数的 0/1 背包
【问题描述】有 n 件物品和一个容量为 C 背包。第 i 件物品的重量是 w[i],价值是 v[i]。现在要求转入背包 的物品个数不超过 M。求解将哪些物品装入背包可使价值总和最大。 只需把问题变一下——有 N 件物品和一个容量为 C、容积为 M 的背包。第 i 件物品的重量是 w[i],体积 是 1,价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。 把最大个数看做一种容积就可以了。

80

第七单元 背包专题

(3) 二维费用的完全背包和多重背包问题
循环时仍然按照完全背包(顺序循环)和多重背包(分割)的方法操作,只不过比完全背包和多重背包多 了一维。

(4) 二维费用背包的另一种解法
把背包的容量和费用看作一个复数。详见《背包九讲》 。

7.6 分组的背包问题
【问题描述】有 n 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i],价值是 v[i]。这些物品被划分 为 K 组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使价值总和最大。 1. 状态表示:设 f[k][c]为前 k 组物品花费 c 时可以获得的最大价值。
?f[k-1][c] 2. 状态转移方程:f[k][c]=max? ?f[k-1][c-w[i]]+v[i]

物品i属于第k组

注意循环的顺序。 for (int k=1;i<=K;i++) for (int c=C;c>=0;c--) for each (int i in 第k组) // 伪代码,指“for (所有属于组k的物品i)” if (c>=w[i]) f[c] = max(f[c], f[c-w[i]] + v[i]); 在“金明的预算方案”(NOIP2006,2)中,就可以把主件、附件组合成一个分组背包(一组最多 4 个物 体,最少 1 个物体)。

7.7 有依赖的背包问题
【问题描述】依赖关系以图论中“森林”的形式给出,也就是说,主件的附件仍然可以具有自己的附件集合, 限制只是每个物品最多只依赖于一个物品(只有一个主件)且不出现循环依赖。 1. 第一种思想:将每个主件及其附件集合转化为物品组。不过,由于附件可能还有附件,就不能将每个附件 都看作一个一般的 01 背包中的物品了。若这个附件也有附件集合,则它必定要被先转化为物品组,然后 用分组的背包问题,解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。 2. 第二种思想:每个父结点都需要对它的各个儿子的属性进行一次 DP 以求得自己的相关属性。 3. 第三种思想:这已经触及到了“泛化物品”的思想,你会发现这个“依赖关系树”每一个子树都等价于一 件泛化物品,求某结点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。

7.8 泛化物品
有这样一种物品,名字叫做泛化物品。有一个函数 h(x),当分配给物品的费用为 a 时,能得到的价值就是 h(a)。 实际上,前面总结的所有背包都可以看做泛化物品,只不过在某些时候 h 的值为 0。 如果面对两个泛化物品 h 和 l,要用给定的费用从这两个泛化物品中得到最大的价值,怎么求呢?事实上, 对于一个给定的费用 v,只需枚举将这个费用如何分配给两个泛化物品就可以了。同样的,对于 0~C 的每一个 整数 c,可以求得费用 c 分配到 h 和 l 中的最大价值 f(v): f(v)=max{h(k)+l(c-k)},0?k?c。 可以看到,f 也是一个由泛化物品 h 和 l 决定的定义域为 0~C 的函数,也就是说,f 是一个由泛化物品 h 81

第七单元 背包专题 和 l 决定的泛化物品,f 是 h 与 l 的和。这个运算的时间复杂度取决于背包的容量,是 O(V2)。 泛化物品的定义表明:在一个背包问题中,若将两个泛化物品代以它们的和,不影响问题的答案。事实上, 对于其中的物品都是泛化物品的背包问题,求它的答案的过程也就是求所有这些泛化物品之和的过程。设此和 为 s,则答案就是 s[V]中的最大值。 一般而言,求解背包问题,即求解这个问题所对应的一个函数,即该问题的泛化物品。而求解某个泛化物 品的一种方法就是将它表示为若干泛化物品的和然后求之。

7.9 混合背包问题
【问题描述】还是背包问题,不过有的物品只能取一次(0/1 背包),有的可以取无限次(完全背包),有的 只能取有限次(多重背包)。怎么解决? 由于我们按物品划分阶段,所以没有必要想太多。下面给出伪代码: for (int i=1; i<N; i++) // 不变 if (物品i属于0/1背包) { // 按照0/1背包的做法取物品i for (int c=C;c>=0;c--) if (c>=w[i]) f[c] = max(f[c], f[c-w[i]] + v[i]); } else if (物品i属于完全背包) { // 按照完全背包的做法取物品i for (int c=0;c<=C;c++) if (c>=w[i]) f[c] = max(f[c], f[c-w[i]] + v[i]); } else if (物品i属于多重背包) { // 按照多重背包的做法取物品i ?? }

7.10 特殊要求
(1) 输出字典序最小的最优方案
这里“字典序最小”的意思是 1 ~N 号物品的选择方案排列出来以后字典序最小。 一般而言,求一个字典序最小的最优方案,只需要在转移时注意策略:以 0/1 背包为例。在某一阶段,两 种决策的结果相同,就应该按照前者来输出方案。

(2) 求方案总数
以 0/1 背包为例。它的状态转移方程为 f[i][c]=max?
?f[i-1][c] ?f[i-1][c-w[i]]+v[i]

除了可以求可得到的最大价值外,还可以得到装满背包或将背包装至某一指定容量的方案总数。 只需把状态转移方程中的 max 改成 sum (求和) , 并将初始条件设为 f[0][0]=1, 就可以通过 f[n-1][C] 求出方案总数。 事实上,这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案。 82

第七单元 背包专题

(3) 最优方案的总数
这里的最优方案是指物品总价值最大的方案。以 01 背包为例。 结合求最大总价值和方案总数两个问题的思路,最优方案的总数可以这样求:开一个数组 g[i][c],表示 这个子问题的最优方案的总数。在求 f[i][c]的同时,顺便就把 g[i][c]带下来了。 代码如下: for (int i=1;i<=n;i++) for (int c=0;c<=C;c++) { f[i][c]=f[i-1][c]; if (c>=w[i]) f[i][c] = max(f[i][c], f[i-1][c-w[i]] + v[i]); g[i][c]=0; if (f[i][c]==f[i-1][c]) g[i][c] += g[i-1][c]; if (f[i][c] == (f[i-1][c-w[i]] + v[i])) g[i][c] += g[i-1][c-w[i]] + v[i]; // 注:如果两个状态的值相等,那么计算g时应该把两部分都算进去。这就是必须单独求g的原因。 }

(4) 求次优解、第 K 优解
对于求次优解、第 K 优解类的问题,如果相应的最优解问题能写出状态转移方程、用动态规划解决,那么 求次优解往往可以相同的复杂度解决,第 K 优解则比求最优解的复杂度上多一个系数 K。 其基本思想是将每个状态都表示成有序队列,将状态转移方程中的 max/min 转化成有序队列的合并。
?f[i-1][c] ① 以 0/1 背包为例。0/1 背包的状态转移方程为 f[i][c]=max? 。如果要求第 ?f[i-1][c-w[i]]+v[i] ②

K 优解,那么状态 f[i][c]就应该是一个大小为 K 的数组 f[i][c][K+1]。其中 f[i][c][k]表示前 i 个物品、 背包大小为 c 时,第 k 优解的值。显然可以认为 f[i][c][K+1]是一个有序队列。 然后可以说: f[i][c]这个有序队列是由①、 ②这两个有序队列合并得到的。 有序队列①即 f[i-1][c][K], ②则理解为在 f[i-1][c-w[i]][K]的每个数上加上 v[i]后得到的有序队列。合并这两个有序队列并将结果 的前 K 项储存到 f[i][c][K+1]中的复杂度是 O(K)。最后的答案是 f[N][C][K]。总的复杂度是 O(CNK)。 实际上,一个正确的状态转移方程的求解过程已经覆盖了问题的所有方案。只不过由于是求最优解,所以 其它达不到最优的方案都被忽略了。因此,上面的做法是正确的。 另外,要注意题目对于“第 K 优解”的定义,将策略不同但权值相同的两个方案是看作同一个解还是不同 的解。如果是前者,则维护有序队列时要保证队列里的数没有重复的。

7.11 背包问题的搜索解法
(1) 代码
对于 0/1 背包问题,简单的深搜的复杂度是 O(2n)。就是枚举出所有 2n 种将物品放入背包的方案,然后 找最优解。代码如下(调用 try(1,0,0)即可): int max=0; void try(int i, int curw, int curv) { if (i>n) // i是当前物体,curw是当前重量,curv是当前的价值

83

第七单元 背包专题 { if (curv > max) max = curv; return; } if (curw + w[i] <= C) try(i+1, curw + w[i], curv + v[i]); try(i+1, curw, curv); }

(2) 预处理和剪枝
预处理:在搜索中,可以认为顺序靠前的物品会被优先考虑。 所以,可以利用贪心的思想,将更有可能出现在结果中的物品的顺序提前,可以较快地得出贪心的较优解, 也更有利于最优性剪枝。这需要按照“性价比”(权值/费用)来排列搜索顺序。 另一方面,若将费用较大的物品排列在前面,可以较快地填满背包,有利于可行性剪枝。 最后一种可以考虑的方案是:在开始搜索前将给定的物品的顺序打乱。这样可以避免命题人设置的陷阱。 可行性剪枝:即判断按照当前的搜索路径搜下去能否找到一个可行解,例如:若将剩下所有物品都放入背 包仍然无法将背包充满(设题目要求必须将背包充满),则剪枝。 最优性剪枝:即判断按照当前的搜索路径搜下去能否找到一个最优解,例如:若加上剩下所有物品的权值 也无法得到比当前得到的最优解更优的解,则剪枝。

(3) 搜索还是 DP
在看到一道背包问题时,应该用搜索还是动态规划呢? 如果一个背包问题可以用动态规划求解,V 一定不能很大,否则 O(VN)的算法无法承受,而一般的搜索解 法都是仅与 N 有关,与 V 无关。 所以,V 很大时,应该优先考虑搜索;N 较大时,应该优先考虑动态规划。 另外,当想不出合适的动态规划算法时,就只能用搜索了。

7.12 子集和问题
【问题描述】给定一个整数的集合 S 和一个整数 X,问是否存在 S 的一个子集满足其中所有元素的和为 X。 【分析】 子集和问题是一个 NPC 问题,与 0/1 背包问题并不相同。 这个问题有一个时间复杂度为 O(2N/2)的较高效的搜索算法,其中 N 是集合 S 的大小。 第一步思想是二分。将集合 S 划分成两个子集 S1 和 S2,它们的大小都是 N/2。对于 S1 和 S2,分别枚举出 它们所有的 2N/2 个子集和,保存到某种支持查找的数据结构中(如散列表)。然后就要将两部分结果合并,寻 找是否有和为 X 的 S 的子集。 事实上,对于 S1 的某个和为 X1 的子集,只需寻找 S2 是否有和为 X-X1 的子集。假设采用的散列表是理想 的,每次查找和插入都仅花费 O(1)的时间。两步的时间复杂度显然都是 O(2N/2)。 实践中,往往可以先将第一步得到的两组子集和分别排序,然后再用两个指针扫描的方法查找是否有满足 要求的子集和。这样的实现,在可接受的时间内可以解决的最大规模约为 N=42。

84

第八单元 排序算法

第八单元

排序算法

8.1 常用排序算法
(1) 使用 STL 算法!
平均时间:O(nlogn) 头文件:<algorithm> ① 调用方法:sort(第一项的地址, 最后一项的地址+1); 如 sort(&a[0],&a[n]);或 sort(a,a+n); 注意,STL 的区间是左闭右开区间。 ② 自定义规则的排序:有时排序的条件不止一个,或不方便对原数据进行排序,就需要自定义比较规则。 这时需要建立一个函数,把“小于”解释明白。例如: bool cmp(const int &i, const int &j) {return w[i]<w[j];} // 自定义比较规则 ?? sort(a, a+n, cmp); cmp 要讲清 a[i]和 a[j]的比较方法。 对于上面的代码, 就是 “如果 w[i]<w[j], 那么 a[i]就排在 a[j] 的前面”。

(2) 快速排序!
平均时间:O(nlogn) 快速排序俗称“快排”,是基于比较的排序算法中最快的一种算法。 void quicksort(int *a, int start, int end) { int low=start, high=end; int temp, check=a[start]; // 划分:把比check小的数据放到它的左边,把比check大的数放到它的右边。 do { while (a[high]>=check&&low<high) high--; // 注意,不要写成“low<=high”! if (a[high]<check) temp=a[high], a[high]=a[low], a[low]=temp; while (a[low]<=check&&low<high) low++; // 注意,不要写成“low<=high”! if (a[low]>check) temp=a[high], a[high]=a[low], a[low]=temp; } while (low!=high); a[low]=check; low--,high++; // 递归:对已经划分好的两部分分别进行快速排序 if (low>start) quicksort(a, start, low); 85

第八单元 排序算法 if (high<end) quicksort(a, high, end); } 快速排序的版本很多,上面只是众多版本中的一种。 快速排序的三个优化方法: 1. 规模很小时(如 end-start<10),使用插入排序代替快速排序。 2. 使用栈模拟递归。 3. 极端数据(如比较有序的数组)会使快速排序变慢,甚至退化为冒泡排序。可以采用“三者取中法” 来解决这个问题:令 check 等于 a[start]、a[end]、a[(start+end)/2]中的中间值。 第三种方法可以消除坏数据(基本有序的数据,它可以使快速排序退化为 O(n2)时间)对排序的影响。

(3) 归并排序
时间复杂度:O(nlogn) 注意: 1. 其他排序算法的空间复杂度是 O(1),而归并排序的空间复杂度很大,为 O(n)。 2. 下面的 end 是“末尾索引+1” ,即数列末尾要留一个空位。 int temp[N]; void mergesort(int *a, int start, int end) { if (start+1>=end) return; // 划分阶段、递归 int mid = start+(end-start)/2; mergesort(a, start, mid); mergesort(a, mid, end); // 将mid两侧的两个有序表合并为一个有序表。 int p=start,q=mid,r=start; while (p<mid || q<end) if (q>=end || (p<mid && a[p]<=a[q])) temp[r++]=a[p++]; else temp[r++]=a[q++]; for (p=start;p<end;p++) a[p]=temp[p]; } 在(end-start)不太大时,可以用插入排序代替归并排序。 归并排序还有另一种写法:开始复制的时候,把第二个子数组中元素的顺序颠倒了一下。 int temp[N]; // “临时安置点” void mergesort(int *a, int start, int end) { if (start==end) return; int mid = start+(end-start)/2; mergesort(a, start, mid); mergesort(a, mid, end);

86

第八单元 排序算法 // 合并 for (int i=mid; i>=start; i--) temp[i]=a[i]; for (int j=1;j<=end-mid;j++) temp[end-j+1]=a[j+mid]; for (int i=start,j=end,k=start; k<=end; k++) if (temp[i]<temp[j]) a[k]=temp[i++]; else a[k]=temp[j--]; } 在(end-start)不太大时,也可以用插入排序代替归并排序。

8.2 简单排序算法
以下三种排序算法的时间复杂度是 O(n2)。在这三种排序算法中,比较好的是插入排序。

(1) 插入排序!
基本思想:假设前 i 个元素已经排好序,然后把第 i+1 个元素插入到合适的位置上。 void ins_sort(int *a, int start, int end) { int j,k; for (int i=start+1; i<end; i++) { for (k=a[i],j=i-1; k<a[j] && j>=start; j--) a[j+1]=a[j]; a[j+1]=k; } }

(2) 选择排序!
基本思想:处理第 i 个元素时,找到它后面所有数的最小值。如果这个最小值比它小,就互相交换。 void swap_sort(int *a, int start, int end) { int temp; for (int i=start; i<end; i++) for (int j=i+1; j<end; j++) if (a[i]>a[j]) temp=a[i],a[i]=a[j],a[j]=temp; }

(3) 冒泡排序!
基本思想:对相邻两个元素进行比较,并将较小的数放到前面。重复 n 组即可完成排序。 void bubble_sort(int *a, int start, int end) { int temp; for (int i=start; i<end; i++) 87

第八单元 排序算法 for (int j=end; j>i; j--) // 从start到i,在“冒泡”过程中,元素已经排好序。 if (a[j-1]>a[j]) temp=a[j-1], a[j-1]=a[j], a[j]=temp; }

8.3 线性时间排序
以下几种排序算法的时间复杂度为 O(n),因为它们使用的是基于数字本身的排序。

(1) 桶排序!
基本思想:设计 M 个桶,根据元素本身进行分配。因为 M 个桶是按顺序排列的,所以分配元素之后元素 也会按顺序排列。 待排序的数据范围不太大时可以考虑这样排序 (比如 1~1000 可以考虑, 而 1~100000 就必须用快速排序) 。 下面假设每个数都位于区间[1, M]。 int cnt[M]; memset(cnt,0,sizeof(cnt)); for (int i=0; i<N; i++) cnt[a[i]]++; // 从cnt[0]开始挨个列举就行了。例如 for (int i=0; i<M; i++) while ((cnt[i]--)>0) cout<<i<<" ";

(2) 计数排序
基本思想: 对于序列中的每一元素 x,确定序列中小于 x 的元素的个数。 下面假设每个数都位于区间[1, m]。 int a[N], b[N], cnt[M]; ?? memset(cnt,0,sizeof(cnt)); for (int i=0;i<n;i++) cnt[a[i]]++; for (int i=1;i<M;i++) cnt[i]+=cnt[i-1]; for (int i=n-1;i>0;i--) { b[cnt[a[i]]] = a[i]; cnt[a[i]]--; } // 输出结果 for (int i=0;i<n;i++) cout<<b[i]<<' ';

(3) 基数排序*
基本思想:对 n 个元素依次按 k,k-1,...1 位上的数字进行桶排序。 int tmp[N], cnt[10]; int n; int maxbit(int *data, int n) { 88 // 辅助函数,求数据的最大位数

第八单元 排序算法 int d = 1; int p =10; for (int i = 0;i < n; i++) while (data[i] >= p) p *= 10, d++; return d; } void radixsort(int *data, int n) { int d = maxbit(data,n); int i,j,k; int radix = 1; for (i = 1; i<= d;i++) { for (j = 0;j < 10;j++) cnt[j] = 0; for (j = 0;j < n; j++) { k = (data[j]/radix)%10; cnt[k]++; } for (j = 1;j < 10;j++) cnt[j] = cnt[j-1] + cnt[j]; for (j = n-1;j >= 0;j--) { k = (data[j]/radix)%10; cnt[k]--; tmp[cnt[k]] = data[j]; } for (j = 0;j < n;j++) data[j] = tmp[j]; radix = radix*10; } } // 将tmp中的位置依次分配给每个桶 // 将所有桶中记录依次收集到tmp中 // 基数排序 // 保存最大的位数

// 进行d次排序

// 每次分配前清空计数器

// 统计每个桶中的记录数

// 将临时数组的内容复制到data中

8.4 使用二叉树的排序算法*
(1) 二叉树排序
有关二叉排序树的代码参见 106 页“10.4 二叉排序树” 。 二叉树排序的步骤很简单,就是先把每个元素插入到 BST 中,然后中序遍历。 时间复杂度:O(nlogn) 应该清楚地认识到,因为二叉排序树很容易变得不平衡,并且它的空间占用比较大,插入结点也要花费一 些时间,所以,二叉树排序比快速排序慢很多。 使二叉排序树不平衡的方法:数据基本有序,BST 退化成长长的链表;或数据使 SBT 形成堆积的“人”字 形。

89

第八单元 排序算法

(2) 堆排序
有关堆的代码参见 108 页“10.5 堆和优先队列*” 。使用最大值堆,因为这样做可以不占用额外的空间。 堆排序的步骤也不难。操作方法如下: ① 将整个数组转化为一个堆(使用 buildheap 完成) 。 ② 将堆顶的最大元素取出 (removemax) , 并把它放到数组的最后 (准确的说, 位置是堆中元素个数减 1) 。 ③ 剩余元素重新建堆。 ④ 重复②,直到堆为空。 时间复杂度:O(nlogn) 堆排序与其他 O(nlogn)的排序算法相比要慢很多。堆排序适用于寻找第 k 大(小)元素。

8.5 小结
搜索算法的比较: 1. 稳定性 插入排序、冒泡排序、二叉树排序、归并排序及其他线性时间排序是稳定的; 选择排序、希尔排序(《资料》里没有总结)、快速排序、堆排序是不稳定的。 2. 时间复杂度 插入排序、冒泡排序、选择排序的时间复杂度为 O(n2); 其它非线性时间排序的时间复杂度为 O(nlogn); 线性时间排序的时间复杂度为 O(n)。 3. 辅助空间 线性时间排序、归并排序的辅助空间为 O(n),其它排序的辅助空间为 O(1)。 4. 其它方面 插入、冒泡排序的速度较慢,但参加排序的序列局部或整体有序时,这种排序能达到较快的速度。在这种 情况下,快速排序反而慢了。 当 n 较小时,对稳定性不作要求时宜用选择排序,对稳定性有要求时宜用插入或冒泡排序。若待排序的记 录的关键字在一个明显有限范围内时,且空间允许是用桶排序。 当 n 较大时,关键字元素比较随机,对稳定性没要求宜用快速排序。 当 n 较大时,关键字元素可能出现本身是有序的,对稳定性有要求时,空间允许的情况下,宜用归并排序。 当 n 较大时,关键字元素可能出现本身是有序的,对稳定性没有要求时宜用堆排序。

90

第九单元 基本数据结构

第九单元

基本数据结构

9.1 线性表(顺序结构)
线性表可以用普通的一维数组存储。 你可以让线性表可以完成以下操作(代码实现很简单,这里不再赘述): 1. 返回元素个数。 2. 判断线性表是否为空。 3. 得到位置为 p 的元素。 4. 查找某个元素。 5. 插入、删除某个元素:务必谨慎使用,因为它们涉及大量元素的移动。

9.2 线性表(链式结构)
(1) 单链表!
1. 定义:下面有一个空链表,表头叫 head,并且表内没有任何元素。 struct node { int value; node *next; } arr[MAX]; int top=-1; node *head = NULL; 2. 内存分配:在竞赛中不要用 new,也不要用 malloc、calloc——像下面一样做吧。 #define NEW(p) p=&arr[++top];p->value=0;p->next=NULL node *p; NEW(head); // 初始化表头 NEW(p); // 新建结点 3. 插入:把 q 插入到 p 的后面。时间复杂度 O(1)。 if (p!=NULL && q!=NULL) // 先判定是否为空指针。如果不是,继续。 { q->next=p->next; p->next=q; } 4. 删除:把 p 的下一元素删除。时间复杂度 O(1)。 if (p!=NULL && p->next!=NULL) // 先判定是否为空指针。如果不是,继续。 { node *q=p->next; p->next=q->next; // delete(q); } 5. 查找或遍历:时间复杂度 O(n)。 node *p=first; while (p!=NULL) { // 处理value 91 // 如果使用动态内存分配,最好将它的空间释放。

第九单元 基本数据结构 // cout<<p->value<<'\t'; p=p->next; }

(2) 静态链表
指针的作用就是存储地址。如果我们找到了替代品,就可以放弃指针了。 需要把上面的定义改一下: struct node { int value; int next; } arr[MAX]; // 表示下一元素在arr中的下标

(3) 循环链表
和单链表有一个重大区别:单链表最后一个元素的 next 指向 NULL,而循环链表最后一个元素的 next 指向 first。 遍历时要留心,不要让程序陷入死循环。 一个小技巧:如果维护一个表尾指针 last,那么就可以在 O(1)的时间内查找最后一个元素。同时可以防 止遍历时陷入死循环。

(4) 双链表
1. 定义:下面有一个空链表,表头叫 first。 struct node { int value; node *next, *prev; } arr[MAX]; int top=-1; node *first = NULL; // 根据实际需要可以维护一个表尾指针last。 2. 内存分配:最好不要使用 new 运算符或 malloc、calloc 函数。 #define NEW(p) p=arr+(++top);p->value=0;p->next=NULL;p->prev=NULL node *p; NEW(head); // 初始化表头 NEW(p); // 新建结点 3. 插入:把 q 插入到 p 的后面。时间复杂度 O(1)。 if (p==NULL||q==NULL) // 先判定是否为空指针。如果不是,继续。 { q->prev=p; q->next=p->next; q->next->prev=q; p->next=q; } 4. 删除:把 p 的下一元素删除。时间复杂度 O(1)。 if (p==NULL||p->next==NULL) // 先判定是否为空指针。如果不是,继续。 { 92

第九单元 基本数据结构 node *q=p->next; p->next=q->next; q->next->prev=p; // delete(q); } 5. 查找或遍历:从两个方向开始都是可以的。 // 如果使用动态内存分配,最好将它的空间释放。

(5) 将元素插入到有序链表中*
void insert(const node *head, node *p) { node *x, *y; y=head; do { x=y; y=x->next; } while ((y!=NULL) && (y->value < p->value); x->next=p; p->next=y; }

9.3 栈
(1) 栈的实现!
1. 2. 3. 4. 操作规则:先进后出,先出后进。 int stack[N], top=0; // top 表示栈顶位置。 入栈:inline void push(int a) { stack[top++]=a; } 出栈:inline int pop() { return stack[--top]; } 栈空的条件:inline bool empty() { return top<0; }

如果两个栈有相反的需求,可以用这种方法节省空间:用一个数组表示两个栈。分别用 top1、top2 表示 栈顶的位置,令 top1 从 0 开始,top2 从 N-1 开始。

(2) DFS 和栈
递归其实也用到了栈。每调用一次函数,都相当于入栈(当然这步操作“隐藏在幕后” ) 。函数调用完成, 相当于出栈。 一般情况下,调用栈的空间大小为 16MB。也就是说,如果递归次数太多,很容易因为栈溢出导致程序崩 溃,即“爆栈” 。 为了防止“爆栈” ,可以将递归用栈显式实现。如果可行,也可以改成迭代、递推等方法。 使用栈模拟递归时,注意入栈的顺序——逆序入栈,后递归的要先入栈,先递归的要后入栈。 下面是非递归版本的 DFS 模板: stack <int> s; // 存储状态 void DFS(int v, ?) { s.push(v); // 初始状态入栈 93

第九单元 基本数据结构 while (!s.empty()) { int x = s.top(); s.pop(); // 处理结点 if (x达到某种条件) { // 输出、解的数量加1、更新目前搜索到的最优值等 ? return; } // 寻找下一状态。当然,不是所有的搜索都要这样寻找状态。 // 注意,这里寻找状态的顺序要与递归版本的顺序相反,即逆序入栈。 for (i=n-1;i>=0;i--) { s.push(? /*i对应的状态*/); } } // 无解 cout<<"No Solution."; } // 获取状态

9.4 队列
(1) 顺序队列!
1. 2. 3. 4. 操作规则:先进先出,后进后出。 定义:int queue[N], front=0, rear=0; front 指向队列首个元素,rear 指向队列尾部元素的右侧。 入队:inline void push(int a) { queue[rear++]=a; } 出队:inline int pop() { return queue[front++]; } 队空的条件:inline bool empty() { return front==rear; }

(2) 循环队列!
1. 2. 3. 4. 循环队列——把链状的队列变成了一个环状队列。与上面的链状队列相比,可以节省很大空间。 定义:int queue[N], front=0, rear=0; front 指向队列首个元素,rear 指向队列尾部元素的右侧。 入队:inline void push(int a) { queue[rear]=a; rear=(rear+1)%N; } 出队:inline int pop() { int t=queue[front]; front=(front+1)%N; return t; } 队满或队空的条件:inline bool empty() { return front==rear; } 队满和队空都符合上述条件。怎么把它们区分开呢? 第一种方法:令队列的大小是 N+1,然后只使用 N 个元素。这样队满和队空的条件就不一样了。 第二种方法:在入队和出队同时记录队列元素个数。这样,直接检查元素个数就能知道队列是空还是满。

94

第九单元 基本数据结构

(3) BFS 和队列
BFS 要借助队列来完成,并且,将队列改成堆栈,BFS 就变成了 DFS。BFS 的具体实现见 42 页“3.7 代 码模板” 。

9.5 二叉树
(1) 二叉树的链表存储法!
struct node { int value; node *leftchild, *rightchild; //int id; // 结点编号。 //node *parent; // 指向父亲结点。 } arr[N]; int top=-1; node * head = NULL; #define NEW(p) p=&arr[++top]; p->leftchild=NULL; p->rightchild=NULL; p->value=0

\

(2) 完全二叉树的一维数组存储法!
0 1 3 7 8 9 4 5 2 6

如果一个二叉树的结点严格按照从上到下、从左到右的顺序填充,就可以用一个一维数组保存。 下面假设这个树有 n 个结点,待操作的结点是 r(0?r<n) 。 操作 r 的父亲 r 的左儿子 r 的右儿子 r 的左兄弟 r 的右兄弟 判断 r 是否为叶子 宏定义 #define parent(r) #define leftchild(r) #define rightchild(r) #define leftsibling(r) #define rightsibling(r) #define isleaf(r) r 的取值范围 (((r)-1)/2) ((r)*2+1) ((r)*2+2) ((r)-1) ((r)+1) ((r)>=n/2) r≠0 2r+1<n 2r+2<n r 为偶数且 0<r?n-1 r 为奇数且 r+1<n r<n

(3) 二叉树的遍历!
1. 前序遍历 void preorder(node *p) { 95

第九单元 基本数据结构 if (p==NULL) return; // 处理结点p cout<<p->value<<' '; preorder(p->leftchild); preorder(p->rightchild); } 2. 中序遍历 void inorder(node *p) { if (p==NULL) return; inorder(p->leftchild); // 处理结点p cout<<p->value<<' '; inorder(p->rightchild); } 3. 后序遍历 void postorder(node *p) { if (p==NULL) return; postorder(p->leftchild); postorder(p->rightchild); // 处理结点p cout<<p->value<<' '; } 假如二叉树是通过动态内存分配建立起来的,在释放内存

相关文章:
NOIP复习资料(C++版)
NOIP复习资料(C++版)_学科竞赛_高中教育_教育专区。noip 前言NOIP 复习资料(C++版) 主 编 葫芦岛市一高中 李思洋 完成日期 2012 年 8 月 27 日 0 前言 前言...
NOIP复习资料
160 X NOIP 复习资料(C++版) 第一单元 程序设计基础 1.1 基本数据类型名称 int unsigned int* char unsigned char short** unsigned short long long unsigned...
noip复习资料(提高组c++版)
前言NOIP 复习资料(C++版) 主 编 葫芦岛市一高中 李思洋 完成日期 2012 年 8 月 27 日 0 前言 前言 有一天,我整理了 NOIP 的笔记,并收集了一些经典算法。...
C++个人复习资料
C++个人复习资料_IT认证_资格考试/认证_教育专区。C/C++学习总结,精辟,通俗易懂 C++复习大纲 #类中每个非静态成员函数内部隐含有 this,构造和析构也是有的。this...
C++复习资料
C++复习资料_IT认证_资格考试/认证_教育专区。c++复习资料 一、选择题 1. 对于拷贝初始化构造函数和赋值操作的关系,正确的描述是( C ) A. 拷贝初始化构造函数...
c++复习资料及答案
C++复习资料及答案 一、 判断题 1、在变量定义 int sum , SUM; 中 sum 和 SUM 是两个相同的变量名。 (N ) 2、字符串”china”在内存中占据的存储...
c++复习资料
c++复习资料_计算机软件及应用_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档c++复习资料_计算机软件及应用_IT/计算机_专业资料。一、考试题型: 1、选择...
C++复习资料
C++复习资料_IT认证_资格考试/认证_教育专区。昆明理工复习资料C++语言程序设计复习题 一 、单项选择题 1. 在以下标识符中,合法的标识符是 ( C ) A.0_t B...
c++复习资料及答案
c++复习资料及答案_从业资格考试_资格考试/认证_教育专区。复习资料C++复习资料及答案一、 判断题 1、在变量定义 int sum , SUM; 中 sum 和 SUM 是两...
c++复习资料及答案
c++复习资料及答案_工学_高等教育_教育专区。《C++复习资料及答案一、 判断题 1、在变量定义 int sum , SUM; 中 sum 和 SUM 是两个相同的变量名。 (N ...
更多相关标签: