当前位置:首页 >> 计算机软件及应用 >>

NOIP复习资料



重要说明: 1. 《资料》没有完全编完。不过,重要的东西已经编完了。 如果遇到 Pascal 程序, 或者未经过认真排版的内容, 说明它们是没有完 成的、不太重要的内容。打印之前注意处理。 当然,最好不要打印。 2. 很多程序并没有经过认真的调试。学习、套用时务必谨慎! 3. 请使用“工具”菜单下的“修订”功能修改《资料》 ,并及时将修改后的 文档交给主编,以便于编者的修改和完善。 4. 从陶立强同学那里淘到很多好东西, 所以在本学期资料很可能编不完了。

NOIP 复习资料
(C++版)





李思洋 赵宏祝 1.0 Alpha 2(2012.4.15)

审 读 文档版本

葫芦岛市第一高级中学

NOIP 复习资料(C++版) - 目录

前言
本资料始于一本信息学的笔记。最初我并没有考虑编写资料,不过,我觉得应该把常用的代码总结一下,所 以就在网络资料《信息学奥林匹克竞赛辅导教程》上找了一些算法,比如说 Dijkstra,写到了笔记本上。 虽然资料是用 Pascal 语言写的,但是没关系——我了解一些 P 的代码,整理笔记时可以翻译。于是我完 成了一本 C++笔记。 考虑到笔记的内容有些乱,不方便与同校同学共享,我决定用 Word 编写一份电子版的资料。 NOIP 复习资料有很多,可惜都是 Pascal 语言的,并且存在着“太乱” 、内容少等问题。由于这个原因, 我决定努力编写一本令人满意的 C++复习资料。 《资料》内容很多,已经远远超过了我的那本笔记。原因很简单,就是我编写资料的时候,从网络资料中吸 收了很多东西,包括那些 Pascal 语言的复习资料。 1. 读者对象 本《资料》不是教程。所以对读者的要求不低。读者应该具备以下几个条件: 1. 有学习信息学奥赛的欲望。 2. 学习 C++语言(注意,不是 C!,能够较快地读懂 C++代码,并熟练地使用 C++编写程序。 ) 3. 事先已经理解一些概念性的东西(如“连通图”。 ) 4. 有举一反三、触类旁通的能力,以及较强的自学能力。 5. 有学习、引用或背诵现成代码的需要。 符合以下几个条件的读者最好不要阅读《资料》 : 1. 没有学过 C++语言,对竞赛知识不甚了解。 2. 没有时间和精力学习信息学,甚至没有可用于学习的电脑。 3. 感觉 NOIP 像玩一样容易。 4. 自己已经有一套复习资料。 (不同的人编程习惯也不同,资料看太多,会“学杂了”的) 2. 结构 《资料》不是教程,所以没有必要循序渐进地学习。遇到需要的,应该学习、理解,或者干脆背下来。 第一单元:对我们平时不太注意的语言知识做一个总结,同时介绍了一些和 OI 有关的信息。 第二单元~第六单元:总结了常用算法和一些经典问题。我认为,这些程序都应该掌握,最好熟练掌握。 第七、八单元:总结了几个排序算法和查找算法。其实没有必要全部学会——掌握简单、常用的即可。 第九单元:介绍了常用的数据结构。此外,读者可以忽略“线段树” 。 第十单元:高精度算法。这里的代码是经过多次调试的,是正确的。我建议大家使用这种写法,并且把高精 度加法、减法、乘法背下来。 第十一单元:虽然叫“常用数学知识” ,但是没有必要较真。这里的计算几何不同于 NOI 的计算几何——主 要目的是拓展高中的数学知识。 第十二单元:需要一些数学的“感觉” 。 第十三单元:常用的图论算法。如果感觉有用,最好把它们直接背下来。NOIP 是不允许携带代码模板的。 附录 A:看完之后有收获,编写的目的就达到了。 附录 B:有关 DEBUG 的知识,一定要熟练。 附录 C:和竞赛本身有关。竞赛之前看一眼就行了。 附录 D:NOIP 竞赛大纲,看一眼就行了。 附录 E:很多资料都是用 Pascal 语言写的。附录 E 的目的是帮读者把 Pascal 语言的程序看懂,并尝试 翻译成 C 语言。 附录 F:参考文献。 附录 G:我家没有网,所以不知道网站里有什么。有兴趣的话,可以自己看看。

I

NOIP 复习资料(C++版) - 目录 3. 前提 首先,你需要一台电脑,还要有 C++编译器。 如果使用 Linux 系统, 那么系统会自带 C++编译器。 可以选择一个 IDE, Anjuta, Code::Blocks。 如 或 如果使用 Windows 系统,你需要自己安装 C++编译器。如果安装 DEV-C++,那么它会自带一个编译器。 如果不使用 DEV-C++,你需要下载 MinGW 编译器。 最好不要使用 Visual C++,因为它必须要建立工程才能编译程序,很麻烦的。 4. 习惯 下面是我个人的一些习惯: 1. 能使用链表就使用链表。当然,因为是竞赛,所以不使用动态内存分配。 2. 尽可能用 STL。尽管慢一点点,但是可读性好。 3. 数组下标不一定 0 开始。读代码之前应该仔细确认,防止发生混乱。 4. 经常用 C++资料中没有的“>?”“<?”“>?=”“<?=”运算符(感谢刘汝佳的书) 、 、 、 。 5. 重要说明 NOIP 不允许携带代码模板,所以不要尝试把资料的打印版本或电子版本带入竞赛场地。如果需要使用某种 算法,就应该事先把它背熟,而不是打小抄。 由于我的学习任务繁重,以及编辑时比较匆忙,里面有很多程序还未仔细调试。所以学习代码之前一定先调 试,套用代码时务必谨慎!

II

NOIP 复习资料(C++版) - 目录

目录
说明: 标“*”表示内容在 NOIP 中很少涉及,或者说“有点偏” ; 标“**”表示内容是 NOI 及以上范围的。这里只是为了实用才介绍。

第一单元

程序设计基础 .................................................. 1
1 1 1 2 2 2 3 3 4 4 4 5 5 6 6 6 6 7 7 7 8 8 8 9

1.1 基本数据类型 ............................................................ 1.2 运算符 ................................................................. (1) 常见运算符的优先级..................................................... (2) 使用提示 ............................................................. 1.3 输入和输出 .............................................................. (1) 使用标准输入/输出 ..................................................... (2) 使用流输入/输出 ....................................................... 1.4 其他常用操作 ............................................................ 1.5 字符串操作* ............................................................. (1) 使用字符数组.......................................................... (2) 使用字符串类.......................................................... 1.6 文件操作 ............................................................... (1) 使用输入/输出重定向操作 ................................................ (2) 使用流输入/输出文件.................................................... (3) 使用文件指针.......................................................... 1.7 简单的算法分析和优化 ..................................................... (1) 时间复杂度 ........................................................... (2) 空间复杂度 ........................................................... (3) 常用算法的时空复杂度 ................................................... (4) 简单的优化方法 ........................................................ 1.8 写给没有参加过 NOIP 的同学 ................................................. (1) NOIP 和设计竞赛的区别 .................................................. (2) 常用语 .............................................................. 1.9 IDE ...................................................................

1.10 小结 .................................................................. 9

第二单元

搜索 ........................................................ 10
10 10 11 12 13 13 13 13 14 14 15 16

2.1 N 皇后问题 ............................................................. (1) 深度优先搜索(DFS) .................................................. (2) 位运算加速 .......................................................... 2.2 骑士覆盖问题 ........................................................... (1) 广度优先搜索(BFS) .................................................. (2) 迭代加深搜索*........................................................ 2.3 DFS 产生全排列和组合(无重集元素) ......................................... (1) 排列 ............................................................... (2) 组合 ............................................................... 2.4 走迷宫 ................................................................ (1) DFS ............................................................... (2) BFS ...............................................................

2.5 8 数码问题 ............................................................. 17 (1) BFS ............................................................... 17

III

NOIP 复习资料(C++版) - 目录 (2) 广度优先双向搜索** ................................................... (3) 启发式搜索(A*算法)** ................................................ 2.6 图论模型 .............................................................. (1) 倒水问题 ............................................................ (2) 过河问题 ............................................................ (3) 另一个过河问题 ....................................................... 2.7 模板 .................................................................. (1) DFS 模板............................................................ (2) BFS 模板............................................................ (3) DFS 和 BFS 的比较 .................................................... 2.8 剪枝 .................................................................. 2.9 小结 .................................................................. 19 21 23 23 23 23 24 24 24 25 25 25

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

贪心算法 ..................................................... 26
部分背包问题 ........................................................... 乘船问题 .............................................................. 选择不相交区间 ......................................................... 区间选点问题 ........................................................... 区间覆盖问题 ........................................................... 删数问题 .............................................................. 工序问题 .............................................................. 种树问题 .............................................................. 马跳棋盘问题* .......................................................... 小结 ................................................................. 26 26 26 26 26 27 27 27 27 29

第四单元

分治算法 ..................................................... 31
31 31 31 31 31 32 33 33 34

4.1 快速排序、归并排序 ...................................................... 4.2 二分查找 .............................................................. 4.3 快速幂 ................................................................ (1) 递归算法 ............................................................ (2) 非递归算法 .......................................................... 4.4 最长非降子序列 ......................................................... 4.5 求逆序对个数 ........................................................... 4.6? 棋盘覆盖问题 ......................................................... 4.7 小结 ..................................................................

第五单元

动态规划(DP) ............................................... 35
35 35 35 36 36 37 37 38 38 38 39

5.1 导例:数字三角形 ........................................................ (1) 数据存储 ............................................................ (2) 递推 ............................................................... (3) 记忆化搜索——用递归代替递推 ............................................. (4) 记录路径 ............................................................ (5) 使用滚动数组......................................................... (6) 无奈的解法 .......................................................... 5.2 石子合并 .............................................................. (1) 环的处理方法......................................................... (2) 求解 ............................................................... (3) 能量项链(NOIP2006, 1) ..............................................

IV

NOIP 复习资料(C++版) - 目录 5.3 方格取数问题 ........................................................... (1) 单向取数问题......................................................... (2) 变式问题 ............................................................ (3) 双向取数问题——传纸条(NOIP2008, 3) .................................. 5.4 背包问题 .............................................................. 5.5 最长非降子序列(LIS) ................................................... 5.6 最长公共子序列(LCS) ................................................... 5.6 表达式上的动态规划:乘积最大 .............................................. 5.7 DAG 上的最短路径 ........................................................ (1) 最短路径的动态规划解法 ................................................ (2) 街道问题 ............................................................ 5.8 树上的动态规划:加分二叉树 ............................................... 5.9 Bitonic 旅行:最佳的状态转化方式 .......................................... 5.10 资源分配问题 .......................................................... 5.11 小结 ................................................................. 41 41 41 41 42 42 43 43 44 44 44 45 45 46 46

第六单元

背包专题 ..................................................... 48
48 48 48 48 48 49 49 49 49 49 49 50 50 50 50 51 51 51 51 52 53 54 54 54 54 55 55 56

6.1 部分背包 .............................................................. 6.2 0/1 背包 .............................................................. (1) 二维数组表示......................................................... (2) 一维数组表示......................................................... (3) 一维之下的一个常数优化 ................................................ (4) 初始化时的细节 ....................................................... 6.3 完全背包问题 ........................................................... (1) 比较差的算法......................................................... (2) 更优的算法 .......................................................... 6.4 多重背包问题 ........................................................... (1) 转化为 0/1 背包——二进制法 ............................................ (2) 使用优先队列的算法**.................................................. 6.5 二维费用的背包问题 ...................................................... (1) 0/1 背包的表示方法 ................................................... (2) 限制物品总个数的 0/1 背包 .............................................. (3) 二维费用的完全背包和多重背包问题 ........................................ (4) 二维费用背包的另一种解法 ............................................... 6.6 分组的背包问题 ......................................................... 6.7 有依赖的背包问题 ........................................................ 6.8 泛化物品 .............................................................. 6.9 混合背包问题 ........................................................... 6.10 特殊要求 ............................................................. (1) 输出字典序最小的最优方案 ............................................... (2) 求方案总数 .......................................................... (3) 最优方案的总数 ....................................................... (4) 求次优解、第 K 优解 ................................................... 6.11 背包问题的搜索解法 ..................................................... 6.12 小结 .................................................................

第七单元

排序算法 ..................................................... 58

7.1 常用排序方法 ........................................................... 58

V

NOIP 复习资料(C++版) - 目录 (1) 调用库函数 .......................................................... (2) 快速排序( “快排” .................................................... ) (3) 归并排序 ............................................................ 7.2 简单排序算法(不推荐使用) ............................................... (1) 插入排序 ............................................................ (2) 选择排序 ............................................................ (3) 冒泡排序 ............................................................ 7.3 线性时间排序 ........................................................... (1) 桶排序 ............................................................. (2) 计数排序 ............................................................ (3) 基数排序 ............................................................ 7.4 使用树的排序算法* ....................................................... (1) 二叉树排序 .......................................................... (2) 堆排序 ............................................................. 7.5 小结 .................................................................. 58 58 59 59 59 60 60 60 60 61 61 62 62 63 65

第八单元

查找算法 ..................................................... 66
66 66 66 66 68 67 69 69

8.1 顺序查找 .............................................................. 8.2 二分查找 .............................................................. (1) 普通的二分查找(非递归) ............................................... (2) 二分查找求下界 ....................................................... 8.3 二叉排序树(BST)* ..................................................... 8.4 查找第 k 小元素 ......................................................... 8.5 哈希表* ............................................................... 8.6 小结 ..................................................................

第九单元

常用数据结构 ................................................. 70

9.1 链表 .................................................................. 70 (1) 单链表 ............................................................. 70 (2) 静态链表 ............................................................ 70 (3) 循环链表 ............................................................ 71 (4) 双链表 ............................................................. 71 9.2 栈(LIFO 表) .......................................................... 71 (1) 栈 ................................................................. 71 (2) DFS 和栈............................................................ 72 9.3 队列、循环队列(FIFO 表) ................................................ 72 (1) 队列 ............................................................... 72 (2) 循环队列 ............................................................ 73 (3) BFS 和队列 .......................................................... 73 9.4 二叉树 ................................................................ 73 (1) 二叉树的表示......................................................... 73 (2) 二叉树的遍历......................................................... 73 (3) 已知前(后)序遍历和中序遍历,求后(前)序遍历 ............................ 74 (4) 多叉树变二叉树 ....................................................... 75 (5) 求树的直径* ......................................................... 75 (6) 哈夫曼树* .............................................. 错误!未定义书签。 9.5 堆* .................................................................. 68 9.6 并查集 ................................................................ 76

VI

NOIP 复习资料(C++版) - 目录 (1) 存储 ............................................................... (2) 合并 ............................................................... (3) 带路径压缩的查找(递归) ............................................... (4) 带路径压缩的查找(非递归) ............................................. 9.7 图 ................................................................... (1) 图的存储方法......................................................... (2) 图的遍历 ............................................................ (3) 图的连通性 .......................................................... (4) 欧拉回路( “一笔画” .................................................. ) (5) 图论建模:食物网问题 .................................................. (6) 图论建模:篝火晚会(NOIP2005,3) ...................................... 9.8 线段树** .............................................................. (1) 线段的定义 .......................................................... (2) 建立一棵线段树 ....................................................... (3) 插入一条线段......................................................... (4) 删除一条线段......................................................... (5) 统计 ............................................................... 9.9 小结 .................................................................. 76 77 77 77 77 78 80 81 82 83 83 84 85 85 86 87 88 89

第十单元

高精度算法 ................................................... 91
91 91 92 92 92 93 94 95 95

10.1 定义 ................................................................. 10.2 赋值和初始化 .......................................................... 10.3 比较运算符 ............................................................ 10.4 四则运算 ............................................................. (1) 高精度加、减法 ....................................................... (2) 高精度乘法 .......................................................... (3) 高精度除法 .......................................................... 10.5 输入/输出 ............................................................ 10.6 小结 .................................................................

第十一单元

常用数学知识 ................................................ 97

11.1 计数原理 ............................................................. 97 (3) 二项式定理 .......................................................... 98 11.2 组合数的计算 .......................................................... 98 (1) 使用加法递推——O(n2) ................................................. 98 (2) 使用乘法递推——O(n) ................................................. 99 11.3 排列和组合的产生 ....................................................... 99 (1) DFS 产生全排列和组合 .................................................. 99 (2) 由上一排列产生下一排列 ................................................ 99 (3) 由上一组合产生下一组合 ............................................... 100 11.3 秦九韶算法 ........................................................... 100 11.4 进制转换 ............................................................ 101 (1) 十进制变 N 进制——短除法 ............................................. 101 (2) N 进制变十进制 ...................................................... 101 11.5 鸽巢原理、容斥原理* ................................................... 101 11.6 常见的递推关系 ....................................................... 102 (1) 梵塔问题 ........................................................... 102 11.6 表达式求值 ........................................................... 104

VII

NOIP 复习资料(C++版) - 目录 (1) 递归 .............................................................. (2) 利用堆栈来模拟运算................................................... (3) 利用分治思想进行计算 ................................................. (4) 构建表达式树........................................................ 11.7 快速幂 .............................................................. 11.8 计算几何初步** ....................................................... (1) 细节 .............................................................. (2) 向量 .............................................................. (3) 直线和线段 ......................................................... (4) 复数和复平面........................................................ (5) 长方形的面积交和面积并 ............................................... 11.9 多项式乘法 ........................................................... (1) 朴素算法 ........................................................... (2) 使用点积优化**...................................................... 11.10 小结 ............................................................... 104 105 107 109 110 110 110 110 112 113 114 114 114 114 115

第十二单元

数论算法 .................................................. 116
116 116 116 116 117 117 117 117 117 118 119 119 119 119 120

12.1 最大公约数、最小公倍数 ................................................. 12.2 解不定方程 ax+by=c .................................................. 12.3 同余问题* ........................................................... (1) 同余式 ............................................................ (2) 同余式组 ........................................................... 12.4 素数和素数表 ......................................................... (1) 素数定理 ........................................................... (2) 判断素数 ........................................................... (3) 筛法产生素数表 ...................................................... (4) Miller-Rabin 素性测试* ............................................. 12.5 分解质因数 ........................................................... (1) 分解质因数 ......................................................... (2) 除数函数 ........................................................... (3) 欧拉函数 ........................................................... 12.6 小结 ................................................................

第十三单元

图论算法 .................................................. 121
121 121 122 122 123 123 124 125 125 126 126 127 127 127

13.1 最小生成树(MST) .................................................... (1) Prim 算法(贪心) [邻接矩阵] ......................................... (2) Kruskal 算法(贪心) [边目录] ....................................... (3) 使用并查集的 Kruskal 算法 [边目录] .................................... 13.2 单源最短路问题(SSSP 问题) ............................................ (1) Dijkstra 算法(贪心) [邻接矩阵] ..................................... (2) 使用优先队列的 Dijkstra 算法** [邻接表] ............................... (3) Bellman-Ford 算法(迭代) [边目录] .................................. (4) 使用队列的 Bellman-Ford 算法(SPFA) [邻接表] ......................... 13.3 每两点间最短路问题(APSP 问题) ......................................... (1) Floyd-Warshall 算法 [邻接矩阵] ..................................... (2) 有向图的传递闭包 [邻接矩阵] .......................................... 13.4 拓扑排序(AOV 网) .................................................... (1) DFS(递归算法) [邻接矩阵/邻接表] ....................................

VIII

NOIP 复习资料(C++版) - 目录 (2) 使用辅助队列 [邻接矩阵/邻接表] ....................................... 13.5 关键路径(AOE 网) .................................................... (1) 对 DAG 求关键路径 [邻接矩阵/邻接表].................................... (2) 对已经进行拓扑排序的序列求关键路径 ..................................... 13.6 二分图 .............................................................. (1) 染色法判定二分图 [邻接表] ............................................ (2) 二分图的最大匹配** .................................................. 13.7 网络流初步** ......................................................... 13.8 小结 ................................................................ 128 128 128 130 131 131 132 132 140

附录 A
A.2 A.3 A.4 A.5 A.6

一些技巧...................................................... 141
动态化静态 ............................................................ 前序和 ............................................................... 特殊形状的数据 ........................................................ 离散化* .............................................................. 位集合运算* ........................................................... (1) 集合的表示方法 ...................................................... (2) 集合的交、并、补、差 ................................................. (3) 其他运算 ........................................................... (4) 重要提示 ........................................................... 141 142 142 142 144 144 144 144 144

A.1 #define ............................................................. 141

附录 B

DEBUG ....................................................... 145
145 145 145 145 145 145 146 146 146

B.1 一些技巧 ............................................................. (1) 将变量的值输出到屏幕上。 .............................................. (2) 暂停屏幕 ........................................................... (3) 计时 .............................................................. (4) 代码修改完成后,把调试输出注释掉,而不是删掉。 ........................... B.2 更安全地编写调试代码 ................................................... B.3 故障处理 ............................................................. B.4 命令提示符* ........................................................... B.5 gdb** ...............................................................

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

一些经验...................................................... 147
考前 30 分钟 .......................................................... 审题 ................................................................. 编写代码 ............................................................. 理解和设计测试数据 ..................................................... 交卷前 5 分钟 .......................................................... 骗分 ................................................................. 147 147 148 148 149 149

附录 D

NOIP 竞赛大纲 ................................................. 151

D.1 命题形式 ............................................................. 151 D.2 初赛内容与要求 ........................................................ 151 D.3 复赛内容与要求 ........................................................ 152

附录 E

Pascal 语言简介* .............................................. 153

E.1 代码结构 ............................................................. 153

IX

NOIP 复习资料(C++版) - 目录 (1) 开头 .............................................................. 153 (2) main() ........................................................... 153 (3) 代码块和注释........................................................ E.2 数据类型和变量声明 ..................................................... (1) 数据类型 ........................................................... (2) 常量 .............................................................. (3) 变量 .............................................................. (4) 字符串类型 ......................................................... (5) 子界类型 ........................................................... (6) 集合类型 ........................................................... E.3 标准函数 ............................................................. (1) 算术函数 ........................................................... (2) 标准函数 ........................................................... (3) 转换函数 ........................................................... (4) 杂类函数 ........................................................... E.4 运算符 ............................................................... E.5 程序结构 ............................................................. (1) 顺序结构程序........................................................ (2) 选择结构程序........................................................ (3) 循环结构程序........................................................ E.6 函数和过程 ............................................................ E.7 文件操作 ............................................................. E.8 Free Pascal IDE 的三大问题 ............................................ (1) 不支持中文 ......................................................... (2) 乱码 .............................................................. (3) Compile Failed ................................................... 153 153 153 153 154 154 155 155 155 155 155 156 156 156 156 156 157 157 157 158 158 158 159 159

附录 F 附录 G

参考文献...................................................... 160 一些网站...................................................... 160

X

NOIP 复习资料(C++版)

第一单元

程序设计基础

1.1 基本数据类型
名称 int unsigned int* char unsigned char short** unsigned short long long unsigned long bool char signed char unsigned char float double wchar_t*** long 占用空间 4 4 1 1 2 2 8 8 1 1 1 1 4 8 2 long double 别名 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 使用/J 编译时为 0~255 –128~127 0~255 3.4E +/- 38 (7 位有效数字) 1.7E +/- 308 (15 位有效数字) 0~65,535

* 一般都使用有符号整数,除非范围不够大,或者你确定你的减法运算不会出现“小数减大数” 。 ** 一般来说,使用 int、long long 更保险一些。并且,int 和 long long 才是 NOIP 最常用的数据类型。 *** 所有算法竞赛都不会涉及汉字和其他语言文字的处理,所以用 char 就足够了。

1.2 运算符
(1) 常见运算符的优先级
运算符 :: .(对象成员) ->(指针) [](数组下标) ()(函数调用) ++ -- (typecast)(强制类型转换) sizeof ~ ! +(一元) -(一元) *(取值运算符) &(取地址运算符) new delete .* ->* * + / % 结合方式 无 从左向右 从右向左 从左向右 从左向右 从左向右 从左向右 从左向右 从左向右 从左向右

<< >> < <= > >= >?(取最大值) <?(取最小值) == != &

1

NOIP 复习资料(C++版) ^ | && || ?:(条件运算符) = , *= /= %= += -= &= ^= >?=(取最大值) <?=(取最小值) >>= <<= 从左向右 从左向右 从左向右 从左向右 从右向左 从右向左 从左向右

取最值:例如, “5>?3”返回 5, “5<?3”返回 3, “a>?=b”同“a=a>?b”“a<?b”同“a=a<?b” , 。

(2) 使用提示
1. 不要同时对变量进行赋值和自增、自减,以免发生混乱:写“i=i++”之类代码,在 DEBUG 时会吃亏的。 2. 比较运算符、位移运算符、逻辑运算符、条件运算符的优先级较低,所以使用时要多加括号,以防出错。 3. ||、&&、?:是短路运算符。 举个例子, f(a)||f(b)时, 求 如果 f(a)==true, 就不再计算 b 的值而直接返回 true。 只有 f(a)==false 时才计算 f(b)。 4. a<<n 相当于 a×2n,a>>n 相当于 a÷2n。 5. 尽管>?、<?、>?=、<?=很难在其他 C 语言教程(包括 MSDN)中找到,但它们确实是合法的运算符。 6. 在数组维数较多时,可以利用引用来增强可读性,例如: int &f=F[i][j][k]; for (int l=0; l<n; l++) { f[l] = …… …… } 7. 赋值“=”是一种运算符,所以 a=b=c=0、i=j+=k、d[x=y]都是合法的。

1.3 输入和输出
(1) 使用标准输入/输出
头文件:#include <cstdio> 变量约定: FILE *fin, *fout;——fin、 fout 分别代表输入文件和输出文件。 把它们换成 stdin 和 stdout, 就是从屏幕输入和从屏幕输出。 “1.5 字符串操作”也使用了同样的变量。 1. 输出字符串或变量的值:printf("格式字符串", ……); 或 fprintf(fout, "格式字符串", ……); 格式字符: 字符 d u o x, X 含义 整数 无符号整数 八进制整数 十六进制整数(小写、大写) 字符 e, E f c s 含义 用科学记数法表示的浮点数 浮点数 字符 字符串(字符数组)

* 最好用流输出 long long 类型的值。 因为 Linux 和 VC++用的是"%lld", 一般编译器用的是"%I64d", 不一样。 常见的修饰符: a) %5d:5 位数,右对齐。不足 5 位用空格补齐,超过 5 位按实际位数输出。 b) %-5d:5 位数,左对齐。不足 5 位用空格补齐,超过 5 位按实际位数输出。

2

NOIP 复习资料(C++版) c) %05d:5 位数,右对齐。不足 5 位用'0'补齐,超过 5 位按实际位数输出。 d) %+d:无论是正数还是负数,都要把符号输出。 e) %.2f:保留 2 位小数。如果小数部分超过 2 位就四舍五入,否则用 0 补全。 2. 输入到变量: a) scanf("格式字符串", &……); 或 fscanf(fin, "格式字符串", &……); ① 格式字符和 printf 基本一致。 ② 不要忘记―&‖。 ③ scanf 和 fscanf 的返回值是:成功输入的变量个数。 ④ 忽略 TAB、空格、回车。遇到这些字符就停止读取。 b) fgetc(fin); 读取单个字符。 首先要判断它是否为 EOF(文件结束) 。如果不是,就可以用强制类型转换变成 char。 3. 提示:Windows、Linux、Mac 的回车字符是不同的。 Windows 为'\r'和'\n',Linux 为'\n',Mac 为'\r'。

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

前两行代码,每次输出之前都要调用。 c) 输出成其他进位制数: 8: cout<<oct<<a; 16: cout<<hex<<a; 4. 如果涉及大量数据的输入和输出,最好不要使用流。

1.4 其他常用操作
1. 很多函数、容器都需要引用 std 命名空间。所以需要在#include 后面、你的代码前面加上一句: using namespace std; 如果不这么做,你就要面临:std::cout<<std::hex<<a<<std::endl; 2. 数组初始化:memset(a, 0. sizeof(a)); a) 头文件:#include <cstring> b) 必须牢记:第二个参数只能传入 0 或-1。传入其他数会发生意想不到的事情。 3. 执行 DOS 命令或其他程序:system("命令行"); a) 头文件:#include <cstdlib> b) 暂停屏幕:system("pause"); c) 在交卷之前必须删除相关代码。

3

NOIP 复习资料(C++版) 4. 随机数发生器: a) 头文件:#include <cstdlib> b) 产生随机数: ① 0~32767 的随机数:rand() ② 粗略地控制范围(注意,这样产生的随机数分布是不均匀的) :rand()%范围 如果范围超过了 32767,你可以随便地处理(如乘 99,再加一个随机数,等等) 。 ③ 精确地控制范围:(double)rand()/RAND_MAX*范围 c) 初始化随机数种子: ① srand(数字):初始化随机数种子。 ② 注意,这条语句在程序开头使用,并且最多用一次。同一程序、同一平台,srand 中的参数相等, 用 rand()产生的随机数序列相同。 ③ 使随机数更加随机:引用<ctime>,然后这样初始化随机数种子,srand(time(NULL))。

1.5 字符串操作
(1) 使用字符数组
头文件:#include <cstring> 假设待处理的字符串为 str 和 str2,即:char str[MAX], str2[MAX]; 牢记,字符串的最后一个字符一定是'\0'。如果字符串内没有'\0',进行以下操作时可能会发生意外。 1. 输出字符串 str: a) cout<<str; b) printf("%s",str); 或 fprintf(fout, "%s", str); 2. 输入字符串 str: a) scanf("%s", str); 或 fscanf(fin, "%s", str); b) cin>>str; 以上两种方法在输入时会忽略空格、 回车、 TAB 等字符, 并且在一个或多个非空格字符后面输入空格时, 会终止输入。 c) fgets(str, MAX, fin); 3. 4. 每调用一次,就会读取一行的内容(即不断读取,直到遇到回车停止) 。 求字符串 str 的长度:strlen(str) // 这个长度不包括末尾的'\0'。 把字符串 str2 连接到字符串 str 的末尾:strcat(str, str2) a) str 的空间必须足够大,能够容纳连接之后的结果。 b) 函数的返回值为&str[0],连接的结果直接保存到 str 里。 c) strncat(str, str2, n)是把 str2 的前 n 个字符连接到 str 的末尾。 把字符串 str2 复制到字符串 str 中:strcpy(str, str2) // 把 str2 复制到 str 中。 比较 str 和 str2 的大小:strcmp(str, str2) 如果 str>str2,返回 1;如果 str==str2,返回 0;如果 str<str2,返回-1。 在 str 中寻找 str2:strstr(str, str2) a) 返回值是一个指针,表示 str2 在 str 中的位置。用 strstr 的返回值减 str,就是具体的索引位置。

5. 6. 7.

(2) 使用字符串类*
头文件:#include <string> 假设待处理的字符串为 str 和 str2,即:string str, str2; 1. 输出字符串 str:cout<<str;

4

NOIP 复习资料(C++版) 2. 输入字符串 str: a) cin>>str; 输入时会忽略空格、回车、TAB 等字符,并且在一个或多个非空格字符后面输入空格时,会终止输入。 b) getline(cin, str, '\n'); // 遇到'\n',即回车才终止读入 求字符串 str 的长度:str.length() 访问序号为 10 的字符:str[10] // 和字符数组一样 提取子串:str.substr(a, b); // 返回值是从第 a 个字符开始,长度为 b 的子串。 连接字符串:可以直接使用“+”或“+=”运算符连接字符串。 a) 由于“+”是通过运算符重载实现的,所以两个操作数中至少有一个是 string 对象。"a"+"b"就是非 法的。 b) “+”涉及新对象的创建,所以会引起一定数量的开销。 在 str 末尾追加字符/字符串: a) str.append(字符串对象); // 追加字符串 b) str.append("字符串"); c) str.append(10, 'a'); // 追加 10 个 a d) str.append(str2, 3, 5); // 从 str2 的第 3 个字符开始,取 5 个字符,追加到 str 末尾 e) str.push_back('*'); // 追加单个字符 在 str 的第 k 位置插入字符串: a) str.insert(k, str2); // 插入 str2 b) str.insert(k, "字符串"); c) str.insert(k, str2, n); // 插入 str2 的前 n 个字符 d) str.insert(k, "字符串", n); // 插入字符数组中的前 n 个字符 e) str.insert(k, str2, a, b); // 相当于 str.insert(k, str2.substr(a,b)); 用 str2 的一部分替换 str 的一部分: a) str.replace(k, n, str2); // 用 str2 的前 n 个字符替换 str 中从 k 开始的 n 个字符 b) str.replace(k, n, "字符串"); c) str.replace(k, n1, str2, n2); // 用 str2 的前 n2 个字符替换 str 中从 k 开始的 n1 个字符 d) str.replace(k, n1, str2, k2, n2); // 相当于 str.replace(k, n1, str2.substr(k2,n2)) e) str.replace(k, n1, n2, '**); // 用 n2 个'*'替换 str 中从 k 开始的 n 个字符 10. 把 str 转换成字符数组:str.c_str() 11. 字符串比较:可以直接使用==、!=、>、<、>=、<=运算符。 12. 搜索子串: a) str.find('a', k); // 从 k 开始寻找'a'。k 可以省略,代表从头开始搜索。 b) str.find("字符串", k); c) str.find(str2, k); d) 如果找到了对应的子串,就返回索引位置,否则返回 string::npos。

3. 4. 5. 6.

7.

8.

9.

1.6 文件操作
(1) 使用输入/输出重定向操作
注意:有些算法竞赛将这种做法视为作弊。编程之前请注意比赛要求。 头文件:#include <cstdio> 方法:只需在操作文件之前添加以下两行代码。 freopen("XXXXX.in","r",stdin); freopen("XXXXX.out","w",stdout);

5

NOIP 复习资料(C++版) 调用两次 freopen 后,scanf、printf、cin、cout 的用法完全不变,只是操作对象由屏幕变成了指定文件。

(2) 使用流输入/输出文件
注意:如果数据量太大,那么程序很有可能在数据读完之前就超时!在输入/输出内容特别多的时候,要使用其 他文件操作方法。 头文件:#include <fstream> 命名空间:using namespace std; 方法:声明两个全局变量。 ifstream fin("XXXXX.in"); ofstream fout("XXXXX.out"); 然后就可以像对待 cin 和 cout 一样对待 fin 和 fout 了,如:fin>>a; fout<<b; 如果不习惯,可以使用#define:#define cin fin 和#define cout fout

(3) 使用文件指针
头文件:#include <cstdio>(#include <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)。 // 在某些情况下,忘记关闭文件会被认为是没有产生文件。

1.7 简单的算法分析和优化
(1) 时间复杂度
为了描述一个算法的优劣,我们引入算法时间复杂度和空间复杂度的概念。 时间复杂度:一个算法主要运算的次数,用大 O 表示。通常表示时间复杂度时,我们只保留数量级最大的 项,并忽略该项的系数。 例如某算法,赋值做了 3n3+n2+8 次,则认为它的复杂度为 O(n3);另一算法的主要运算是比较,做了 4× 2n+2n4+700 次,则认为它的时间复杂度为 O(2n)。 当然,如果有多个字母对算法的运行时间产生很大影响,就把它们都写进表达式。如 m×n 的数组遍历的时 间复杂度可以写作 O(mn)。 常见的数量级大小:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)

6

NOIP 复习资料(C++版)

(2) 空间复杂度
空间复杂度:一个算法主要占用的内存空间,也用大 O 表示。 在实际应用时,空间的占用是需要特别注意的问题。太大的数组经常是开不出来的,即使开出来了,遍历的 时间消耗也是惊人的。

(3) 常用算法的时空复杂度
1s 运算次数约为 8,000,000。也就是说,如果把 n 代入复杂度的表达式,得数接近或大于 8,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

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

常见算法 直接输出结果或仅仅简单的数学计算 (如 y=n/2*3, 然后结束了) 二分查找、快速幂 贪心算法、扫描和遍历 带有分治思想的算法 动态规划 动态规划 搜索 产生所有的全排列 暴力法破解密码

(4) 简单的优化方法
① 时间的简单优化方法 时间上的优化在于少做运算、做耗时短的运算等。 有几个规律需要注意: 1. 整型运算耗时远低于实型运算耗时。 2. 位运算比四则运算快。 3. +、- 运算非常快(但是减法也比加法稍慢些) 。 4. *运算比加法慢得多。 5. /运算比乘法慢得多。 6. 比较运算慢于四则运算。 7. 赋值运算慢于比较运算(因为要写内存) 。 这些规律我们可以从宏观上把握。事实上,究竟做了几步运算、几次赋值、变量在内存还是缓存等多数由编 译器、系统决定。但是,少做运算(尤其在循环体、递归体中)一定能很大程度节省时间。 ② 空间的简单优化方法 空间上的优化主要在于减小数组大小、降低数组维数等。 常用的节省内存的方法有: 压缩储存——例:数组中每个数都只有 0、1 两种可能,则可以按位储存,空间压缩为原来的八分之一。 覆盖旧数据——例: 矩阵中每一行的值只与上一行有关, 输出只和最末行有关, 则可将奇数行储存在第一行, 偶数行储存在第二行,降低空间复杂度。 要注意的是,对空间的优化即使不改变复杂度、只是改变 n 的系数也是极有意义的。空间复杂度有时对时 间也有影响,要想方设法进行优化。

7

NOIP 复习资料(C++版)

1.8 写给没有参加过 NOIP 的同学
(1) NOIP 和设计竞赛的区别
1. 我们参加的是算法竞赛。所以,答案是检验程序的唯一标准。 2. 记住,NOIP 是粗暴的比赛,所以当你友好地询问“Hello! Please input n:,客气的提示“Please ” wait, the program is solving the problem…” ,谦虚地回答“Congratulation! The result is …”时,测评器会告诉你“Wrong answer! Your score is zero!” (答案错误,得 0 分) 。 (要严格按照格式输入、输出文件,不要输出与算法无关的东西。格式错误和计算结果错误是等效的) 3. 题目中已经规定,输入和输出要在文件中进行。所以直接从屏幕上输入、输出是要得 0 分的。 4. 程 序 运 行 时 间 是 有 限 制 的 。 如 果 你 的 程 序 没 有 在 规 定 时 间 内 算 完 , 或 者 在 “ Press any key to continue…” ,会得 0 分的。 5. 如果出现窗口和对话框,那么恭喜你,你的编程水平不低。但是,你会得 0 分的。 (测评器是 NOI Linux。你玩<windows.h>,测评器会告诉你: “嘿,哥们,我不认识 windows” ) 6. 用绝对路径读取和存储文件,会得 0 分的。 7. 在 main()中忘记 return 0,别担心,编译器会替你 return 0 的(题目得 0 分) 。 (程序必须正常退出,否则即使答案正确也是 0 分。 ) 8. 被问题和算法困住是正常的事情。 但是, 不要被语言本身困住。 所以一要把语言弄熟, 二要养成良好的习惯。 9. 只要能解决问题,怎么写代码都行——没有人看你的代码。所以, ……intn, a[1000 ],ans= 0;intmai n(){FILE*fp=f open(" xx.in", ");fscanf "r (fp,"%d ",&n); for(in i=0;i< t n;)fsc anf(fp ,"%d",& i a[ ++]);……re turn0;} 也是可以的(代码中有空格,要不然无法通过编译) 。 10. 如果你写黑客程序(打开某个程序,操作规定之外的文件,画地图,访问网络,甚至控制测评器) ,你会被 河蟹的。

(2) 常用语
1. 竞赛简称 a) OI:信息学奥林匹克竞赛 b) NOIP:联赛,分为普及组(初中生参加)和提高组(高中生参加) 。 NOIP 初赛相当于其他科目的省级联赛,NOIP 复赛相当于其他科目的全国初赛。 c) NOI:全国竞赛。先进省队然后才能参加。 d) CTSC:中国国家队选拔赛,选拨选手参加 IOI。 e) IOI:国际信息学奥林匹克竞赛。 f) APIO:亚洲与太平洋地区信息学奥林匹克。 g) ACM:大学生的程序设计竞赛,和高中生没有关系。 2. 选手 a) OIer:学信息学奥赛的人 b) P 党:指用 Pascal 语言编程的 OIer。 c) C 党:指用 C 或 C++语言编程的 OIer。 d) 弱菜:新手 e) 大牛、神牛:高手 3. 题目 a) 水题:特别简单的题——有编程基础的就能做上——只要认真审题,基本上就能得满分。 b) 水过:做完了一道水题。 c) 秒过:所有数据 0ms,毫无压力。 d) 暴 0:一个题目一个测试点也没过,得 0 分。 e) 被虐:被题目虐杀,自己完全做不出,或者对自己的表现很不满意。 f) 暴虐:这个是主动的,把题目虐杀,秒掉。

8

NOIP 复习资料(C++版) 4. 评测 a) AC:Accepted,测试点全部正确。 b) AK:把一次比赛的所有的题目全都做对,得满分。 c) WA:Wrong Answer,答案错误,也可以是输出格式错误。 d) CE:Compile Error,编译错误,出现了某些语法错误,错误引用头文件,或者忘记引用头文件,还 可能是忘记 using namespace std 而直接使用 std 的成员。 e) RE:Runtime Error,运行错误。可能是算法中数组下标越界,可能是因文件错误而引发的下标越界, 也可能是爆栈。 f) TLE:Time Limit Error,超时。可能是算法太慢,也可能是程序在等待键盘输入。 g) MLE:Memory Limit Error,超过空间限制。在 NOIP 中一般不会出现此类问题。不过,尽管内存 够大,做题之前仍然要仔细阅读内存限制。

1.9 IDE
为了更好地学习信息学,你需要一台带有 C++编译器的计算机。为了方便编程,还要有 IDE。 如果使用 Linux 操作系统,系统会自带 C++编译器(g++)和调试器(gdb) ,不过没有 IDE。你可以选择 以下几种 IDE——Anjuta、Code::Blocks、GUIDE。 如果使用 Windows 系统,你需要自己安装 C++编译器、调试器和 IDE。以下是几种选择: 1. DEV-C++:竞赛中使用的 IDE。它是一款比较常用的 IDE,并且自带编译器和调试器,所以安装完成 后就可以直接编译程序了。可惜它的调试功能很不好用。 2. Visual C++:最好不要使用 Visual C++,一方面它必须要建立工程才能编译程序,很麻烦的;另 一方面,它在某些方面的语法和标准的 C++不同。它也自带编译器和调试器。 3. Code::Blocks:它是一款功能强大的 IDE,并且有 Windows 版本。它不含编译器,所以需要安装 MinGW 才能编译程序。 4. GUIDE:是一款比较“简朴”的 IDE。它也需要安装 MinGW 才能编译程序。不过,GUIDE 无法正确输 出中文字符。 5. Turbo C:?? 6. 记事本+cmd:??

1.10 小结
本单元介绍了 C++语言和竞赛常识。语言是实现算法的工具,所以读者应该熟练运用 C++语言,在竞赛的 时候不应该在语言上出现疑难和失误。 本单元的要点有: 1. int 和 long long 是最常用的两种数据类型。为了保险,最好不要使用 unsigned 和 short。 2. >?、<?、>?=、<?=也是比较运算符。在算法竞赛中使用,可以简化代码。 3. 数据输入和输出的方法很多。 小规模数据可以使用流, 因为代码简洁; 而大规模数据最好使用文件指针, 因为流的操作速度慢。 4. 随机数、计时、数组初始化、暂停屏幕都是常用的操作。 5. 涉及字符串操作的时候,既可以使用传统的方法,也可以使用 string 类。后者代码简洁,前者速度 更快。 6. 算法的时间复杂度和空间复杂度有很多种。通过数据规模,可以大致确定需要使用的算法。 7. 在网络上与他人交流时,有很多常用语。使用次数多了,也就自然成了专用单词。 有了扎实的语言基础,就可以比较容易地完成模拟题了。做模拟题的要点也很简单,就是不用刻意想算法, 只需按照题目要求写程序。

9

NOIP 复习资料(C++版)

第二单元

搜索

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

(1) 深度优先搜索(DFS)
逐列(行)搜索。每测试一个位置,就检查它是否与其他皇后冲突,如果冲突,回溯。 每放置一个皇后,就要记录——所在列、 “/”对角线和“\”对角线都不能放皇后了。 #include "iostream" #include "cstdlib" #include "ctime" using namespace std; // 检查是否可以放置皇后 #define canplace(row, i) !(column[i]||cross1[row-i+n]||cross2[row+i]) #define init(x) memset(x,0,sizeof(x)) bool column[20],cross1[50],cross2[50]; int pos[20]; int n; int sum; void dfs(int row) { int i; if (row==n) sum++; else for (i=0;i<n;i++) // i ======> column { if (canplace(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() {

10

NOIP 复习资料(C++版) cin>>n; time_t tm = time(NULL); init(column); init(cross1); init(cross2); sum=0; dfs(0); printf("%d皇后共有%ld种排列, 计算时间%d秒\n", n, sum, (int) (time(NULL) - tm)); system("pause"); return 0; }

(2) 位运算加速
把状态放在单独一个 4 字节的 int 整型变量中,并且使用位运算——速度会比朴素算法快一些。 #include "iostream" #include "cstdlib" #include "ctime" // sum用来记录皇后放置成功的不同布局数;upperlim用来标记所有列都已经放置好了皇后。 long 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清零。 也就是为获取下一次的最右可用列使用做准备, 程序将来会回溯到这个位置继续试探。

11

NOIP 复习资料(C++版) */ pos -= p; /* row + p,将当前列置1,表示记录这次皇后放置的列。 (ld + p) << 1,标记当前皇后左边相邻的列不允许下一个皇后放置。 (ld + p) >> 1,标记当前皇后右边相邻的列不允许下一个皇后放置。 */ /* 此处的移位操作实际上是记录对角线上的限制,只是因为问题都化归 到一行网格上来解决,所以表示为列的限制就可以了。显然,随着移位 在每次选择列之前进行,原来N×N网格中某个已放置的皇后针对其对角线 上产生的限制都被记录下来了。 */ test(row + p, (ld + p) << 1, (rd + p) >> 1); } } else { // row的所有位都为1,即找到了一个成功的布局,回溯。 sum++; } } int main() { int n = 16; int i; scanf("%d", &n); time_t tm = time(NULL); // N个皇后只需N位存储,N列中某列有皇后则对应bit置1。 upperlim = (upperlim << i) - 1; sum = 0; test(0, 0, 0); printf("%d皇后共有%ld种排列, 计算时间%d秒\n", n, sum, (int) (time(NULL) - tm)); system("pause"); return 0; }

+2.2 骑士覆盖问题
【问题描述】在一个 n×n 的棋盘中摆放尽量少的骑士(象棋中的“马”,使得棋盘的每一格都会被至少一个骑 ) 士攻击到。但骑士无法攻击到它自己站的位置.

12

NOIP 复习资料(C++版)

+(1) 广度优先搜索(BFS)
先确定 k 个骑士能否实现,然后再尝试 k+1 个骑士。 1 process(state) 2 for each possible next state from this one 3 enqueue next state 4 search() 5 enqueue initial state 6 while !empty(queue) 7 state = get state from queue 8 process(state)

+(2) 迭代加深搜索*
广度优先搜索可以用迭代加深搜索代替。 迭代加深搜索实质是限定下界的深度优先搜索, 即首先允许深度优先搜索搜索 k 层搜索树, 若没有发现可行解, 再将 k+1 后再进行一次以上步骤,直到搜索到可行解。 这个―模仿广度优先搜索‖搜索法比起广搜是牺牲了时间,但节约了空间。 使用 BFS,扩展的节点非常多的时候(如“埃及分数”,可以改用迭代加深搜索。 ) 1 truncated_dfsearch(hnextpos, depth) 2 if board is covered 3 print solution and exit 4 5 6 7 8 9 if depth == 0 return for i from nextpos to n*n put knight at i truncated_dfsearch(i+1, depth-1) remove knight at i

10 dfid_search 11 for depth = 0 to max_depth 12 truncated_dfsearch(0, depth)

2.3 DFS 产生全排列和组合(无重集元素)
int item[N]; bool used[N]; // 第 i 位要放置的数字

(1) 排列
void try(int deep) {

13

NOIP 复习资料(C++版) if (deep==N) { // print(); return; } for (int i=0;i<N;i++) if (!used[i]) { used[i]=true; item[deep]=i; try(deep+1); used[i]=false; } } // 别忘记清除‖使用‖标记 // 输出结果

(2) 组合
一个合法的组合有这样一个特点:排在右面的数字一定严格大于左面的数字。 int M; // 组合数的另一个参数 void try(int deep) { if (deep==M) { // print(); return; } for (int i=item[deep-1]+1 ; i<N-(M-deep) ; i++) { // 由于后面的元素一定前面的大,所以不需要标记used了。 item[deep]=i; try(deep+1); } } // 输出结果

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

14

NOIP 复习资料(C++版) 1101010101 0000010000 为了防止在搜索时发生下标越界,我们需要做一个小处理:在迷宫的外圈圈上一层围墙,即 111111111111 100010000001 101010111101 101110001001 100010101111 101000100011 101110111001 111010101011 100000100001 111111111111

以下是一些定义: char Map[110][110]; #define map(x,y) int n,m; struct point {int x,y;}; bool visited[110][110]; point prev[110][110]; void flag(int x, int y) { if (!(x==1&&y==1)) { point &t=prev[x][y]; flag(t.x,t.y); } map(x,y)='*'; }

// 为方便读取,就把纵坐标放在了前面。 Map[y][x]

// 记录路径的方法:从A节点扩展到B节点时,将prev[B]设为A。 // 追踪节点,在经过的路径上画“*”

(1) DFS
#define isok_dfs(a,b) (Map[b][a]!='1')&&(visited[a][b]==false) #define expand_dfs(a,b) {prev[a][b]=p;DFS(a,b);} bool stop=false; void DFS(int x,int y) { if (stop) return; if (x==m&&y==n) { flag(m,n); //asdf

15

NOIP 复习资料(C++版) for (int i=0;i<=n+1;i++) cout<<Map[i]<<endl; stop=true; return; } visited[x][y]=true; point p; p.x=x; p.y=y; if (isok_dfs(x-1,y)) expand_dfs(x-1,y) if (isok_dfs(x,y-1)) expand_dfs(x,y-1) if (isok_dfs(x+1,y)) expand_dfs(x+1,y) if (isok_dfs(x,y+1)) expand_dfs(x,y+1) } 通过试验可以发现,本问题用 DFS 解决不如用 BFS 解决。

(2) BFS
queue<point> q; #define isok(a,b) (Map[b][a]!='1')&&(visited[a][b]==false) #define expand(a,b) {prev[a][b]=p;t.x=a;t.y=b;q.push(t);} void BFS() { point t,p; p.x=p.y=1; q.push(p); while (!q.empty()) { p=q.front(); q.pop(); int &x=p.x, &y=p.y; visited[x][y]=true; if (x==m&&y==n) { flag(m,n); for (int i=0;i<=n+1;i++) cout<<Map[i]<<endl; return; } if if if if (isok(x-1,y)) (isok(x,y-1)) (isok(x+1,y)) (isok(x,y+1)) expand(x-1,y) expand(x,y-1) expand(x+1,y) expand(x,y+1) // 判断能否扩展 // 扩展节点

} cout<<"Failed"<<endl; }

16

NOIP 复习资料(C++版)

+(3) 广度优先双向搜索**
如果有一个 20×20 的迷宫,所有的点都是 0,那么程序会死掉。这时需要一些搜索技巧来加快速度。

+(4) A*算法**
构造一个估价函数:

+2.5 8 数码问题
【问题描述】用最少的步数实现:2 8 3 1 2 3 1 6 4 -> 8 4 7 5 7 6 5

(1) BFS
program num8; type a33=array[1..3,1..3] of 0..8; a4=array[1..4] of -1..1; node=record ch:a33; si,sj:1..3; pnt,dep:byte; end; const goal:a33=((1,2,3),(8,0,4),(7,6,5)); start:a33=((2,8,3),(1,6,4),(7,0,5)); di:a4=(0,-1,0,1); dj:a4=(-1,0,1,0); var data:array[1..100] of node; temp:node; r,k,ni,nj,head,tail,depth:integer; function check(k:integer):boolean; begin ni:=temp.si+di[k];nj:=temp.sj+dj[k]; if (ni in [1..3]) and (nj in [1..3]) then check:=true else check:=false; end; function dupe:boolean; var i,j,k:integer; buf:boolean; begin buf:=false;i:=0; repeat inc(i);buf:=true; for j:=1 to 3 do for k:=1 to 3 do if data[i].ch[j,k]<>data[tail].ch[j,k] then buf:=false; until buf or (i>=tail-1);

17

NOIP 复习资料(C++版) dupe:=buf; end; function goals:boolean; var i,j:byte; begin goals:=true; for i:=1 to 3 do for j:=1 to 3 do if data[tail].ch[i,j]<>goal[i,j] then goals:=false; end; procedure print; var buf:array[1..100] of integer; i,j,k,n:integer; begin n:=1; i:=tail;buf[1]:=i; repeat inc(n);buf[n]:=data[i].pnt; i:=data[i].pnt; until i=0; writeln('steps=',depth+1); for i:=1 to 3 do begin for k:=n-1 downto 1 do begin for j:=1 to 3 do write(data[buf[k]].ch[i,j]); if (i=2) and (k<>1) then write('->') else write(' '); end; writeln; end; readln;halt end; begin head:=0;tail:=1; with data[1] do begin ch:=start;si:=3;sj:=2;pnt:=0;dep:=0; end; repeat inc(head);temp:=data[head]; depth:=temp.dep; for r:=1 to 4 do if check(r) then begin inc(tail);data[tail]:=temp; with data[tail] do begin ch[si,sj]:=ch[ni,nj];

18

NOIP 复习资料(C++版) ch[ni,nj]:=0;si:=ni;sj:=nj; pnt:=head; dep:=depth+1; end; if dupe then dec(tail) else if goals then print; end; until head>=tail; writeln('no solution');readln; end. 2 8 3 1 2 3 1 6 4 -> 8 4 7 5 7 6 5 空格被删除了……

(2) 广度优先双向搜索**
program num8; const maxn=4000; type jid=record str:string[9]; f:0..maxn; dep:byte; end; bin=0..1; var c:array[0..1,1..maxn] of ^jid; head,tail:array[0..1] of integer; start,goal:string[9]; procedure init; var i,j:integer; begin start:='283164705'; goal:='123804765'; for i:=0 to 1 do for j:=1 to maxn do new(c[i,j]); c[0,1]^.str:=start; c[0,1]^.f:=0; c[0,1]^.dep:=0; c[1,1]^.str:=goal; c[1,1]^.f:=0; c[1,1]^.dep:=0; for i:=0 to 1 do begin head[i]:=0;tail[i]:=1;end; end; procedure print(st:bin;tail,k:integer); procedure print0(m:integer); begin if m<>0 then begin print0(c[0,m]^.f);writeln(c[0,m]^.str) end; end; procedure print1(m:integer);

19

NOIP 复习资料(C++版) var n:integer; begin n:=c[1,m]^.f; while n<>0 do begin writeln(c[1,n]^.str); n:=c[1,n]^.f end; end; begin if st=0 then begin writeln('step=',c[0,tail]^.dep+c[1,k]^.dep); print0(tail); print1(k);end else begin writeln('step=',c[0,k]^.dep+c[1,tail]^.dep); print0(k); print1(tail); end ; halt; end; procedure check(st:bin); procedure bool(st:bin); var i:integer; begin for i:=1 to tail[1-st] do if c[st,tail[st]]^.str=c[1-st,i]^.str then print(st,tail[st],i); end; var i:integer; begin for i:=1 to tail[st]-1 do if c[st,tail[st]]^.str=c[st,i]^.str then begin dec(tail[st]);exit end; bool(st); end; procedure expand(st:bin); var i,p0,p1,d:integer; str0,str1:string[9]; begin inc(head[st]); str0:=c[st,head[st]]^.str; d:=c[st,head[st]]^.dep; p0:=pos('0',str0); for i:=1 to 4 do begin if tail[st]>=maxn then exit; p1:=p0+2*i-5; if (p1 in [1..9]) and not ((p0=3) and (p1=4))and not((p0=4)and (p1=3)) and not((p0=6)and(p1=7))and not((p0=7)and(p1=6)) then begin inc(tail[st]); str1:=str0; str1[p0]:=str1[p1]; str1[p1]:='0'; c[st,tail[st]]^.str:=str1; c[st,tail[st]]^.f:=head[st]; c[st,tail[st]]^.dep:=d+1;

20

NOIP 复习资料(C++版) check(st); end; end; end; begin init; check(0); repeat if (tail[0]<=tail[1]) and not((head[0]>=tail[0])or(tail[0]>=maxn)) then expand(0); if (tail[1]<=tail[0]) and not((head[1]>=tail[1])or(tail[1]>=maxn)) then expand(1); if not((head[0]>=tail[0])or(tail[0]>=maxn)) then expand(0); if not((head[1]>=tail[1])or(tail[1]>=maxn)) then expand(1); Until((head[0]>=tail[0])or(tail[0]>=maxn))And((head[1]>=tail[1])or(tail[1]>=maxn )); writeln('No answer'); end.

(3) 启发式搜索(A*算法)**
NOIP 中用不到。 program num8; type a33=array[1..3,1..3] of 0..8; a4=array[1..4] of -1..1; node=record ch:a33; si,sj:1..3; f:byte; pnt,dep,next:byte; end; const goal:a33=((1,2,3),(8,0,4),(7,6,5)); start:a33=((2,8,3),(1,6,4),(7,0,5)); di:a4=(0,-1,0,1); dj:a4=(-1,0,1,0); var data:array[0..100] of node; temp:node; r,k,ni,nj,head,tail,depth:integer; function check(k:integer):boolean; begin ni:=temp.si+di[k];nj:=temp.sj+dj[k]; if (ni in [1..3]) and (nj in [1..3]) then check:=true else check:=false; end; function dupe:boolean; var i,j,k:integer; buf:boolean; begin buf:=false;i:=0; repeat inc(i);buf:=true;

21

NOIP 复习资料(C++版) for j:=1 to 3 do for k:=1 to 3 do if data[i].ch[j,k]<>data[tail].ch[j,k] then buf:=false; until buf or (i>=tail-1); dupe:=buf; end; function goals:boolean; var i,j:byte; begin goals:=true; for i:=1 to 3 do for j:=1 to 3 do if data[tail].ch[i,j]<>goal[i,j] then goals:=false; end; procedure print; var buf:array[1..100] of integer; i,j,k,n:integer; begin n:=1; i:=tail;buf[1]:=i; repeat inc(n);buf[n]:=data[i].pnt; i:=data[i].pnt; until i=0; writeln('steps=',depth+1); for i:=1 to 3 do begin for k:=n-1 downto 1 do begin for j:=1 to 3 do write(data[buf[k]].ch[i,j]); if (i=2) and (k<>1) then write('->') else write(' '); end; writeln; end; readln;halt end; function calc_f(a:a33):byte; var i,j,temp:byte; begin temp:=0; for i:=1 to 3 do for j:=1 to 3 do if (a[i,j]<>goal[i,j]) and (a[i,j]>0) then inc(temp); calc_f:=temp+depth+1; end; procedure sort(num:integer); var x,y:word; begin y:=head; repeat x:=y;y:=data[x].next;

22

NOIP 复习资料(C++版) until (y=0) or (data[y].f>data[num].f); data[x].next:=num;data[num].next:=y; end; begin head:=0;tail:=1; data[0].next:=1; with data[1] do begin ch:=start;si:=3;sj:=2; pnt:=0;dep:=0;next:=0; f:=calc_f(ch); end; repeat head:=data[head].next;temp:=data[head]; depth:=temp.dep; for r:=1 to 4 do if check(r) then begin inc(tail);data[tail]:=temp; with data[tail] do begin ch[si,sj]:=ch[ni,nj]; ch[ni,nj]:=0;si:=ni;sj:=nj; pnt:=head; dep:=depth+1; f:=calc_f(ch); end; if dupe then dec(tail) else if goals then print else sort(tail); end; until data[head].next=0; writeln('no solution');readln; end.

+2.6 图论模型
(1) 倒水问题

(2) 过河问题
【问题 1】 一个人带着一只狼、一只羊和一篮子白菜打算过河。 只有人能划船, 并且每次人最多只能带一样东西。 不过人不在的时候,狼会吃羊,羊会吃菜。请问怎样才能全部安全过河?

(3) 另一个过河问题
【问题 2】有 8 个人准备过河,他们分别是警察、罪犯、父亲、两个男孩、母亲和两个女孩。船上最多能容纳两 个人,并且只有警察、父亲、母亲能够划船。 警察不在的时候,罪犯会伤害其他人;父亲不在的时候,母亲会伤害男孩;母亲不在的时候,父亲会伤害女孩。 请问怎样才能全部安全过河?

23

NOIP 复习资料(C++版)

2.7 模板
(1) DFS 模板
void DFS(int v, … /*相关参数*/) { if (v==?? /*超界*/) { // 超界处理,如:输出、解的数量加1 return; } // 扩展节点,如 for (int i=0; i<n; i++) { // 处理节点 … // 继续搜索 DFS(v+1, …); // 部分问题需要恢复状态,如N皇后问题 … } } // v表示深度

(2) BFS 模板
BFS 占用存储空间比较大,尤其是在状态比较复杂的时候。 queue <int> state; void BFS(int v, …) { state.push(v); while (!state.empty()) { int s = state.front(); state.pop(); // 处理节点 if (s达到某种条件) { // 输出,或做些什么 … return; } // 寻找下一状态,如 for (i=0;i<n;i++) // 存储状态

// 获取状态

24

NOIP 复习资料(C++版) { state.push(… /*i对应的状态*/); } } // 无解 cout<<"Failed"; }

(3) DFS 和 BFS 的比较
DFS 优势 回溯类搜索比较适合 参数传递、状态修改和恢复都比较方便 自顶向下地处理问题 记忆化搜索容易实现 使用递归算法容易导致栈溢出(非递归算法不简洁) 有时不容易输出方案 BFS 解决“最少步数”问题 启发式搜索在BFS中更容易实现

缺点

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

BFS 可以换成迭代加深搜索。这样做虽然浪费了时间,但是可以节省空间。

+2.8 剪枝
(1) 最优化剪枝

(2) 可行性剪枝

Microsoft PowerPoint 演示文稿

剪枝

Microsoft PowerPoint 演示文稿

搜索

Microsoft Office Word 文档

USACO 内容

2.9 小结
搜索法:使用搜索法的目的是把尝试所有方案,然后找出合适的解。 ? 搜索法有以下几种方式: ? 枚举法——从可能的解的集合中一一枚举各元素, 并根据条件检验解的正确性。 它适用于深度较小的问 题。 ? 回溯——按照某种条件往前试探搜索,若前进中遭到失败,则回过头来另择通路继续搜索。深度优先搜 索的原理也是如此。 ? 广度优先搜索——和深度优先搜索的区别在于解答树的扩展方式。 ? 迭代加深搜索——迭代加深搜索实质是限定下界的深度优先搜索。使用广度优先搜索时没有足够空间, 时间又允许时,可以采用这种方法。 ? 写搜索时应遵循 KISS 原则(Keep it simple & stupid,“写最单纯愚蠢的程序”,意思是应把程序 写得尽量简洁) ? 另外,在搜索时可能会遇到很多无效的解,为了节省时间,就需要合理地减枝。

25

NOIP 复习资料(C++版)

第三单元

贪心算法

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

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

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

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

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

3.5 区间覆盖问题
【问题描述】数轴上有 n 个闭区间[ai, bi]。选择尽量少的区间来覆盖指定线段[s, t]。 【贪心策略】 1. 预处理:扔掉不能覆盖[s, t]的区间。 2. 把各区间按 a 从小到大排序。如果区间 1 的起点不是 s,无解,否则选择起点在 s 的最长区间。

26

NOIP 复习资料(C++版) 3. 选择此区间[ai, bi]后,问题转化了覆盖[bi, t],于是返回①,直到[s, t]被完全覆盖为止。

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

3.7 工序问题
【问题描述】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 从大到小排列。

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

3.9 马跳棋盘问题*
【问题描述】在一个 8×8 的国际象棋棋盘上,马( “马走日” )的初始位置(x, y)。怎么走可以不重复地走过 每一个格子?这样输出结果:如果马在第 i 步落在了格子(s, t)上,则在对应位置输出 i。 【贪心策略】马每次往前跳,都往这样的格子上跳——从这一点出发,能够到达的格子数最少。 #include <iostream> #include <iomanip> #include <conio.h> #include <cstdlib> using namespace std; #define ROW 8 #define LINE 8 #define NUM ROW*LINE //行数,可变 //列数,可变 //总格数

27

NOIP 复习资料(C++版) int board[ROW][LINE]; //两个数组存储对应的偏移量 int stepRow[8] = {-1,-2,-2,-1,1,2,2,1}; int stepLine[8] = {-2,-1,1,2,2,1,-1,-2}; //求 (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 + stepRow[( s + k )% 8]; j1 = j + stepLine[( s + k )% 8]; if( i1 >= 0 && i1 < ROW && j1 >= 0 && j1 < LINE && 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; m = exitn( i ,j ,s ,a); if( m == 0 ) return -1; //没有出口的情况 for(int min = 9, k = 0 ; k < m ; k++ ) { //逐个考虑取下一步最少的出口的出口 temp = exitn( i+stepRow[a[k]] , j+stepLine[a[k]] , s , b); if( temp < min ) { min = temp; kk = a[k]; } } return kk; } int main() { int i ,j , step ,no ,start ; //对每个位置的点都进行计算得到各个点的结果

28

NOIP 复习资料(C++版) //如果只想算某一个点的,把循环去掉换上相应的赋值语句就可以了 for( int sx = 0 ; sx < ROW ; sx++ ) for( int sy = 0 ; sy < LINE ; sy++ ){ start = 0; do { memset(board,0,sizeof(board)); board[sx][sy] = 1; i = sx; j = sy; for(step = 2 ; step <= NUM ; step++ ) { if((no = next(i,j,start)) == -1) break; i += stepRow[no]; j += stepLine[no]; board[i][j] = step; } if( step > NUM || no == -1) break; start++; } while( step <= NUM ); if( no != -1 ) { system("pause"); for( i = 0 ; i < ROW ; i++ ) { for( j = 0 ; j < LINE ; j++ ) cout <<setw(4)<<board[i][j]; //打印 cout <<endl; } } } return 0; }

3.10 小结
贪心策略:指从问题的初始状态出发,通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。 ? 贪心思想的本质是每次都形成局部最优解,换一种方法说,就是每次都处理出一个最好的方案。 ? 然而,贪心算法并不总是正确的,因为并不是每次局部最优解都会与整体最优解之间有联系,往往靠贪心生 成的解不是最优解。一般情况下,构造出贪心策略后要进行证明。 ? 如果有贪心性质存在,那么一定要采用贪心算法。因为它容易编写,容易调试,速度极快,并且节约空间。

29

NOIP 复习资料(C++版) ? 几乎可以说,它是所有算法中最好的。 在某些最小值问题中,可以利用贪心算法找到较优解。把这个较优解用于搜索(搜索时发现正在求的解比较 优解大,就立即剪枝,否则更新这个较优解) ,能够在一定程度上加快速度。

30

NOIP 复习资料(C++版)

第四单元
参见 58 页“7.1 常用排序方法” 。

分治算法

4.1 快速排序、归并排序

4.2 二分查找
参见 66 页“8.2 二分查找” 。

4.3 快速幂
举个例子,如果用朴素算法计算 a41,就需要做 41 次乘法运算。时间复杂度 O(n)。 使用分治算法,就有:a41=(a20)2·a,a20=(a10)2,a10=(a5)2,a5=(a2)2·a,a2=(a)2。只需 7 次乘法运算。 时间复杂度 O(logn)。

(1) 递归算法
long long quickpow(long long a, long long b) { if (b == 0) return 1; long long r=quickpow(a, b/2); r*=r; if (b%2) r=r*a; return r; }

(2) 非递归算法
long long quickpow(long long a, long long b) { long long d=1, t=a; while (b>0) { if (t==1) return d; if (b%2) d=d*t; b=b/2; t=t*t; } return d; } 类似的 ab mod n 代码如下: long long quickdiv(long long a, long long b, long long n)

31

NOIP 复习资料(C++版) { long long d=1, t=a; while (b>0) { if (t==1) return d; if (b%2) d=d*t%n; b=b/2; t=t*t%n; } return d; }

4.4 最长非降子序列
【问题描述】一个序列 a1,a2,a3,?,an 共 N 个元素。现在要求从序列找到一个长度最长、且前面一项不大 于它后面任何一项的子序列。只需算出这个序列的长度。N?100000。 /* 动态转移方程:f(i)=max{f(j)}+1(aj>ai且i>j) 用动态规划会超时,因为大部分时间都耗在了寻找max{f(j)}上面。 所以,可以维护一个数组C[x],表示 f(j) == x 时最小的a[k]。 则有C[1]?C[2]?……?C[n] 这样,就可以利用二分查找来确定f[j]了。 */ int a[100001], C[100001], f[100001], n; …… int lower_bound(int *a, int x, int y, int v) { int mid; while (x<y) { mid=x+(y-x)/2; if (a[m]>=v) y=m; else x=m+1; } return x; } int LIS() { int j; int len=1; C[0] = a[0]; f[0] = 1; for (int i=1; i<n; i++) { // 二分查找求下界

// 最长非降子序列

32

NOIP 复习资料(C++版) if (a[j]<C[0]) j=0; else if (a[i]>=C[len-1]) j=len++; else j=lower_bound(a, 0, len, s[i]); C[j] = a[i]; f[i] = j+1; } return len; }

4.5 求逆序对个数
【问题描述】对于一个序列 a1,a2,a3,?,an,如果存在 i,j(i<j) ,使 ai>aj,那么 ai,aj 就是一个逆序对。 现在给你一个有 N 个元素的序列,请求出序列内逆序对的个数。N?100000。 【提示】借助归并排序来进行统计。 int cnt=0; // 逆序对个数 void MergeSort(int l, int r) { int mid, i, j, tmp; if( r > l+1 ) { mid = (l+r)/2; MergeSort(l, mid); MergeSort(mid, r); tmp = l; or( 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]; } } // 使用排序,就可以方便地数跨“分界”的逆序对个数了

+4.6?

棋盘覆盖问题

【问题描述】求用 1×2 的多米诺骨牌,覆盖 5×n 的棋盘的方法数。

33

NOIP 复习资料(C++版) 首先做一个判断:如果 5×n 是奇数,那么一定无解。

4.7 小结
分治策略:对于一个规模为 n 的问题,若该问题可以容易地解决(比如说规模 n 较小)则直接解决,否则 将其分解为 k 个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将 各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 分治法所能解决的问题一般具有以下几个特征: 1. 该问题的规模缩小到一定的程度就可以容易地解决。 2. 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。 3. 利用该问题分解出的子问题的解可以合并为该问题的解。 4. 该问题所分解出的各个子问题是相互独立的,即子问题之间没有交集。 伪代码如下: void solve(p) { if (p的规模够小) { 用简单的办法搞定 } // 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题。 // 一般把问题分成规模大致相同的两个子问题。 for (int i=1;i<=k;i++) 把p分解,第i个子问题为pi // 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题。 for (int i=1;i<=k;i++) solve(pi); // 合并:将各个子问题的解合并为原问题的解。 …… }

// p表示问题的范围、规模或别的东西。

34

NOIP 复习资料(C++版)

第五单元

动态规划(DP)

5.1 导例:数字三角形
数字三角形是一个经典例题,它可以说明很多问题。 【问题描述】有一个数字三角形(如下图) 。现有一只蚂蚁从顶层开始向下走,每走下一级时,可向左下方向或 右下方向走。求走到底层后它所经过的数的最大值。 1 6 3 8 2 6 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) 递推
划分阶段:按行划分阶段,一行为一个阶段。 令 f[i][j]为 第 i 行第 j 列上点到起点的最大和。所有下标从 1 开始。
?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] = (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], max; // max表示计算结果 …… for (int i=1;i<=n;i++) { max=0; for (int j=1;j<=i;j++) max >?= f[i][j] = (f[i-1][j] >? f[i-1][j-1]) + a[i][j]; } cout<<max;

35

NOIP 复习资料(C++版)

(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; F[x][y] = (F[i+1][j] >? F[i+1][j+1]) + a[i][j]; visited[x][y] = true; } …… 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 max,p; for (int i=1;i<=n;i++) { max=p=0; for (int j=1;j<=i;j++) { // p表示终点的位置

36

NOIP 复习资料(C++版) f[i][j] = f[i-1][j] + a[i][j]; g[i][j] = 1; // 状态转移方程中有两个选择,现在是第一个。 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 (max > f[i][j]) max=f[i][j],p=j; } } cout<<max; printpath(n, p);

(5) 使用滚动数组
“空间换时间”虽然很好,但是有的时候,数组根本开不下! 递推的时候,我们发现 f 有 n 行,但只有两行参与了计算。所以可以把 f 变成 f[1][N]来节省空间。 计算的时候,要让 i 和 i-1 对 2 取模,即 f[i%2][j] = (f[(i-1)%2][j] >? f[(i-1)%2][j-1]) + a[i][j]; 然而,要求输出字典序最小的解决方案时,最好不要使用滚动数组。 ( “字典序最小” :一要保证步骤最少,二要保证在步骤相同的情况下,优先选择序号靠前的决策)

(6) 无奈的解法
如果你在竞赛时被动态规划题卡住,就需要想其他方法获取部分分数。 ① 贪心算法: 每次都选择数字大的方向走。不过很容易证明,贪心算法是错误的——局部最优不一定全局最优。 ② 暴力搜索法: int max = 0; void try(int x, int y, int deep, int sum) { if (deep==n) { max >?= sum; return; } else { try(x+1,y,deep+1,sum + a[x+1,y]); try(x+1,y+1,deep+1,sum + a[x+1,y+1]); } } 调用 try(1,1,1,a[1][1])即可。时间复杂度 O(2n)。 ③ 贪心+搜索:

37

NOIP 复习资料(C++版) 对于某些求最小值的问题,可以先用贪心算法得到较优解。然后开始搜索。 搜索时只要计算结果比已求得的最小值大就剪枝。搜索到顶点时更新最小值。 不过,求最大值的问题不能使用此方法。

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

(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 堆合并所能获得 的最小价值。 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 "cstdlib" #include "iostream" using namespace std; #define INF 10000000 #define d(i,j) (s[j]-s[i-1]) int f1[101][101],f2[101][101]; int v[201], s[201]; int n; int main()

38

NOIP 复习资料(C++版) { cin>>n; memset(f1, 0, sizeof(f1)); memset(f2, 0, sizeof(f2)); memset(s, 0, sizeof(s)); 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] >?= f1[i][k]+f1[k+1][j]+d(i,j); f2[i][j] <?= f2[i][k]+f2[k+1][j]+d(i,j); } cout<<"f2["<<i<<"]["<<j<<"]="<<f2[i][j]<<endl; } } int max=0, min=INF; for (int i=1;i<=n;i++) { max >?= f1[i][i+n-1]; min <?= f2[i][i+n-1]; } cout<<max<<" "<<min<<endl; return 0; } 时间复杂度:O(n3)

(3) 能量项链(NOIP2006, 1)
思路是相似的——阶段、状态都一样,而得分的方式变了。 /* ① 设第i个珠子的头标记是value[i],然后规定所有下标都是从1开始。 ② 设f(i,j)为从i到j这一条链的最大值,那么

39

NOIP 复习资料(C++版) f(i,j) = max{f(i,k)+f(k,j)+v[i]*v[k+1]*v[j+1]} 边界条件 f(k,k)=0 ③ 把环拉成链:再复制一遍,然后当做正常的来DP */ #include "fstream" #include "cstdlib" #include "iostream" using namespace std; ifstream fin("energy.in"); ofstream fout("energy.out"); int f[1001][1001]; int n; int value[2001]; int main() { fin>>n; for (int i=1;i<=n;i++) { fin>>value[i]; value[n+i]=value[i]; } memset(f, 0, sizeof(f)); for (int p=1;p<n;p++) { for (int i=1,j=i+p ; (i<n+n)&&j<=(n+n) ; i++,j=i+p) { f[i][j]=0; for (int k=i;k<j;k++) f[i][j] >?= f[i][k]+f[k+1][j]+value[i]*value[k+1]*value[j+1]; } } int max=0; for (int i=1;i<=n;i++) max >?= f[i][i+n-1]; fout<<max; return 0; } // 把环拉成链 其中i<=k<j

40

NOIP 复习资料(C++版)

5.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[i][j]表示从起点出发走到(i,j)时经过数字总和的最大值。
?f[i-1][j] 3. 状态转移方程:f[i][j]=max?f[i][j-1]+a[i][j] ?

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

(2) 变式问题
① 必须经过某点 可以这样做:将取数过程分成两部分。第一部分的起点是(1,1),终点是这个点;第二部分的起点是这个点,终 点是(m,n)。比如,要求必须过(3,2),就可以按下图把问题一分为二: 1 8 7 1 5 6 2 0 9 4 5 1 8 7 1 4 2 3 6 3

② 不能经过某点 一个简单的办法是:把那个点的值设置成一个负数。 ③ 不允许连续三次向下走(不允许连续两次的太简单,研究意义不大) 可以在状态中加一维,表示“向下走的次数” 1. 状态表示:? 2. 状态转移方程:?

(3) 双向取数问题——传纸条(NOIP2008, 3)
首先要对问题进行一下转化——从左上角出发,通过两条互不相交的路径到达右下角。 如果还使用上面的动态转移方程,就会出现“局部最优不一定是全局最优”的问题。很有可能在第一条路径选择 完成后,第二条路径无法到达终点! 方法一:双进程动态规划 设(i,j)、(k,l)为两条路径上的点,f[i,j][k,l](其实是 f[i][j][k][l])表示两条线路从起点出发, 分别到达这两个点时经过的数字和的最大值,那么 f[i,j][k,l]=max{f[i-1,j][k,l]+a[i,j], f[i,j-1][k,l]+a[i,j],

41

NOIP 复习资料(C++版) f[i,j][k-1,l]+a[k,l] f[i,j][k,l-1]+a[k,l]} 注意交叉的处理。 复杂度 O(n4) 方法二: 可以发现,只要知道移动步数和两个横坐标,那么两个纵坐标就可以计算出来。 设两张纸条同时从(1,1)开始传,传往(n,m),f[i,j1,j2]表示第 i 步,第一张纸条、 第二张纸条的纵坐标分别是 j1,j2 f[i,j1,j2]=max(f[i-1,j1,j2],f[i-1,j1-1,j2],f[i-1,j1,j2-1],f[i-1,j1-1,j2-1])+a[ij1+1, j1]+a[i-j2+1,j2] 另外如果 j1=j2 且 i<>n+m-1 则 f[i,j1,j2]=-maxlongint 两个纸条无法传递 到同一个人上

5.4 背包问题
参见 48 页“第六单元 背包专题” 。

5.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 LCS(int *a, int n) { int max; for (int i=1;i<=n;i++) { 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 (i=1;i<=n;i++) max >?= f[i];

42

NOIP 复习资料(C++版) return max; }

+(2) 最长公共子序列(LCS)
【问题描述】有两个序列 a 和 b。求一个最长的序列 p,使它既是 a 的子序列,又是 b 的子序列。输出序列的长 度。 (a、b 长度小于 1000) 1. 划分阶段: 2. 状态表示:f(i,j)表示 a 的前 i 个元素、b 的前 j 个元素中最长公共子序列的长度。 3. 状态转移方程: int f[1001][1001]; int LCS(int *a, int m, int *b, int n) { memset(f,0,sizeof(f)); } // a 中 m 个元素,b 中 n 个元素

int LCS(const char *s1, const char *s2) { // s1:0...m, s2:0...n int m = strlen (s1), n = strlen (s2); int i, j; memset(f,0,sizeof(f)); for ( i=1; i <= m; ++i ) for ( j=1; j <= n; ++j ){ if(s1[i-1]==s2[j-1]) f[i][j] = f[i-1][j-1]+1; else if(f[i-1][j]>f[i][j-1])f[i][j]= f[i-1][j]; else f[i][j] = f[i][j-1]; } return f[m][n]; }

5.6 表达式问题:乘积最大
【问题描述】 (NOIP2000,2) 在一个长度为 n 的非 0 数字串中插入 k 个乘号, 使表达式的值最大。 (6?n?40,1 ?k?6) 1. 划分阶段:以一个乘号为一个阶段。 2. 状态表示:f(i,l)表示前 i 个数字插入 l 个乘号之后的最大乘积。 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 个数字之后表示的整数。 …… // 省略一些声明,包括高精度算法 int n, k; hp f[51][21], s[51][51];

43

NOIP 复习资料(C++版) 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; t=c-'0'; s[i][i]=t; 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<=(i-1 <? k);l++) { f[i][l] = 0; for (int j=l;j<i;j++) f[i][l] = f[i][l] >? (f[j][l-1]*s[j+1][i]); } cout<<f[n][k]<<endl; return 0; } // 递推计算s

+5.7 DAG 上的最短路径
(1) 最短路径的动态规划解法
【问题描述】一个有向无环图。求从起点 start 出发,到终点 end 的最短路径长。 1. 状态表示:f(j)为 start 到 j 的最短路径长。 2. 状态转移方程:f(j)=max{f(i)}+G[i][j],i 是 j 的前驱。

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

44

NOIP 复习资料(C++版)

问题的关键:构造出一个 DAG。

+5.8 树型动态规划:加分二叉树

(加分二叉树,NOIP2003,3) ①根-》叶:不常见 ②叶-》根: 例题:加分二叉树

+5.9 Bitonic 旅行
历史上有一个著名的“货郎担问题” (也叫“中国邮路问题”:已知 n 个点两两间的距离,给出过这些定 ) 点的最短闭合回路。 (有时把这 n 个定点间距离定 义为欧氏几何平面上距离,称“ 欧几里德旅行商问

45

NOIP 复习资料(C++版) 题”) 。 这个问题是 NP- 难问题,只能用搜索解决。 后来,J. L. Bentley 提出了这个问题的变形——Bitonic Tour 问题(又称双调旅程问题) 。 Bitonic 旅行:已知地图上 n 个旅行须到达的城市,要求从最西端的城市开始,严格地由西向东到最 东端的城市,再严格地由东向西回到出发点,除出发点外 每个城市经过且只经过一次。给出路程的最 短值。 数据规模:1?n?1000 你可能会这么想:按旅行顺序每过一个城市为一阶段。可是这样,状态量需要记录由东向西每一步所经 过的城市,时间复杂度 O(2^n),与搜索无异! 我们需要换一种状态转化方式。 递推思路——从最东端开始,找两条到最西端的路径。将地点按从东到西编号,每加入一个地点为一个阶 段。计算从地点 i 到最东再到地点 j 路程的最小值 f(i,j) ,这个过程是递推的。最后求出 min{f(n,k)+dist[n,k]}。 动态转移方程—— f(i,j)=f(i-1,j)+dist[i,i-1],1?j?i-2,i ?n f(i,j)=f(i,j-1)+dist[j,j-1],1?j=i-1,i?n (实现时注意对边界情形的处理) ,其中 dist[i,j]表示 i 与 j 间距离。 时间复杂度为 O(n^2),很好。附件中给出源代码。

+5.10 资源分配问题

5.11 小结
动态规划:各个阶段采取的决策依赖于当前状态,又随即引起状态的转移,在变化的状态中产生一个决策序列, 称这种解决多阶段决策最优化问题的方法为动态规划方法。 ? 动态规划的基本思想:努力避免重复解决相同问题或子问题。

46

NOIP 复习资料(C++版) ? ? 动态规划的优点:比搜索快 动态规划的适用范围:状态必须满足最优化原理,状态必须满足无后效性。 恰当地划分阶段、表示状态可以很快解决问题。不恰当地划分阶段、表示状态会使问题复杂,甚至不能用动 态规划解决。 找到子问题是进行动态规划的重要一步。 一般情况下,动态规划问题要用递推的方式求解。如果递推顺序不容易确定,也可以使用记忆化搜索。 ? 塔形、方格形数据——可以以每一层为一个阶段,逐层递推。 ? 把区间[i,j]分割成两部分——可以按 j-i 的差值递推。 ? 串——应该把前 k 个字符处理完,然后解决前 k+1 个字符。 ? 树——一般先把叶子节点的最优值求出来,再把某些信息传给根。 ? 递推方法还有很多,需要自己不断积累??

? ?

47

NOIP 复习资料(C++版)

第六单元

背包专题

6.1 部分背包
参见 26 页“3.1 部分背包问题” 。部分背包问题是贪心算法问题,其他背包问题都是动态规划问题、

6.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] >?= f[i-1][c-w[i]] + v[i]; } 时间复杂度、空间复杂度:都是 O(NC)

(2) 一维数组表示
1. 定义状态:由于递推的过程和铺地毯类似,所以可以把 i 省略。
?f[c] 2. 状态转移方程:f[c]=max? ?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] >?= 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 = (C - sumw) >? (w[i]); for (int c=C;c>=bound;c--) if (c>=w[i]) f[c] >?= f[c-w[i]] + v[i];

48

NOIP 复习资料(C++版) }

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

6.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×

?w[i]),比较大。
C

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

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

(第二行变了)

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

(1) 转化为 0/1 背包——二进制法
按照二进制分割物品。比方说,物品 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++) // 完全背包 if (c>=w[i]) f[c] >?= f[c-w[i]] + v[i]; }

49

NOIP 复习资料(C++版) 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] >?= 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] >?= f[c-w[i]] + amount*v[i]; } } 时间复杂度:O(V×?logw[i])

(2) 使用优先队列的算法**

6.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。求解将哪些物品装入背包可使价值总和最大。

50

NOIP 复习资料(C++版) 只需把问题变一下——有 N 件物品和一个容量为 C、容积为 M 的背包。第 i 件物品的重量是 w[i],体积是 1, 价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。 把最大个数看做一种容积就可以了。

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

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

6.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] >?= f[c-w[i]] + v[i]; 在“金明的预算方案” (NOIP2006,2)中,就可以把主件、附件组合成一个分组背包(一组最多 4 个物体,最 少 1 个物体) 。

+6.7 有依赖的背包问题
简化的问题 这种背包问题的物品间存在某种“依赖”的关系。也就是说,i 依赖于 j,表示若 选物品 i,则必须选物品 j。为了简化起见,我们先设没有某个物品既依赖于别的物品,又被别的 物品所依赖;另外,没有某件物品同时依赖多件物品。 算法 这个问题由 NOIP2006 金明的预算方案一题扩展而来。遵从该题的提法,将不依赖于别 的物品的物品称为“主件” ,依赖于某主件的物品称为“附件” 。由这个问题的简化条件可知所 有的物品由若干主件和依赖于每个主件的一个附件集合组成。 按照背包问题的一般思路,仅考虑一个主件和它的附件集合。可是,可用的策略非常多,包 括:一个也不选,仅选择主件,选择主件后再选择一个附件,选择主件后再选择两个附件?? 无法用状态转移方程来表示如此多的策略。 (事实上,设有 n 个附件,则策略有 2n+ 1 个,为指数级。 ) 考虑到所有这些策略都是互斥的(也就是说,你只能选择一种策略) ,所以一个主件和它的 附件集合实际上对应于 P06 中的一个物品组,每个选择了主件又选择了若干个附件的策略对应 于这个物品组中的一个物品,其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步 转化并不能给出一个好的算法,因为物品组中的物品还是像原问题的策略一样多。 再考虑 P06 中的一句话:可以对每组中的物品应用 P02 中“一个简单有效的优化” 。这提示我 们,对于一个物品组中的物品,所有费用相同的物品只留一个价值最大的,不影响结果。所以,

51

NOIP 复习资料(C++版) 我们可以对主件 i 的“附件集合”先进行一次 01 背包,得到费用依次为 0..V-c[i]所有这些值时相应 的最大价值 f'[0..V-c[i]]。那么这个主件及它的附件集合相当于 V-c[i]+1 个物品的物品组,其中费 用为 c[i]+k 的物品的价值为 f'[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的,通 过一次 01 背包后,将主件 i 转化为 V-c[i]+1 个物品的物品组,就可以直接应用 P06 的算法解决问题 了。 较一般的问题更一般的问题是:依赖关系以图论中“森林”的形式给出(森林即多叉树的集 合) ,也就是说,主件的附件仍然可以具有自己的附件集合,限制只是每个物品最多只依赖于一 个物品(只有一个主件)且不出现循环依赖。 解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是, 由于附件可能还有附件,就不能将每个附件都看作一个一般的 01 背包中的物品了。若这个附件 也有附件集合,则它必定要被先转化为物品组,然后用分组的背包问题解出主件及其附件集合 所对应的附件组中各个费用的附件所对应的价值。 事实上,这是一种树形 DP,其特点是每个父节点都需要对它的各个儿子的属性进行一次 DP 以 求得自己的相关属性。这已经触及到了“泛化物品”的思想。看完 P08 后,你会发现这个“依赖 关系树”每一个子树都等价于一件泛化物品,求某节点为根的子树对应的泛化物品相当于求其 所有儿子的对应的泛化物品之和。 小结 NOIP2006 的那道背包问题我做得很失败,写了上百行的代码,却一分未得。后来我通 过思考发现通过引入“物品组”和“依赖”的概念可以加深对这题的理解,还可以解决它的推广 问题。用物品组的思想考虑那题中极其特殊的依赖关系:物品不能既作主件又作附件,每个主 件最多有两个附件,可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组, 这便揭示了问题的某种本质。 我想说:失败不是什么丢人的事情,从失败中全无收获才是。

+6.8 泛化物品
定义考虑这样一种物品,它并没有固定的费用和价值,而是它的价值随着你分配给它的费 用而变化。这就是泛化物品的概念。 更严格的定义之。在背包容量为 V 的背包问题中,泛化物品是一个定义域为 0..V 中的整数的 函数 h,当分配给它的费用为 v 时,能得到的价值就是 h(v)。 这个定义有一点点抽象,另一种理解是一个泛化物品就是一个数组 h[0..V],给它费用 v,可 得到价值 h[V]。 一个费用为 c 价值为 w 的物品,如果它是 01 背包中的物品,那么把它看成泛化物品,它就是 除了 h(c) =w 其它函数值都为 0 的一个函数。如果它是完全背包中的物品,那么它可以看成这样 一个函数,仅当 v 被 c 整除时有 h(v) =v/c*w,其它函数值均为 0。如果它是多重背包中重复次数最 多为 n 的物品,那么它对应的泛化物品的函数有 h(v) =v/c*w 仅当 v 被 c 整除且 v/c?n,其它情况函数值均 为 0。 一个物品组可以看作一个泛化物品 h。对于一个 0..V 中的 v,若物品组中不存在费用为 v 的的 物品,则 h(v)=0,否则 h(v)为所有费用为 v 的物品的最大价值。P07 中每个主件及其附件集合等价 于一个物品组,自然也可看作一个泛化物品。 泛化物品的和如果面对两个泛化物品 h 和 l,要用给定的费用从这两个泛化物品中得到最大 的价值,怎么求呢?事实上,对于一个给定的费用 v,只需枚举将这个费用如何分配给两个泛化 物品就可以了。同样的,对于 0..V 的每一个整数 v,可以求得费用 v 分配到 h 和 l 中的最大价值 f(v)。 也即

可以看到,f 也是一个由泛化物品 h 和 l 决定的定义域为 0..V 的函数,也就是说,f 是一个由泛化物 品 h 和 l 决定的泛化物品。

52

NOIP 复习资料(C++版) 由此可以定义泛化物品的和:h、l 都是泛化物品,若泛化物品 f 满足以上关系式,则称 f 是 h 与 l 的 和。这个运算的时间复杂度取决于背包的容量,是 (V2)。 泛化物品的定义表明:在一个背包问题中,若将两个泛化物品代以它们的和,不影响问题 的答案。事实上,对于其中的物品都是泛化物品的背包问题,求它的答案的过程也就是求所有 这些泛化物品之和的过程。设此和为 s,则答案就是 s[0..V]中的最大值。 背包问题的泛化物品一个背包问题中,可能会给出很多条件,包括每种物品的费用、价值 等属性,物品之间的分组、依赖等关系等。但肯定能将问题对应于某个泛化物品。也就是说,给 定了所有条件以后,就可以对每个非负整数 v 求得:若背包容量为 v,将物品装入背包可得到的 最大价值是多少,这可以认为是定义在非负整数集上的一件泛化物品。这个泛化物品――或者 说问题所对应的一个定义域为非负整数的函数――包含了关于问题本身的高度浓缩的信息。一 般而言,求得这个泛化物品的一个子域(例如 0..V)的值之后,就可以根据这个函数的取值得到 背包问题的最终答案。 综上所述,一般而言,求解背包问题,即求解这个问题所对应的一个函数,即该问题的泛化 物品。而求解某个泛化物品的一种方法就是将它表示为若干泛化物品的和然后求之。 小结本讲可以说都是我自己的原创思想。具体来说,是我在学习函数式编程的 Scheme 语言 时,用函数编程的眼光审视各类背包问题得出的理论。这一讲真的很抽象,也许在“模型的抽象 程度”这一方面已经超出了 NOIP 的要求,所以暂且看不懂也没关系。相信随着你的 OI 之路逐渐 延伸,有一天你会理解的。 我想说: “思考”是一个 OIer 最重要的品质。简单的问题,深入思考以后,也能发现更多。

6.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] >?= f[c-w[i]] + v[i]; } else if (物品i属于完全背包) { // 按照完全背包的做法取物品i for (int c=0;c<=C;c++) if (c>=w[i]) f[c] >?= f[c-w[i]] + v[i]; } else if (物品i属于多重背包) { // 按照多重背包的做法取物品i …… }

53

NOIP 复习资料(C++版)

+6.10 特殊要求
+(1) 输出字典序最小的最优方案
输出字典序最小的最优方案这里“字典序最小”的意思是 1..N 号物品的选择方案排列出来 以后字典序最小。以输出 01 背包最小字典序的方案为例。 一般而言,求一个字典序最小的最优方案,只需要在转移时注意策略。首先,子问题的定 义要略改一些。我们注意到,如果存在一个选了物品 1 的最优方案,那么答案一定包含物品 1,原 问题转化为一个背包容量为 v-c[1],物品为 2..N 的子问题。反之,如果答案不包含物品 1,则转化 成背包容量仍为 V,物品为 2..N 的子问题。不管答案怎样,子问题的物品都是以 i..N 而非前所述 的 1..i 的形式来定义的,所以状态的定义和转移方程都需要改一下。但也许更简易的方法是先把 物品逆序排列一下,以下按物品已被逆序排列来叙述。 在这种情况下,可以按照前面经典的状态转移方程来求值,只是输出方案的时候要注意: 从 N 到 1 输入时,如果 f[i][v] == f[i 1][i v]及 f[i][v] == f[i 1][f c[i]] +w[i]同时成立, 应该按 照后者(即选择了物品 i)来输出方案。

+(2) 求方案总数
对于一个给定了背包容量、物品费用、物品间相互关系(分组、依赖等)的背包 问题,除了再给定每个物品的价值后求可得到的最大价值外,还可以得到装满背包或将背包装 至某一指定容量的方案总数。 对于这类改变问法的问题,一般只需将状态转移方程中的 max 改成 sum 即可。例如若每件物 品均是完全背包中的物品,转移方程即为 f[i][v] = sumff[i 1][v];f[i][v c[i]]g 初始条件 f[0][0]=1。 事实上,这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案。

+(3) 最优方案的总数
这里的最优方案是指物品总价值最大的方案。以 01 背包为例。 结合求最大总价值和方案总数两个问题的思路,最优方案的总数可以这样求:f[i][v]意义同 前述,g[i][v]表示这个子问题的最优方案的总数,则在求 f[i][v]的同时求 g[i][v]的伪代码如下:

54

NOIP 复习资料(C++版)

+(4) 求次优解、第 K 优解
对于求次优解、第 K 优解类的问题,如果相应的最优解问题能写出状态 转移方程、用动态规划解决,那么求次优解往往可以相同的复杂度解决,第 K 优解则比求最优解 的复杂度上多一个系数 K。 其基本思想是将每个状态都表示成有序队列,将状态转移方程中的 max/min 转化成有序队 列的合并。这里仍然以 01 背包为例讲解一下。 首先看 01 背包求最优解的状态转移方程:f[i][v] = maxff[i 1][v];f[i 1][v c[i]] +w[i]g。如 果要求第 K 优解,那么状态 f[i][v]就应该是一个大小为 K 的数组 f[i][v][1..K]。其中 f[i][v][k]表示 前i个 物品、背包大小为 v 时,第 k 优解的值。 “f[i][v]是一个大小为 K 的数组”这一句,熟悉 C 语言的同学 可能比较好理解,或者也可以简单地理解为在原来的方程中加了一维。显然 f[i][v][1..K]这 K 个数 是由大到小排列的,所以我们把它认为是一个有序队列。 然后原方程就可以解释为:f[i][v]这个有序队列是由 f[i-1][v]和 f[i-1][v-c[i]]+w[i]这两个有序队 列 合 并 得 到 的 。 有 序 队 列 f[i-1][v] 即 f[i-1][v][1..K] , f[i-1][v-c[i]]+w[i] 则 理 解 为 在 f[i-1][v-c[i]][1..K]的每个数 上加上 w[i]后得到的有序队列。合并这两个有序队列并将结果的前 K 项储存到 f[i][v][1..K]中的复杂 度是 O(K)。最后的答案是 f[N][V][K]。总的复杂度是 (V NK)。 为什么这个方法正确呢?实际上,一个正确的状态转移方程的求解过程遍历了所有可用的 策略,也就覆盖了问题的所有方案。只不过由于是求最优解,所以其它在任何一个策略上达不 到最优的方案都被忽略了。如果把每个状态表示成一个大小为 K 的数组,并在这个数组中有序 的保存该状态可取到的前 K 个最优值。那么,对于任两个状态的 max 运算等价于两个由大到小的 有序队列的合并。 另外还要注意题目对于“第 K 优解”的定义,将策略不同但权值相同的两个方案是看作同一 个解还是不同的解。如果是前者,则维护有序队列时要保证队列里的数没有重复的。 小结显然,这里不可能穷尽背包类动态规划问题所有的问法。甚至还存在一类将背包类动 态规划问题与其它领域(例如数论、图论)结合起来的问题,在这篇论背包问题的专文中也不会 论及。但只要深刻领会前述所有类别的背包问题的思路和状态转移方程,遇到其它的变形问法, 只要题目难度还属于 NOIP,应该也不难想出算法。 触类旁通、举一反三,应该也是一个 OIer 应有的品质吧。

+6.11 背包问题的搜索解法
对于 01 背包问题,简单的深搜的复杂度是 (2N)。就是枚举出所有 2N 种将物品放入背包的方案,然后找最优 解。基本框架如下:

55

NOIP 复习资料(C++版) 搜索的剪枝基本的剪枝方法不外乎可行性剪枝或最优性剪枝。可行性剪枝即判断按照当前 的搜索路径搜下去能否找到一个可行解,例如:若将剩下所有物品都放入背包仍然无法将背包 充满(设题目要求必须将背包充满) ,则剪枝。最优性剪枝即判断按照当前的搜索路径搜下去能 否找到一个最优解,例如:若加上剩下所有物品的权值也无法得到比当前得到的最优解更优的 解,则剪枝。 搜索的顺序在搜索中,可以认为顺序靠前的物品会被优先考虑。所以利用贪心的思想,将 更有可能出现在结果中的物品的顺序提前,可以较快地得出贪心地较优解,更有利于最优性剪 枝。所以,可以考虑将按照“性价比” (权值/费用)来排列搜索顺序。另一方面,若将费用较大 的物品排列在前面,可以较快地填满背包,有利于可行性剪枝。最后一种可以考虑的方案是:在 开始搜索前将输入文件中给定的物品的顺序随机打乱。这样可以避免命题人故意设置的陷阱。 以上三种决定搜索顺序的方法很难说哪种更好,事实上每种方法都有适用的题目和数据,也有 可能将它们在某种程度上混合使用。 子集和问题子集和问题是一个 NP-Complete 问题,与前述的(加权的)01 背包问题并不相同。 给定一个整数的集合 S 和一个整数 X,问是否存在 S 的一个子集满足其中所有元素的和为 X。这个 问题有一个时间复杂度为 (2 N 2 )的较高效的搜索算法,其中 N 是集合 S 的大小。第一步思想是二 分。将集合 S 划分成两个子集 S1 和 S2,它们的大小都是 N/2。对于 S1 和 S2,分别枚举出它们所有 的2 N 2 个子集和,保存到某种支持查找的数据结构中,例如 hash set。然后就要将两部分结果合 并,寻找是否有和为 X 的 S 的子集。事实上,对于 S1 的某个和为 X1 的子集,只需寻找 S2 是否有和 为 X-X1 的子集。假设采用的 hash set 是理想的,每次查找和插入都仅花费 (1)的时间。两步的时 间复杂度显然都是 (2 N 2 )。实践中,往往可以先将第一步得到的两组子集和分别排序,然后再用 两个指针扫描的方法查找是否有满足要求的子集和。这样的实现,在可接受的时间内可以解决 的最大规模约为 N=42。 搜索还是 DP? 在看到一道背包问题时,应该用搜索还是动态规划呢?首先,可以从数据范 围中得到命题人意图的线索。如果一个背包问题可以用 DP 解,V 一定不能很大,否则 (V N)的 算法无法承受,而一般的搜索解法都是仅与 N 有关,与 V 无关的。所以,V 很大时(例如上百万) , 命题人的意图就应该是考察搜索。另一方面,N 较大时(例如上百) ,命题人的意图就很有可能 是考察动态规划了。另外,当想不出合适的动态规划算法时,就只能用搜索了。例如看到一个从 未见过的背包中物品的限制条件,无法想出 DP 的方程,只好写搜索以谋求一定的分数了。

6.12 小结
本单元基本上都是《背包九讲》里的内容。这是一本经典的教程,这本教程给了很多的启示。 1. 0/1 背包问题是一个很重要的问题,也是其他背包问题的基础。 2. 可以使用滚动数组优化空间复杂度。 3. 按照二进制划分一个数 N,既可以保证把 1~N 取遍,又可以使划分出的数尽可能少。 4. 使用堆或优先队列可以优化 DP。不过,NOIP 用不到这样的优化。 5. 比自己已经掌握的问题多一个限制条件时,可以考虑在状态中多加一维。 6. 由于背包问题以物品为阶段,所以决策时可以“具体问题具体分析” 。混合背包问题就是这样。 7. 由于动态规划考虑了所有方案,所以可以把动态规划问题变成统计问题。

56

NOIP 复习资料(C++版) 8. 字典序最小:一方面是长度尽可能短;另一方面,在选择时,只要解相同,就选关键字最小的方案。 9. 动态规划问题可以用搜索解决,不过要慢很多。

57

NOIP 复习资料(C++版)

第七单元

排序算法

7.1 常用排序方法
(1) 调用库函数
平均时间:O(nlogn) 首先要引用头文件:#include <algorithm> ① 调用方法:sort(第一项的地址, 最后一项的地址) // 例如 sort(&a[0],&a[n]);或 sort(a,a+n) ② 自定义规则的排序: int cmp(const int i, const int j) {return a[i]<a[j];} // 自定义比较规则 …… sort(a, a+n, cmp);

(2) 快速排序( “快排” )
平均时间:O(nlogn),最坏时间:O(n2) 如果不考虑最坏情况,快速排序是基于比较的排序算法中最快的一种算法。 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--; if (a[high]<check) temp=a[high], a[high]=a[low], a[low]=temp; while (a[low]<=check&&low<high) low++; 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); if (high<end) quicksort(a, high, end); // 合并:此时数组已经有序,所以不用额外操作了。 } 快速排序的版本很多,上面只是众多版本中的一种。

58

NOIP 复习资料(C++版) 快速排序的三个优化方法: 1. 规模很小时(如 end-start<10) ,可以什么都不做。快速排序过程全部结束之后,数组应该是基本有序 的,这时调用插入排序,完成整个排序过程。 2. 极端数据(如比较有序的数组)会使快速排序变慢,甚至退化为冒泡排序。可以采用“三者取中法”来解决 这个问题:令 check 等于 a[start]、a[end]、a[(start+end)/2]中的中间值。 3. 使用栈模拟递归。

(3) 归并排序
时间复杂度:O(nlogn) 注意,其他排序算法的空间复杂度是 O(1),而归并排序的空间复杂度很大,为 O(n)。 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); // 合并 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]; }

7.2 简单排序算法
以下几种排序算法的时间复杂度是 O(n2)。

(1) 插入排序
// 对a进行一次扫描,每遇到一个数,都把它插入到合适的位置。 void ins_sort(int *a, int start, int end) { int j,k; for (int i=start+1; i<=end; i++) { k=a[i]; j=i-1; while (k<a[j] && j>=start) a[j+1]=a[j], j--; a[j+1]=k;

59

NOIP 复习资料(C++版) } }

(2) 选择排序
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) 冒泡排序
void bubble_sort(int *a, int start, int end) { int temp; for (int i=start; i<=end; i++) for (int j=end-1; j>start; j--) if (a[j-1]>a[j]) { temp=a[j-1]; a[j-1]=a[j]; a[j]=temp; } }

7.3 线性时间排序
以下几种排序算法的时间复杂度为 O(n),因为它们使用的不是基于比较的排序。

(1) 桶排序
注意事项:待排序的数据范围不太大(比如 1~1000 可以考虑桶排序,而 1~100000 就必须用快速排序) 。 int count[M]; // 设计M个桶,M最好比数据的最大值大一点点 memset(count,0,sizeof(count)); for (int i=0; i<N; i++) count[a[i]]++; // 从count[0]开始挨个列举就行了。例如 for (int i=0; i<M; i++) while (count[i--]>0) cout<<i<<" ";

60

NOIP 复习资料(C++版)

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

+(3) 基数排序
基本思想:对 n 个元素依次按 k,k-1,...1 位上的数字进行桶排序。 program jspx; const n=8; type link=^node; node=record data:integer; next:link; end; var i,j,l,m,k:integer; a:array[1..n] of integer; s:string; q,head:array[0..9] of link; p,p1:link; begin writeln('Enter data:'); for i:=1 to n do read(a[i]); for i:=5 downto 1 do begin for j:=0 to 9 do begin new(head[j]); head[j]^.next:=nil; q[j]:=head[j] end; for j:=1 to n do begin str(a[j],s); for k:=1 to 5-length(s) do s:='0'+ s; m:=ord(s[i])-48; new(p); p^.data:=a[j];

61

NOIP 复习资料(C++版) p^.next:=nil; q[m]^.next:=p; q[m]:=p; end; l:=0; for j:=0 to 9 do begin p:=head[j]; while p^.next<>nil do begin l:=l+1;p1:=p;p:=p^.next;dispose(p1);a[l]:=p^.data; end; end; end; writeln('Sorted data:'); for i:= 1 to n do write(a[i]:6); end.

+7.4 使用树的排序算法
(1) 二叉树排序*
排序二叉树:每一个参加排列的数据对应二叉树的一个结点,且任一结点如果有左(右)子树,则左(右)子树 各结点的数据必须小(大)于该结点的数据。中序遍历排序二叉树即得排序结果。程序如下: program pxtree; const a:array[1..8] of integer=(10,18,3,8,12,2,7,3); type point=^nod; nod=record w:integer; right,left:point ; end; var root,first:point;k:boolean;i:integer; procedure hyt(d:integer;var p:point); begin if p=nil then begin new(p); with p^ do begin w:=d;right:=nil;left:=nil end; if k then begin root:=p; k:=false end; end else with p^ do if d>=w then hyt(d,right) else hyt(d,left); end; procedure hyt1(p:point); begin with p^ do begin if left<>nil then hyt1(left); write(w:4);

62

NOIP 复习资料(C++版) if right<>nil then hyt1(right); end end; begin first:=nil;k:=true; for i:=1 to 8 do hyt(a[i],first); hyt1(root);writeln; end. 时间复杂度:O(nlogn) 应该清楚地认识到, 因为二叉排序树很容易变得不平衡, 并且它的空间占用比较大, 插入节点也要花费一些时间, 所以,二叉树排序比快速排序慢很多。

(2) 堆排序**
堆:设有数据元素的集合(R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有 Ri<=R2i 和 Ri<=R2i+1(或>=) 堆的性质:堆的根结点上的元素是堆中的最小元素,且堆的每一条路径上的元素都是有序的。 堆排序的思想是: 1)建初始堆(将结点[n/2],[ n/2]-1,...3,2,1 分别调成堆) 2)当未排序完时 输出堆顶元素,删除堆顶元素,将剩余的元素重新建堆。 使用最大值堆。 时间复杂度:O(nlogn)。 如果希望找到数组中第 k 大的元素,可以考虑建堆,时间为 O(n+klogn)。 procedure swap(i,j:longint);//交换 var t:longint; begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; procedure heapdown(i:longint); var l,r:longint; m:longint; begin l:=i shl 1;{l:=i*2;l 是 i 的左儿子} r:=i shl 1+1;{r:=(i*2)+1;r 是 i 的右儿子} if (l<=n) and (a[l]>a[i]) then m:=l else m:=i; if (r<=n) and (a[r]>a[m]) then m:=r; if i<>m then begin swap(i,m); heapdown(m);

63

NOIP 复习资料(C++版) end; end; procedure heapup(i:longint); var f:longint; begin f:=i shr 1;{f:=i div 2;f 是 i 的父亲} if a[f]<a[i] then begin swap(i,f); heapup(f); end; end; procedure buildheap;//建堆(大根堆) var i:longint; begin for i:=n shr 1 downto 1 do heapdown(i); end;

procedure swap(i,j:longint); var t:longint; begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; procedure build(i,m:longint); //建堆(小根堆) begin while i*2<=m do begin i:=i*2; if (i<m) and (a[i+1]>a[i]) then inc(i); if (a[i]>a[i div 2]) then swap(i div 2,i) else break; end;

64

NOIP 复习资料(C++版) end; procedure deal; //主程序 begin for i:=n div 2 downto 1 do build(i,n); for i:=n downto 2 do begin swap(1,i); build(1,i-1); end; end;

7.5 小结
本单元介绍了几种常用的排序算法。其实,我们没有必要掌握全部算法。 1. 利用库函数排序是一个性价比很高的方法。所以,该偷懒就偷懒吧。 2. 在涉及第二关键字排序, 或根据其他比较方式排序时, 使用库函数就方便多了——只需定义一个函数, “a 把 小于 b 吗”解释明白就行了。 3. 快速排序和归并排序都利用了分治思想。尽管时间复杂度都是 O(nlogn),平均情况下,快速排序还是比归 并排序块。 4. 归并排序、二叉树排序占用空间大。 5. 归并排序是稳定的排序,而快速排序不稳定。 6. 插入排序、冒泡排序和选择排序的时间复杂度都是 O(n2)。不过,对于比较有序的序列,这三种排序还是比 较快的,这时快速排序反倒慢了一些。 7. 在数据规模不大,或取值范围不大时,可以使用时间复杂度为 O(n)的排序算法。 8. 二叉树排序基于二叉排序树,很容易出现不平衡的现象。 9. 堆排序有一大优点:建堆很快,查找第 k 大元素也很快。

65

NOIP 复习资料(C++版)

第八单元
int find(int *a, int x, int y, int v) { for (int i=x; i<=y; i++) if (a[i]==v) return true; return false; }

查找

8.1 顺序查找

8.2 二分查找
注意:要查找的线性表必须是有序的。如果无序,就必须先排序然后再二分。

(1) 普通的二分查找(非递归)
int bsearch(int *a, int x, int y, int v) { int mid; while (x<y) { mid=x+(y-x)/2; if (a[m]==v) return m; else if (a[m]>v) y=m; else x=m+1; } return -1; } // 找不到

(2) 二分查找求下界
int lower_bound(int *a, int x, int y, int v) { int mid; while (x<y) { mid=x+(y-x)/2; /* a[m]==v:至少找到一个,但左边可能还有。 a[m]>v:不能在m的后面。 a[m]<v:m和前面都不可以。 */ if (a[m]>=v) y=m; else x=m+1; } return x;

66

NOIP 复习资料(C++版) } // 求上界:把上面的判断语句改成 if (a[m]<=v) x=m+1; else y=m; 上述两个函数都可以在 STL 中找到:#include <algorithm>

8.3 查找第 k 小元素
和快速排序相近。不同的是,在“递归”这一阶段只需对“有第 k 小数据”的一部分进行排序,另一部分就不 用管了。 int part(int *a, int start, int end) { int low=start, high=end; int temp, check=a[start]; do { while (a[high]>=check&&low<=high) high--; if (a[high]<check) temp=a[high], a[high]=a[low], a[low]=temp; while (a[low]<=check&&low<=high) low++; if (a[low]>check) temp=a[high], a[high]=a[low], a[low]=temp; } while (low!=high); a[low]=check; return low; } int find(int *a, int start, int end, int k) { if (start==end) return a[k-1]; int p = part(a, start, end); int q = p – start + 1; // 只对包含第k小元素的部分进行查找和排序。 if (k <= q) return find(a, start, p, k); else return find(a, p+1, end, k-q); } 以上操作可以用堆或优先队列解决。 // 计算p位置的“排名”

67

NOIP 复习资料(C++版)

+8.4 二叉排序树(BST)*
(1) 二叉排序树

(2) 插入一个元素

(3) 删除一个元素

(4) 查找一个元素

(5) 平衡树

+8.5 堆和优先队列**
(1) 堆

(2) 插入一个元素

(3) 插入一组元素

(4) 删除一个元素

(5) 查找一个元素

(6) STL 中的优先队列

+8.6 哈夫曼(Huffman)编码树*
(1) 建立哈夫曼编码树

68

NOIP 复习资料(C++版)

(2) 编码和解码

+8.7 哈希表*
(1) 散列函数

(2) 开散列方法

(3) 闭散列方法

(4) 删除

8.8 小结
本单元介绍了几个常用的查找算法, 对于一般问题来说够用了。 其实还有很多支持查找的数据结构能把查找 的时间复杂度降得,这里就不研究了。 本单元的要点: 1. 顺序查找是比较粗暴的查找方法。很多线性结构的查找就要用顺序查找。 2. 二分查找速度很快,但是只能用于有序的序列。 3. 哈希表可以用于 BFS。这样在一定程度上可以减少时间消耗。 4. 查找第 k 小元素时没有必要把整个序列都处理一遍。递归时只递归有第 k 小元素的那一部分就行了。 5. 二分查找基于线性表,查找很快,但插入数据的速度很慢。二叉排序树是二叉树,它的插入和查找操作 都很快。 不过,二叉排序树很容易变得不平衡。所以要加入一些规则来尽量使它变得平衡。 6. 堆是完全二叉树。它分为最大值堆和最小值堆。 7. 哈夫曼树也是二叉树。它是利用贪心算法构造出来的。

69

NOIP 复习资料(C++版)

第九单元

常用数据结构

9.1 链表
(1) 单链表
1. 定义:下面有一个空链表,表头叫 first。 struct node { int value; node *next; } arr[MAX]; int top=-1; node *first = NULL; 2. 内存分配:最好不要使用 new 运算符或 malloc、calloc 函数。 a) 表头:first = arr + (top=0); 然后初始化 first->value=0; first->mext=NULL; b) 其他元素:node *p = arr+(++top); 3. 插入:把 q 插入到 p 的后面。时间复杂度 O(1)。 if (p==NULL||q==NULL) return; // 先判定是否为空指针。如果不是,继续。 q->next=p->next; p->next=q; 4. 删除:把 p 的下一元素删除。时间复杂度 O(1)。 if (p==NULL||p->next==NULL) return; // 先判定是否为空指针。如果不是,继续。 node *q=p->next; p->next=q->next; // delete(q); // 如果使用动态内存分配,最好将它的空间释放。 5. 查找或遍历:时间复杂度 O(n)。 node *p=first; while (p!=NULL) { // 处理value // cout<<p->value<<'\t'; p=p->next; }

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

70

NOIP 复习资料(C++版)

(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; 2. 内存分配:最好不要使用 new 运算符或 malloc、calloc 函数。 a) 表头:first = arr + (top=0); 然后初始化 first->value=0; first->mext=first->pre=NULL; b) 其他元素:node *p = arr+(++top); 3. 插入:把 q 插入到 p 的后面。时间复杂度 O(1)。 if (p==NULL||q==NULL) return; // 先判定是否为空指针。如果不是,继续。 q->prev=p; q->next=p->next; q->next->prev=q; p->next=q; 4. 删除:把 p 的下一元素删除。时间复杂度 O(1)。 if (p==NULL||p->next==NULL) return; // 先判定是否为空指针。如果不是,继续。 node *q=p->next; p->next=q->next; q->next->prev=p; // delete(q); 5. 查找或遍历:两个方向都可以。 // 如果使用动态内存分配,最好将它的空间释放。

9.2 栈(LIFO 表)
(1) 栈
1. 2. 3. 4. 5. 6. 7. 8. 操作规则:先进后出,先出后进。 int stack[N], top=0; 入栈:stack[top++] = a; 出栈:a = stack[--top]; STL 中的栈:头文件为<stack>。 定义一个堆栈:stack<int> s; 入栈:s.push(a); 出栈:a=s.top(); s.pop(); // top 表示栈顶位置。 // top<0 时栈空。

71

NOIP 复习资料(C++版) 9. 判断是否为空:s.empty(),如果为空栈,返回 true。

(2) DFS 和栈
stack <int> state; void DFS(int v, …) { state.push(v); while (!state.empty()) { int s = state.top(); state.pop(); // 处理节点 if (s达到某种条件) { // 输出,或做些什么 … return; } // 寻找下一状态,如 for (i=0;i<n;i++) { state.push(… /*i对应的状态*/); } } // 无解 cout<<"Failed"; } 递归其实也用到了堆栈。每调用一次函数,都相当于入栈(当然这步操作“隐藏在幕后”。函数调用完成后,相 ) 当于出栈。 一般情况下,调用栈的空间大小为 16MB。也就是说,如果递归次数太多,很容易因为栈溢出导致程序崩溃。这 种情况下,可以将递归用栈显式实现,也可以改成迭代等方法。 // 存储状态

// 获取状态

9.3 队列、循环队列(FIFO 表)
(1) 队列
1. 2. 3. 4. 5. 操作规则:先进先出,后进后出。 int queue[N], front=0, rear=0; 入队:queue[rear++] = a; 出队:a = queue[front++]; 队空的条件:front>rear // front 表示开头位置, rear 表示结尾位置。

6. STL 中的队列:头文件为<queue> 7. 定义一个队列:queue<int> q;

72

NOIP 复习资料(C++版) 8. 入队:q.push(a); 9. 出队:a=q.front(); q.pop(); 10. 判断是否为空:q.empty(),如果为空队列,返回 true。

(2) 循环队列
1. 循环队列——把链状的队列变成了一个环状队列。与上面的链状队列相比,可以节省很大空间。 2. 定义:int queue[N], front=0, rear=0; // front 表示开头位置,rear 表示结尾位置。 3. 入队: queue[rear] = a; rear=(rear+1)%N; 4. 出队: a = queue[front]; front = (front+1)%N; 5. 队满的条件:rear == front-1 6. 队空的条件:(front+N)%N > (rear) // 注意,循环队列是环状的

(3) BFS 和队列
参见 24 页“2.7 模板” 把 BFS 中的队列直接改成堆栈,BFS 就变成了 DFS。使用堆栈的 DFS 可以防止递归层数太多而导致的栈溢出。

9.4 二叉树
(1) 一般二叉树的实现
struct node { int value; node *left, *right; } arr[MAX]; 内存分配的方法见 70 页“9.1 链表” 。这里不再赘述。

+(2) 用数组存储完全二叉树

(3) 二叉树的遍历
都是递归完成的事情。 ① 前序遍历 void preorder(node *p) { if (p==NULL) return; // 处理根结点 // cout<<p->value<<'\t'; ……

73

NOIP 复习资料(C++版) preorder(p->left); preorder(p->right); } ② 中序遍历 void inorder(node *p) { if (p==NULL) return; inorder(p->left); // 处理根结点 // cout<<p->value<<'\t'; …… inorder(p->right); } ③ 后序遍历 void postorder(node *p) { if (p==NULL) return; postorder(p->left); postorder(p->right); // 处理根结点 // cout<<p->value<<'\t'; …… }

+(4) 已知前(后)序遍历和中序遍历,求后(前)序遍历
前序遍历的第一个元素是根,后序遍历的最后一个元素也是根。所以处理时需要到中序遍历中找根,然后递归求 出树。 ① 中+后→前 var s1,s2:string; proceduretry(s3,s4:string); varp,i:longint; begin if length(s3)=0 thenexit; if length(s3)=1 thenbeginwrite(s3);exit;end; p:=length(s4); write(s4[p]); i:=pos(s4[p],s3); try(copy(s3,1,i-1),copy(s4,1,i-1)); try(copy(s3,i+1,p-i),copy(s4,i,p-i)); end;

74

NOIP 复习资料(C++版) begin readln(s1); readln(s2); try(s1,s2); end.

+(5) 多叉树变二叉树
左儿子,右兄弟 Ft[i]表示 i 是否有孩子 A[i].right\a[i].left 表示 i 结点的左儿子、右儿子 Num[i]表示 i 结点的最后一个儿子的结点号 readln(n,m); fori:=1tondo begin readln(x,y); //x 表示 x 是 i 的父亲,y 为数据 if ft[x]=falsethen begin a[x].left:=i; num[x]:=i; ft[x]:=true; end else begin a[num[x]].right:=i; num[x]:=i; end; a[i].data:=y; end;

+(6) 求树的直径*
从任意一点出发,搜索到的最远点,则这个最远点必定在数的直径上,再从最远 点搜索一次它的最远点既为树的直径 type txt=record data:char; f,l,r:longint; end; vara:array[0..1000]oftxt; t:array[-1..1000]ofboolean; i,j,n,max,node,m:longint; proceduredfs(x,l:longint); begin if l>maxthenbeginmax:=l;node:=x;end; t[x]:=false;

75

NOIP 复习资料(C++版) if t[a[x].f]thendfs(a[x].f,l+1); if t[a[x].l]thendfs(a[x].l,l+1); if t[a[x].r]thendfs(a[x].r,l+1); end; begin readln(m); read(a[1].data); a[1].f:=-1; a[1].r:=3; a[1].l:=2; fori:=2tomdo begin read(a[i].data); a[i].f:=idiv2; ifi*2<=mthena[i].l:=i*2; ifi*2+1<=mthena[i].r:=i*2+1; end; max:=0; fillchar(t,sizeof(t),false); fori:=1tomdo t[i]:=true; dfs(1,0); max:=0; fillchar(t,sizeof(t),false); fori:=1tomdo t[i]:=true; dfs(node,0); writeln(max); end.

9.5 并查集
【问题描述】有 n 个元素和 c 个询问。每次询问可以进行以下两种操作中的一种: ① 把两个元素合并到一个集合中; ② 查询某两个元素是否在同一集合。 并查集:可以设置一个集合(其实是森林) ,从 0 到 n-1 分别表示那个结点的父亲节点。这样就可以用树形结构 把在同一集合的点连接到一起了。

(1) 并查集的实现
struct node { int parent; int count; int value; // 表示父亲节点。当编号i==parent时为根节点。 // 当且仅当为根节点时有意义:表示自己及子树元素的个数 // 节点的值

76

NOIP 复习资料(C++版) } set[N];

(2) 将两个元素合并到同一集合
void union(int x, int y) { x=find(x); y=find(y); // 寻找各自的根节点

if (x!=y) // 如果不在同一个集合,合并 { set[y].parent = x; set[x].count += set[y].count; } }

(3) 带路径压缩的查找(递归)
int find (int x) { return parent[x]==x ? x : parent[x] = find(x); }

(4) 带路径压缩的查找(非递归)
int find (int x) { int y=x; int temp; while (set[y].parent != y) y = set[y].parent; while (x!=y) { temp = set[x].parent; set[x].parent = y; x = temp; } } 提示: 1. 并查集的查找操作很快,时间复杂度为 O(n)。 2. 判断 x 和 y 是否在同一集合:if (find(x)==find(y)) …… 3. 在所有的合并操作结束后,最好再进行一次路径压缩。 // 寻找父亲节点

// 路径压缩,即把途中经过的节点的父亲全部改成y。

9.6 图
一些全局变量和常数: int n, m; // n 代表结点个数,m 代表边的个数。一般 N?n,M?m

77

NOIP 复习资料(C++版) int G[N][N]; // 用邻接矩阵存储的图 int u[M], v[M], w[M]; // 用边目录存储的图(u 是起点,v 是终点,w 是权) int first[N], next[M]; // 用邻接表存储的图(不使用指针) vector<int> g[N]; // 用邻接表存储的图(使用向量) edge *first[N]; // 用邻接表存储的图(使用指针,edge 的定义在下面) #define INF 100000000 // G[i][j]=INF 表示这条边不存在。不要设置得过大,以防溢出 如果没有特殊说明,邻接表使用 edge *first[N]。

(1) 图的存储方法
1. 邻接矩阵 开一个二维数组 G。G[i][j]表示边(i,j)的权。如果边(i,j)不存在,就令 G[i][j]=INF。 INF:#define INF 9999999 // 取值时不要过大,以防在图论算法中发生溢出! 邻接矩阵最大的缺点就是内存空间占用太大,内存浪费严重。 2. 边目录 设置三个数组 u[M]、v[M]、w[M],分别表示起点、终点和权。 一般情况下,从文件中读取的图都是用边目录来表示的。 3. 邻接表 用一个列表列出所有与现结点之间有边存在的结点名称。 ① 使用链表 struct edge { int u,v,w; edge * next; } mem[M]; // mem相当于动态内存分配。 edge *first[N]; // first[i]代表以i为起点的边。 …… memset(first, 0, sizeof(first)); for (int e=0; e<m; e++) { cin>>mem[e].u>>mem[e].v>>mem[e].w; mem[e]->next=first[u]; first[u]=&mem[e]; } 如果想检查从 a 出发的所有边,那么可以 for (edge *e=first[a]; e!=NULL; e=e->next) { // e->u是起点,e->v是终点,e->w是权 } ② 不使用指针 注意,在这个“邻接表”里放置的元素是边的序号,不是点的序号。但是,只需通过 u 就可以获得点的序号。 int first[N]; // first[u]表示从u出发的第一条边的序号 int u[M],v[M],w[M], next[M]; // next[e]表示编号为e的下一条边的序号 // 插入一条边

78

NOIP 复习资料(C++版) ...... memset(first, -1, sizeof(first)); for (int e=0; e<m; e++) { cin>>u[e]>>v[e]>>w[e]; next[e]=first[u[e]]; first[u[e]]=e; } 如果想检查从 a 出发的所有边,那么可以 for (int e=first[a]; e!=-1; e=next[e]) { // u[e]是起点,v[e]是终点,w[e]是权 } ③ 使用向量(vector) 头文件:#include <vector> 只需把②中的代码换成以下代码: vector<int> g[N]; int u[M],v[M],w[M]; ...... for (int e=0; e<m; e++) { cin>>u[e]>>v[e]>>w[e]; g[u].push_back(e); } 如果想检查从 a 出发的所有边,那么可以 for (int i=0; i<g[a].size(); i++) { int &e=g[a][i]; // u[e]是起点,v[e]是终点,w[e]是权 } 4. 图的表示法的选择 功效表 消耗空间 连接判断的消耗时间 检查某结点所有相邻结点的消耗时间 添加边的消耗时间 删除边的消耗时间 边集 2M M M 1 M 邻接矩阵 N2 1 N 1 2 邻接表 2M N N 1 2N // 插入一条边

// g[u][i]表示从u出发的第i条边的序号

5. 前向星 首先把所有边排序。以起点 u 为第一关键字,终点 v 为第二关键字(全部升序)排列。 接下来开一个数组 int first[N],first[i]表示 u 为 i 的最小位置。 前向星不太常用。在前向星中,添加边和删除边都是很困难的事情。一般情况下,使用邻接表更好一些。

79

NOIP 复习资料(C++版)

(2) 图的遍历
1. 深度优先遍历(递归) [邻接矩阵] 这是基于邻接矩阵的遍历。如果需要,可以改成基于邻接表的遍历。 bool visited[N]; void DFS(int start) { visited[start]=true; // 处理点v cout<<start<<' '; for (int i=0; i<n; i++) if ((!visited[i]) && (G[v][i]!=INF)) DFS(i); } 2. 广度优先遍历 [邻接矩阵] 这是基于邻接矩阵的遍历。如果需要,可以改成基于邻接表的遍历。 queue<int> q; bool visited[N]; void BFS(int start) { q.push(start); do { int v=q.front(); q.pop(); visited[v]=true; // 处理点v cout<<v<<' '; for (int i=0;i<n;i++) if ((!visited[i]) && (G[v][i]!=INF)) q.push(i); } while (!q.empty()); } 直接把代码里的队列改成堆栈,广度优先遍历就变成了深度优先遍历。不过,答案略有些不同。 3. 一个细节 为了保证非连通图中所有的点都被访问,需要这样做: for (int i=0;i<n;i++) if (!visited[i]) DFS(i); // 或BFS(i);

80

NOIP 复习资料(C++版)

+(3) 图的连通性

Microsoft PowerPoint 演示文稿

1. Kosaraju 算法

2. 种子染色法(Flood Fill) Flood Fill 可以用深度优先搜索,广度优先搜索或广度优先扫描来实现。他的实现方式是寻找到一个未被标 记的结点对它标记后扩展,将所有由它扩展出的结点标上与它相同的标号,然后再找另一个未被标号的 结点重 复该过程。这样,标号相同的结点就属于同一个连通子图。 深搜:取一个结点,对其标记,然后标记它所有的邻结点。对它的每一个邻结点这么一直递归下去完成搜索。 广搜:与深搜不同的是,广搜把结点加入队列中。 广度扫描(不常见) :每个结点有两个值,一个用来记录它属于哪个连通子图(c) ,一个用来标记是否已经访问 (v) 。算法对每一个未访问而在某个连通子图当中的结点扫描,将其标记访问,然后把它的邻结点的(c)值改 为当前结点的(c)值。 深搜最容易写,但它需要一个栈。搜索显式图没问题,而对于隐式图,栈可能就存不下了。 广搜稍微好一点,不过也存在问题。搜索大的图它的队列有可能存不下。深搜和广搜时间复杂度均为 O(N+M)。 其中,N 为结点数,M 为边数。 广度扫描需要的额外空间很少,或者可以说根本不要额外空间,但是它很慢。时间复杂度是 O(N^2+M)。 (实际应用中,我们一般写的是 DFS,因为快。空间不是问题,DFS 可改用非递归的栈操作完成。但为了尊重 原文,我们还是译出了广度扫描的全过程。——译者) 广度扫描的伪代码 代码中用了一个小技巧, 因此无须额外空间。 结点若未访问, 将其归入连通子图 (-2) 就是代码里的 component , -2。这样无须额外空间来记录结点是否访问,请读者用心体会。 # component(i) denotes the # component that node i is in 1 function flood_fill(new_component) 2 do 3 num_visited = 0 4 for all nodes i 5 if component(i) = -2 6 num_visited = num_visited + 1 7 component(i) = new_component 8 for all neighbors j of node i 9 if component(j) = nil 10 component(j) = -2 11 until num_visited = 0 12 function find_components 13 num_components = 0 14 for all nodes i 15 component(node i) = nil 16 for all nodes i 17 if component(node i) is nil 18 num_components =

81

NOIP 复习资料(C++版) num_components + 1 19 component(i) = -2 20 flood_fill(component num_components) 算法的时间复杂度是 O(N 2),每个结点访问一次,每条边经过两次。

+(4) 欧拉回路( “一笔画” )
存在欧拉回路的充要条件: 每个点的度数都是偶数, 且图连通

/*==================================================*\ | 欧拉路径 O(E) | INIT: adj[][] 置为图的邻接表; cnt[a] 为 a 点的邻接点个数; | CALL: elpath(0); 注意: 不要有自向边 \*==================================================*/ int adj[V][V], idx[V][V], cnt[V], stk[V], top; int path( int v){ for (int w ; cnt[v] > 0; v = w) { stk[ top++ ] = v; w = adj[v][ --cnt[v] ];

82

NOIP 复习资料(C++版) adj[w][ idx[w][v] ] = adj[w][ --cnt[w] ]; // 处理的是无向图—-边是双向的,删除 v->w 后,还要处理删除 w->v } return v; } void elpath (int b, int n){ // begin from b int i, j; for (i = 0; i < n; ++i) // vertex: 0 ~ n-1 for (j = 0; j < cnt[i]; ++j) idx[i][ adj[i][j] ] = j; printf("%d", b); for (top = 0; path(b) == b && top != 0; ) { b = stk[ --top ]; printf("-%d", b); } printf("\n"); }

+(5) 图论建模:食物网问题*
一点都不像 NOIP 范围的问题。 食物网有以下几个特点: 1. 食物网是有向无环图。 2. 所有入度为 0 的点都是植物。 3. 所有出度为 0 的点都是动物(不是分解者) ,并且所在食物链上的营养级最高。 4. 食物网中食物链的长度一般不超过 5(因为生态系统中能量传递的特点是单向流动、逐级递减) 。不过在这 里,食物链可以达到任意长度——我们在研究图论,而不是生物学。 有关食物网的问题: 1. 统计食物网中食物链条数。 BFS? or DP? 2. 某生物占的营养级数。 DFS? 3. 求能量消耗最少的食物链(无权的最短路,即最短链) 、能量消耗最多的食物链(无权的最长路,即最长链) 。 BFS? 4. 求生物的种间关系(竞争、捕食,或者二者都有) 。 DFS?

+(6) 图论建模:篝火晚会(NOIP2005,3)
【问题描述】 佳佳刚进高中,在军训的时候,由于佳佳吃苦耐劳,很快得到了教官的赏识,成为了“小教官” 。在军训结束的 那天晚上, 佳佳被命令组织同学们进行篝火晚会。 一共有 n 个同学, 编号从 1 到 n。 一开始, 同学们按照 1, ??, 2, n 的顺序坐成一圈, 而实际上每个人都有两个最希望相邻的同学。 如何下命令调整同学的次序, 形成新的一个圈, 使之符合同学们的意愿,成为摆在佳佳面前的一大难题。 佳佳可向同学们下达命令,每一个命令的形式如下: (b1, b2,... bm-1, bm) 这里 m 的值是由佳佳决定的,每次命令 m 的值都可以不同。这个命令的作用是移动编号是(b1, b2,... bm-1,

83

NOIP 复习资料(C++版) bm)的这 m 个同学的位置。要求 b1 换到 b2 的位置上,b2 换到 b3 的位置上,??, 要求 bm 换到 b1 的位置上。 执行每个命令都需要一些代价。我们假定如果一个命令要移动 m 个人的位置,那么这个命令的代价就是 m。我们 需要佳佳用最少的总代价实现同学们的意愿,你能帮助佳佳吗? 【输入文件】 输入文件 fire.in 的第一行是一个整数 n(3 <= n <= 50000) ,表示一共有 n 个同学。其后 n 行每行包括 两个不同的正整数,以一个空格隔开,分别表示编号是 1 的同学最希望相邻的两个同学的编号,编号是 2 的同 学最希望相邻的两个同学的编号,??,编号是 n 的同学最希望相邻的两个同学的编号。 【输出文件】 输出文件 fire.out 包括一行,这一行只包含一个整数,为最小的总代价。如果无论怎么调整都不能符合每个 同学的愿望,则输出-1。 【样例输入】 4 3 4 4 3 1 2 1 2 【样例输出】 2 【数据规模】 对于 30%的数据,n <= 1000; 对于全部的数据,n <= 50000。

Microsoft Office Word 文档

+9.7 线段树**
如果没兴趣——你就当作没看见。 线段树是这样的一种二叉树,每个节点都存储了线段的起点和终点。叶子结点有:起点+1=终点。 使用线段树可以完成一些统计问题。

84

NOIP 复习资料(C++版)

(1) 线段的实现
Type TreeNode=Record a,b,Left,Right,Cover:Longint {cover 表示线段的覆盖次数} End

(2) 建立一棵线段树
Procedure MakeTree(a,b) Var Now:Longint Begin tot ← tot + 1 Now ← tot Tree[Now].a ← a Tree[Now].b ← b If a +1 < b then Tree[Now].Left ← tot + 1 MakeTree(a, ? ? 2 / ) ( b a+ ) Tree[Now].Right ← tot + 1 MakeTree( ? ? 2 / ) ( b a+ , b) End

85

NOIP 复习资料(C++版)

(3) 插入一条线段
Procedure Insert(Num) Begin If (c<Tree[Num].a)and(Tree[Num].b<d) then Tree[Num].Cover ← Tree[Num].Cover + 1 Else If c< ? ? 2 / ) ]. [ ]. [ ( b Num Tree a Num Tree + then Insert(Tree[Num].Left) If d> ? ? 2 / ) ]. [ ]. [ ( b Num Tree a Num Tree + Insert(Tree[Num].Right) End then

86

NOIP 复习资料(C++版)

(4) 删除一条线段
删除一条线段[c,d]

Procedure Delete(Num) Begin If (c<Tree[Num].a)and(Tree[Num].b<d) then Tree[Num].Cover ← Tree[Num].Cover - 1 Else If c< ? ? 2 / ) ]. [ ]. [ ( b Num Tree a Num Tree + then Delete(Tree[Num].Left) If d> ? ? 2 / ) ]. [ ]. [ ( b Num Tree a Num Tree + Delete(Tree[Num].Right) End then

87

NOIP 复习资料(C++版)

(5) 统计

88

NOIP 复习资料(C++版)

对边界范围小,操作数多的题目,我们选择线段树

9.8 小结
数据结构是计算机科学的重要分支。选择合适的数据结构,可以简化问题,减少时间的浪费。 本单元的要点有: 1. 线性表和链表是最基础的数据结构。线性表的插入和删除速度很慢(因为涉及大量元素的移动) ,而链 表可以解决这个问题。 2. 栈和队列是重要的数据结构。栈和队列的区别在于取出数据的顺序。 3. 深度优先搜索和广度优先搜索可以互相转化——操作也很简单,把 stack 和 queue 换一下就可以了。 4. 树的问题,可以用递归思想解决。 5. 树其实是一种特殊的图,所以有些树的问题也能用图论算法解决。 6. 堆、线段树、平衡树等等其实都是二叉树。 7. 使用堆可以优化动态规划。当然,在 NOIP 中用不到。 8. 并查集的本质是森林。为了加快速度,一般在查找时顺便进行路径压缩,把子孙全部变成儿子。 9. 图的存储方法有四种。根据不同问题应该选择不同的存储方法。 10. 图论的思想其实比算法更重要。

89

NOIP 复习资料(C++版)

90

NOIP 复习资料(C++版)

第十单元

高精度算法

10.1 定义
编程时这样做——假设 hp 是高精度类型 先用宏定义:#define hp long long,然后集中精力编写算法代码。 最后直接删除这条宏定义, 把真正的高精度算法写出来。 这样做的好处是无需再修改算法代码, 减小了维护代价。 #define MAX 100 struct hp { int num[MAX]; hp & operator = (const char*); hp & operator = (int); hp(); hp(long long); // 以下运算符可以根据实际需要来选择。 bool operator > (const hp &) const; bool operator < (const hp &) const; bool operator <= (const hp &) const; bool operator >= (const hp &) const; bool operator != (const hp &) const; bool operator == (const hp &) const; hp operator >? (const hp &) const; hp operator <? (const hp &) const; hp hp hp hp hp hp hp hp hp hp }; 实现运算符的代码最好写到结构体的外面。 “<<”和“>>”由于不是 hp 的成员,所以必须写到结构体的外面。 operator operator operator operator operator & & & & & + * / % (const (const (const (const (const += -= *= /= %= hp hp hp hp hp &) &) &) &) &) hp hp hp hp hp const; const; const; const; const; &); &); &); &); &);

operator operator operator operator operator

(const (const (const (const (const

10.2 赋值和初始化
// num[0]用来保存数字位数。另外,利用10000进制可以节省空间和时间。 hp & hp::operator = (const char* c) {

91

NOIP 复习资料(C++版) memset(&num,0,sizeof(num)); int n=strlen(c),j=1,k=1; for (int i=1;i<=n;i++) { if (k==10000) j++,k=1; num[j]+=k*(c[n-i]-'0'); k*=10; } num[0]=j; return *this; } hp & hp::operator = (int a) { char s[MAX]; sprintf(s,"%d",a); return *this=s; } hp::hp() {memset(num,0,sizeof(num)); num[0]=1;} hp::hp(long long n) {*this = n;} // 目的:声明hp时无需显式初始化。 // 目的:支持“hp a=1;”之类的代码。 // 10000进制,4个数字才算1位。

10.3 比较运算符
// 如果位数不等,大小是可以明显看出来的。如果位数相等,就需要逐位比较。 bool hp::operator > (const hp &b) const { if (num[0]!=b.num[0]) return num[0]>b.num[0]; for (int i=num[0];i>=1;i--) if (num[i]!=b.num[i]) return (num[i]>b.num[i]); return false; } bool hp::operator < (const hp &b) const {return b>*this;} bool hp::operator <= (const hp &b) const {return !(*this>b);} bool hp::operator >= (const hp &b) const {return !(b>*this);} bool hp::operator != (const hp &b) const {return (b>*this)||(*this>b);} bool hp::operator == (const hp &b) const {return !(b>*this)&&!(*this>b);} // 下面两个运算符的含义是:取最大值和取最小值。虽然C++资料不提这两种运算符,但它们确实是合法的。 hp hp::operator >? (const hp &b) const {return (*this>b)?(*this):b;} hp hp::operator <? (const hp &b) const {return (*this<b)?(*this):b;}

10.4 四则运算
(1) 高精度加、减法
// 只需模拟小学竖式运算。注意:最高位的位置和位数要匹配。 hp hp::operator + (const hp &b) const

92

NOIP 复习资料(C++版) { hp c; c.num[0] = num[0] >? b.num[0]; for (int i=1;i<=c.num[0];i++) { c.num[i]+=num[i]+b.num[i]; if (c.num[i]>=10000) { c.num[i]-=10000; c.num[i+1]++; } } if (c.num[c.num[0]+1]>0) c.num[0]++; return c; } hp hp::operator - (const hp &b) const { hp c; c.num[0] = num[0]; for (int i=1;i<=c.num[0];i++) { c.num[i]+=num[i]-b.num[i]; if (c.num[i]<0) { c.num[i]+=10000; c.num[i+1]--; } // 退位 // 9999+1,计算完成后多了一位 // 进位

} while (c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--; return c; }

// 100000000-99999999

hp & hp::operator += (const hp &b) {return *this=*this+b;} hp & hp::operator -= (const hp &b) {return *this=*this-b;}

(2) 高精度乘法
hp hp::operator * (const hp &b) const { hp c; c.num[0] = num[0]+b.num[0]+1; for (int i=1;i<=num[0];i++) {

93

NOIP 复习资料(C++版) for (int j=1;j<=b.num[0];j++) { c.num[i+j-1]+=num[i]*b.num[j]; c.num[i+j]+=c.num[i+j-1]/10000; c.num[i+j-1]%=10000; } } while (c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--; return c; } hp & hp::operator *= (const hp &b) {return *this=*this*b;} // 99999999*0 // 和小学竖式的算法一模一样 // 进位

(3) 高精度除法
高精度除法的使用频率不太高。 另外,下面的设计有点不合理——除法和取模同时进行时,要白白地算一遍除法。 hp hp::operator / (const hp &b) const { hp c, d; c.num[0] = num[0]+b.num[0]+1; for (int i=num[0];i>=1;i--) { // 以下三行的含义是:d=d*10000+num[i]; memmove(d.num+2, d.num+1, sizeof(d.num)-sizeof(int)); d.num[0]++; d.num[1]=num[i]; // 以下循环的含义是:c.num[i]=d/b; d%=b; while (d >= b) { d-=b; c.num[i]++; } } while (c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--; return c; } hp hp::operator % (const hp &b) const { hp c, d; c.num[0] = num[0]+b.num[0]+1; for (int i=num[0];i>=1;i--) { // 以下三行的含义是:d=d*10000+num[i]; memmove(d.num+2, d.num+1, sizeof(d.num)-sizeof(int)); d.num[0]++; // 99999999/99999999

94

NOIP 复习资料(C++版) d.num[1]=num[i]; // 以下循环的含义是:c.num[i]=d/b; d%=b; while (d >= b) { d-=b; c.num[i]++; } } while (c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--; return d; } hp & hp::operator /= (const hp &b) {return *this=*this/b;} hp & hp::operator %= (const hp &b) {return *this=*this%b;}

10.5 输入/输出
有了这两段代码,就可以直接用 cout 和 cin 输出、输入高精度数了。 ostream & operator << (ostream & o, hp &n) { o<<n.num[n.num[0]]; for (int i=n.num[0]-1;i>=1;i--) { o.width(4); o.fill('0'); o<<n.num[i]; } return o; } istream & operator >> (istream & in, hp &n) { char s[MAX]; in>>s; n=s; return in; }

10.6 小结
因为有一天做了几道需要高精度的题,我决定编一个高精度的代码模板。NOIP 不允许带代码模板,所以很 有必要把这里的内容背下来。 本单元要点如下: 1. 我们应该背一些模板和现成代码。如果竞赛时遇到了这些内容,写起来就容易了。 2. “迭代式开发” 。先把算法问题解决,再写高精度计算的代码。 3. 重载运算符不一定快,但是对算法部分的代码影响最小。

95

NOIP 复习资料(C++版) 4. 把更高级的模块编出来之前,应该让现有代码与它兼容。这个工作可以用宏定义和条件编译完成。下面 是不使用重载运算符的高精度算法: //#define HP // 高精度写完后解除注释 #ifdef HP struct hp { …… ; void add(hp &a, hp b, hp c) { …… } …… #else #define hp long long; #define add(a,b,c) a=b+c; …… #endif …… hp f[100]; …… add(f[i], f[i-1], a[i]); // hp不使用重载运算符

96

NOIP 复习资料(C++版)

第十一单元

常用数学知识

+11.1 计数原理
3.1 加法原理与乘法原理 1.加法原理: 做一件事情,完成它可以有 n 类办法,在第一类办法中有 m1 种不同的方法,在第二类办法中有 m2 种不同的方 法,??,在第 n 类办法中有 mn 种不同的方法。那么完成这件事共有 N= m1+m2+...+mn 种不同的方法。 2.乘法原理: 做一件事情,完成它需要分成 n 个步骤,做第一步有 m1 种不同的方法,做第二步有 m2 种不同的方法,??, 做第 n 步有 种 mn 不同的方法,那么完成这件事有 N=m1*m2*...*mn 种不同的方法。 3.两个原理的区别:一个与分类有关,一个与分步有关;加法原理是“分类完成” ,乘法原理是“分步完成” 。 练习: 1.由数字 1,2,3,4,5 可以组成多少个三位数(各位上的数字允许重复)? 2.由数字 0、1,2,3,4,5 可以组成多少个三位数(各位上的数字允许重复)? 3.由数字 0,1,2,3,4,5 可以组成多少个十位数字大于个位数字的两位数? 例 4. 一个三位密码锁,各位上数字由 0,1,2,3,4,5,6,7,8,9 十个数字组成,可以 设置多少种三位数的密码(各位上的数字允许重复)?首位数字不为 0 的密码数是多少 种?首位数字是 0 的密码数又是多少种? 5.如图,要给地图 A、B、C、D 四个区域分别涂上 3 种不同颜色中的某一种,允许同 一种颜色使用多次,但相邻区域必须涂不同的颜色,不同的涂色方案有多少种? 6.某班有 22 名女生,23 名男生. ① 选一位学生代表班级去领奖,有几种不同选法? ② 选出男学生与女学生各一名去参加智力竞赛,有几种不同的选法? 7.105 有多少个约数?并将这些约数写出来. 8.从 5 幅不同的国画、2 幅不同的油画、7 幅不同的水彩画中选不同画种的两幅画布置房间,有几种选法? 9.若 x、y 可以取 1,2,3,4,5 中的任一个,则点(x,y)的不同个数有多少? 10.一个口袋内装有 5 个小球另一个口袋内装有 4 个小球,所有这些小球的颜色各不相同① 从两个口袋内 任取一个小球,有 种不同的取法; 11.从两个口袋内各取一个小球,有 种不同的取法. 12.乘积(a1+a2+a3)(b1+b2+b3+b4)(c1+c2+c3+c4+c5)展开共有 个项。 13.有四位考生安排在 5 个考场参加考试.有 种不同的安排方法。 (答案:125;180;15;1000,900,100;6;45,506;8;59;25;9;20;60;625) 3. 2 排列与组合的概念与计算公式 1.排列及计算公式 从 n 个不同元素中,任取 m(m?n)个元素按照一定的顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一 个排列;从 n 个不同元素中取出 m(m?n)个元素的所有排列的个数,叫做从 n 个不同元素中取出 m 个元素的排 列数,用符号 p(n,m)表示. p(n,m)=n(n-1)(n-2)??(n-m+1)= n!/(n-m)!(规定 0!=1). 2.组合及计算公式 从 n 个不同元素中,任取 m(m?n)个元素并成一组,叫做从 n 个不同元素中取出 m 个元素的一个组合;从 n 个 不同元素中取出 m(m?n)个元素的所有组合的个数,叫做从 n 个不同元素中取出 m 个元素的组合数.用符号 c(n,m) 表示. c(n,m)=p(n,m)/m!=n!/((n-m)!*m!);c(n,m)=c(n,n-m); 3.其他排列与组合公式 从 n 个元素中取出 r 个元素的循环排列数=p(n,r)/r=n!/r(n-r)!. n 个元素被分成 k 类,每类的个数分别是 n1,n2,...nk 这 n 个元素的全排列数为

97

NOIP 复习资料(C++版) n!/(n1!*n2!*...*nk!). k 类元素,每类的个数无限,从中取出 m 个元素的组合数为 c(m+k-1,m). 练习: 1. (1)用 0,1,2,3,4 组合多少无重复数字的四位数?(96) (2)这四位数中能被 4 整除的数有多少个?(30) (3)这四位数中能被 3 整除的数有多少个?(36) 2.用 0,1,2,3,4 五个数字组成无重复数字的五位数从小到大依次排列. (1) 第 49 个数是多少?(30124) (2) 23140 是第几个数?(40) 3.求下列不同的排法种数: (1) 6 男2女排成一排,2 女相邻;(p(7,7)*p(2,2)) (2) 6 男2女排成一排,2 女不能相邻;(p(6,6)*p(7,2)) (3) 5 男 3 女排成一排,3 女都不能相邻;(p(5.5)*p(6,3)) (4) 4 男 4 女排成一排,同性者相邻;(p(4,4)*p(4,4)*p(2,2)) (5) 4 男 4 女排成一排,同性者不能相邻。(p(4,4)*p(4,4)*p(2,2)) 4.有四位医生、六位护士、五所学校。 (1) 若要选派三位医生到五所学校之中的三所学校举办健康教育讲座,每所学校去一位医生有多少种不同的选 派方法?(c(5,3)*p(4,3)) (2) 在医生或护士中任选五人,派到五所学校进行健康情况调查,每校去且仅去一人,有多少种不同的选派方 法?(p(10,5)) (3) 组成三个体检小组,每组一名医生、两名护士,到五所学校中的三所学校为老师体检,有多少种不同的选 派方法?(c(5,3)*p(4,3)*c(6,2)*c(4,2)*c(2,2)) 5.平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点都不在同一条直线上。问 用这些点为顶点,能组成多少个不同四边形?(2250) 6.平面上有三条平行直线,每条直线上分别有 7,5,6 个点,且不同直线上三个点都不在同一条直线上。问 用这些点为顶点,能组成多少个不同三角形?(751) 7.将 N 个红球和 M 个黄球排成一行。例如:N=2,M=2 可得到以下 6 种排法: 红红黄黄 红黄红黄 红黄黄红 黄红红黄 黄红黄红 黄黄红红 问题:当 N=4,M=3 时有多少种不同排法?(不用列出每种排法)(35) 8.用 20 个不同颜色的念珠穿成一条项链,能做多少个不同的项链.(20!/20) 9.在单词 MISSISSIPPI 中字母的排列数是(11!/(1!*4!*4!*2!) 10.求取自 1,2,...k 的长为 r 的非减序列的个数为(c(r+k-1,r))

(3) 二项式定理
0 0 - r - n (a+b)n=Cn anb0+Cn an 1b1+?+C an rbr+?+C a0bn n n r - 其中an rbr的二项式系数为C 。 n

11.2 组合数的计算
(1) 使用加法递推——O(n2)

Cm=Cn-1 +Cn-1 n
98

m-1

m

0 n (边界条件Cn =C =1) n // 根据实际需要开数组

int C[1001][1001];

NOIP 复习资料(C++版) …… memset(C,0,sizeof(C)); for (int i=0;i<=n;i++) { C[i][0]=1; for (int j=0;j<=i;j++) C[i][j]=C[i-1][j-1] + C[i-1][j]; }

(2) 使用乘法递推——O(n)

Cm=n-m+1 Cm-1 n m n

0 (边界条件C =1,必须先乘后除,否则会发生“除不开”的 BUG) n

m n n-m 一个小优化:C =C (m>2时用) n n int C[1001]; …… C[0]=1; if (m>n-m) m=n-m; for (int i=1;i<=m;i++) // C[m]其实表示C[n][m];

C[i] = (n-i+1) * C[i-1] / i;

// 如果怕溢出,可以把中间结果转化成long long。

11.3 排列和组合的产生
(1) DFS 产生全排列和组合
见 13 页“2.3 DFS 产生全排列和组合(无重集元素) ”

(2) 由上一排列产生下一排列
① 从右往左寻找第一个小于右边的数,位置为 j。 ② 在 j 位置的右边寻找大于 aj 的最小数字 ak(位置 k) ③ 将 aj 与 ak 的值进行交换 ④ 将数列的 j+1 位到 n 位倒转。 int a[N]; // 初始化:a[i]是字典序最小的排列, 0?i<N int j,k; int p,q; int temp; …… j=(N-1) - 1; while ((j>=0)&&(a[j]>a[j+1])) j--; if (j>=0) { k=N-1; while (a[k]<a[j]) k--; temp=a[j], a[j]=a[k], a[k]=temp; // 从右往左寻找第一个小于右边的数,位置为j。 // 如果j<0说明已经排完了。

// 在j位置的右边寻找大于aj的最小数字ak(位置k) // 将aj与ak的值进行交换

99

NOIP 复习资料(C++版) for (p=j+1,q=N-1; p<q; p++,q--) // 将数列的j+1位到n位倒转 temp=a[p], a[p]=a[q], a[q]=temp; } 可以直接调用库函数:next_permutation(序列第一项的地址, 序列最后一项的地址) 该库函数能够用于可重集的排列。

(3) 由上一组合产生下一组合
① 从右向左寻找可以往下取一个元素的数,位置为 j。 (举个例子:从 7 个数中取 4 个数,有一个组合为 1367,那么 6、7 就不能再往下取了) ② 数列的 j 位到 n 位重新取元素。 注意: ① 从 N 个连续元素中取 M 个元素。如果元素序号不连续,就需要修改下面的“+1” 。 ② 右侧的数字一定严格大于左侧的数字。 int a[M]; // 初始化:a[i]是字典序最小的排序, 0?i<M,1?a[i]?N int j; …… j=M-1; while ((j>=0)&&(a[j]==N-(M-1 -j))) j--; if (i>=0) { a[j]++; for (int k=j+1; k<M; k++) a[k]=a[k-1]+1; }

11.3 秦九韶算法
【问题描述】已知一个一元 n 次多项式函数:f(x)=anxn+an-1xn-1+?+a1x+a0,已知 x0,求 f(x0)。 【方法 1】直接把 x0 代入到式子中。时间复杂度 O(n2)或 O(nlogn)。 【方法 2】 使用秦九韶算法:首先把多项式改写 f(x0) =anxn+an-1xn-1+?+a1x0+a0 0 0 n-1 =(anx0 +an-1xn-2+?+a1)x0+a0 0 n-2 =((anx0 +an-1xn-3+?+a2)x0+a1)x0+a0 0 =(?((anx0+an-1)x0+an-2)x0+?+a1)x0+a0 然后令 vk=(?(anx0+an-1)x0+?+an-(k-1))x0+an-k,则递推式为:
?v0=an ? ,其中 1?k?n ?vk=vk-1x0+an-k

求出 vn 即可。时间复杂度 O(n)。 秦九韶算法的一个典型应用是 N 进制变十进制。

100

NOIP 复习资料(C++版)

+11.4 进制转换
全局变量:int bit[20], top; // 最低位(个位)的下标是 0。

(1) 十进制变 N 进制——短除法
不断地除 N,直到那个数变成 1。把所有的余数连接到一起,就是转换后的 N 进制数。 void convert(int num, int base) { top=-1; do { bit[++top] = num%base; num/=base; } while (num>0); }

(2) N 进制变十进制
利用秦九韶公式进行计算。 int ans=0; for (int i=top; i>=0; i++) { ans*=base; ans+=bit[i]; } // ans*=2; 也可以写成 a<<=1;

+11.5 鸽巢原理、容斥原理*
5.1 鸽巢原理 1.简单形式 如果 n+1 个物体被放进 n 个盒子,那么至少有一个盒子包含两个或更多的物体。 例 1:在 13 个人中存在两个人,他们的生日在同一月份里。 例 2:设有 n 对已婚夫妇。为保证有一对夫妇被选出,至少要从这 2n 个人中选出多少人?(n+1) 2.加强形式 令 q1,q2,...qn 为正整数。如果将 q1+q2+...+qn-n+1 个物体放入 n 个盒子内,那么或者第一个盒子至少含有 q1 个物体,或者第二个盒子 至少含有 q2 个物体,...,或者第 n 个盒子含有 qn 个物体. 例 3:一篮子水果装有苹果、香蕉、和橘子。为了保证篮子内或者至少 8 个苹果或者至少 6 个香蕉或者至少 9 个橘子,则放入篮子中的水果的最小件数是多少?(21 件) 5.2 容斥原理及应用 原理:集 S 的不具有性质 P1,P2,...,Pm 的物体的个数由下式给出: |A1∩A2∩...∩Am|=|S|-∑|Ai|+∑|Ai∩Aj|-∑|Ai∩Aj∩Ak|+...+(-1)m|A1∩A2∩...∩Am| 如:m=3,时上式为: |A1∩A2∩A3|=|S|-(|A1|+|A2|+|A3|)+(|A1∩A2|+|A1∩A3|+|A2∩A3|)-|A1∩A2∩A3| 推论:至少具有性质 P1,P2,...Pm 之一的集合 S 的物体的个数有: | A1∪A2∪....∪Am|=|S|—|A1∩A2∩...∩Am|= ∑|Ai|-∑|Ai∩Aj|+∑|Ai∩Aj∩Ak|+...+(-1)m+1|A1∩A2∩...∩Am| 例 4:求从 1 到 1000 不能被 5,6,和 8 整除的整数的个数?

101

NOIP 复习资料(C++版) (1000-(200+166+125)+(33+25+41)-8=600)

+11.6 常见的递推关系
(1) 梵塔问题
【问题描述】已知有三根针分别用 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) { 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 步。 5.3 常见递推关系及应用 1.算术序列 每一项比前一项大一个常数 d; 若初始项为 h0:则递推关系为 hn=hn-1+d=h0+nd; 对应的各项为:h0,h0+d,h0+2d,....,h0+nd; 前 n 项的和为(n+1)h0+dn(n+1)/2 例 5: 1,2,3,... 例 6: 1,3,5,7...等都是算术序列。 2.几何序列 每一项是前面一项的常数 q 倍 若初始项为 h0:则递推关系为 hn=h0qn-1q=h0qn; 对应的各项为: h0,h0q1,h0q2,....,h0qn 例 7: 1,2,4,8,16,... 例 8: 5,15,45,135,...等都是几何序列; 前 n 项和为((qn+1-1)/(q-1) )h0 3.Fibonacci 序列 除第一、第二项外每一项是它前两项的和; 若首项为 f0 为 0,则序列为 0,1,1,2,3,5,8...递推关系为(n>=2)fn=fn-1+fn-2 前 n 项的和 Sn=f0+f1+f2+...+fn=fn+2-1 例 9:以下是 Fibonacci 的示例: // a是盘子来源,b是暂存区、c是目标

// 只有一根针时直接移动

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

102

NOIP 复习资料(C++版) 1.楼梯有 n 阶台阶,上楼可以一步上 1 阶,也可以一步上 2 阶,编一程序计算共有多少种不同的走法? 2.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问 n 个月后共有多少对兔子? 3.有 n*2 的一个长方形方格,用一个 1*2 的骨牌铺满方格。求铺法总数? 4.错位排列 首先看例题: 例 10:在书架上放有编号为 1,2,....n 的 n 本书。现将 n 本书全部取下然后再放回去,当放回去时要求每本 书都不能 放在原来的位置上。 例如:n=3 时: 原来位置为:123 放回去时只能为:312 或 231 这两种 问题:求当 n=5 时满足以上条件的放法共有多少种?(不用列出每种放法) (44) {1, 3, 2, ....,n}错位排列是{1,2,3,..,n}的一个排列 i1i2...in,使得 i1<>1,i2<>2,i3<>3,...in<>n 错位排列数列为 0,1,2,9,44,265,.... 错位排列的递推公式是:dn=(n-1)(dn-2+dn-1)(n>=3) =ndn-1+(-1)n-2 5.分平面的最大区域数 1.直线分平面的最大区域数的序列为: 2,4,7,11,...., 递推公式是: fn=fn-1+n=n(n+1)/2+1 2.折线分平面的最大区域数的序列为: 2, 7, 16,29, ..., 递推公式是:fn=(n-1)(2n-1)+2n; 3.封闭曲线(如一般位置上的圆)分平面的最大区域数的序列为: 2, 4, 8, 14,..., 递推公式是:fn=fn-1+2(n-1)=n2-n+2 6.Catalan 数列 先看下面两个例题: 例 11:将一个凸多边形区域分成三角形区域的方法数? 令 hn 表示具有 n+1 条边的凸多边形区域分成三角形的方法数。同时令 h1=1,则 hn 满足递推关系 hn=h1hn-1+h2hn-2+...+hn-1h1(n>=2)(想一想,为什么?) 该递推关系的解为 hn=c(2n-2,n-1)/n (n=1,2,3,...) 其对应的序列为 1,1,2,5,14,42,132,....从第二项开始分别是三边形,四边形,...的分法数 即 k 边形分成三角形的方法数为 hk=c(2k-4,k-2)/(k-1)(k>=3) 例 12:n 个+1 和 n 个-1 构成 2n 项 a1,a2,...,a2n 其部分和满足 a1+a2+...+ak>=0(k=1,2,3,..,2n)对与 n 该数列为 Cn=c(2k,k)/(k+1) (k>=0) 对应的序列为 1,1,2,5,14,42,132,... 序列 1,1,2,5,14,42,132,....叫 Catalan 数列。 7.卡特兰数 通项公式:f[n]=

(2n)! 2n ? (2 * n ? 1) ? .... ? (n ? 3) ? (n ? 2) = n! ? (n ? 1)! n ? (n ? 1) ? .... ? 3 ? 2
n>=2 9位 486 2 f[1]=1 10 位 16796

递推公式:f[n]=f[1]*f[n-1]+f[2]*f[n-2]+…+f[n-1]*f[1] 前十项: 1位 1 2位 2 3位 5 4位 14 5位 42 6位 132 7位 429 8位 143 0

103

NOIP 复习资料(C++版)

例 13:下列问题都是 Catalan 数列。 1.有 2n 个人排成一行进入剧场。入场费 5 元。其中只有 n 个人有一张 5 元钞票,另外 n 人只有 10 元钞票, 剧院无其它钞票,问有多少中方法使得只要有 10 元的人买票,售票处就有 5 元的钞票找零? 2.一位大城市的律师在她住所以北 n 个街区和以东 n 个街区处工作。每天她走 2n 个街区去上班。如果他 从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路? 3.在圆上选择 2n 个点,将这些点成对连接起来使得所得到的 n 条线段不相交的方法数? 4.n 个结点可够造多少个不同的二叉树? 5.一个栈(无穷大)的进栈序列为 1,2,3,..n,有多少个不同的出栈序列?

+11.6 表达式求值
(1) 递归
var s,st:string; a:array[0..26]ofstring; bool:array[0..26]ofboolean; ans,i,j,k,x,n:longint; functionmi(a,b:longint):longint; varmax,i:longint; begin max:=1; fori:=1tobdo begin max:=max*a; end; exit(max); end; functiondfs(l,r:longint):longint; varkh,fh,i,code,t:longint; begin kh:=0; fh:=0; fori:=rdowntol do begin if st[i]='('theninc(kh); if st[i]=')'thendec(kh); if kh=0then begin //当出现优先级运算时,采取后面的运算符;当相同运算符时,采 取前面的运算符 if (st[i]in ['+','-'])thenbeginfh:=i;break;endelse if (st[i]='*')and((fh=0)or(st[fh]in ['*','^']))thenfh:=ielse if (fh=0)and(st[i]='^')thenfh:=i; end; end;

104

NOIP 复习资料(C++版) if fh=0then begin if (st[l]='(')and(st[r]=')')thenexit(dfs(l+1,r-1)); if st[l]='('thenexit(dfs(l+1,r)); if st[r]=')'thenexit(dfs(l,r-1)); if st[l]='a'thenexit(x); val(copy(st,l,r-l+1),t,code); exit(t); end; if fh<>0then begin if st[fh]='+'thenexit((dfs(l,fh-1)+dfs(fh+1,r))); if st[fh]='-'thenexit((dfs(l,fh-1)-dfs(fh+1,r))); if st[fh]='*'thenexit((dfs(l,fh-1)*dfs(fh+1,r))); if st[fh]='^'thenexit(mi(dfs(l,fh-1),dfs(fh+1,r))); end; end; begin readln(st); writeln(dfs(1,length(st))); end.

(2) 利用堆栈来模拟运算
我们常用的科学计算器就是这样计算的。 1.表达式的求值 问题:能否设计算法,编制一个程序,让计算机扫描如下表达式,并将其值打印出来。 # 3 * ( 4 + 8 ) / 2 -5 # 注:给表达式设置#,标志扫描的开始和结束。 提示算法:设两个栈,一个是操作数栈,用来存放操作数,如 3、4、8 等,另一个是运算符栈,用来存放 运算符。 首先将标志―#‖进运算符栈的栈底。 然后依次扫描,按照栈的后进先出原则进行: (1)遇到操作数,进操作数栈; (2)遇到运算符时,则需将此运算符的优先级与栈顶运算符的优先级比较, 若若高于栈顶元素则进栈,继续扫描下一符号, 否则,将运算符栈的栈顶元素退栈,形成一个操作码 Q,同时操作数栈的栈顶元素两次退栈,形成两个操作 数 a、b,让计算机对操作数与操作码完成一次运算操作,即 aQb,并将其运算结果存放在操作数栈中…… 模拟计算机处理算术表达式过程。从键盘上输入算术表达式串(只含+、-、×、÷运算符,充许含括号) ,输出 算术表达式的值。设输入的表达式串是合法的。 附源程序: program exsj_1; const max=100; var number:array[0..max] of integer; symbol:array[1..max] of char; s,t:string;

105

NOIP 复习资料(C++版) i,p,j,code:integer; procedure push;{算符入栈运算} begin inc(p);symbol[p]:=s[i]; end; procedure pop;{运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算} begin dec(p); case symbol[p+1] of '+':inc(number[p],number[p+1]); '-':dec(number[p],number[p+1]); '*':number[p]:=number[p]*number[p+1]; '/':number[p]:=number[p] div number[p+1]; end; end; function can:boolean;{判断运算符的优先级别,建立标志函数} begin can:=true; if (s[i] in ['+','-']) and (symbol[p]<>'(') then exit; if (s[i] in ['*','/']) and (symbol[p] in ['*','/']) then exit; can:=false; end; begin write('String : '); readln(s); s:='('+s+')'; i:=1; p:=0; while i<=length(s) do begin while s[i]='(' do {左括号处理] begin push; inc(i); end; j:=i; repeat {取数入操作数栈} inc(i); until (s[i]<'0') or (s[i]>'9'); t:=copy(s,j,i-j); val(t,number[p],code); repeat if s[i]=')' then {右括号处理} begin while symbol[p]<>'(' do pop; dec(p); number[p]:=number[p+1]; end else begin {根据标志函数值作运算符入栈或出栈运算处理} while can do pop; push; end; inc(i); until (i>length(s)) or (s[i-1]<>')'); end;

106

NOIP 复习资料(C++版) write('Result=',number[0]); readln; end.

(3) 利用分治思想进行计算
对于这样的问题,我们常采用这样的思路处理:找出式中最后运算的运算符 A,先将其左右两边分别运 算(递归

相关文章:
NOIP复习资料终极版
NOIP复习资料(C++版) 218页 免费 NOIP实用算法 33页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...
NOIP复习资料终极版
宜昌一中 2009NOIP 复习资料 宜昌一中 2009NOIP 复习资料 感谢唐弢(TT) ,刘炟呈(CRL) ,陈艺(衬衣) ,猫(向缪丹妮) 等众位大牛的倾力支持 特别感谢袁逸铭(yy...
NOIP复习资料
G.基数排序 思想:对每个元素按从低位到高位对每一位进行一 次排序 Noip 复习资料 五、高精度计算高精度数的定义: type hp=array[1..maxlen] of integer; 1...
NOIP复赛复习资料汇总
NOIP复赛复习资料汇总_IT认证_资格考试/认证_教育专区。noip复赛资料 NOIP 复赛知识总结 (一) Pascal 过程与函数调用 * abs(x):y 取 x 的绝对值,x 与 y ...
NOIP复习资料终极版(改版)
Noip 2010 复习 A:aet of 1..40; //[1..40]者错了 [1..40]者错了 [1..40] Begin A:=[]; A:=a+[5,6]; /// Time:=meml[$40,$6c]; ...
NOIP试题集锦
(ans); 2013 年 10 月 18 日 noip2011 公交观光 描述 风景迷人的小城 Y ...口腔执业医师实践技能复习资料 中医护理学基础重点 执业医师实践技能考试模拟试题 ...
信息学竞赛NOIP复习资料
信息学竞赛NOIP复习资料_IT/计算机_专业资料。详细的信息学竞赛NOIP复习资料 第一章 PASCAL函数和技巧一、常用函数与过程: * abs(x):y 取x 的绝对值,x 与y ...
NOIP复习(动态规划)
[NOIP 复习]第三章:动态规划分类: NOIP Wikioi ACM-ICPC/蓝桥杯/其他大学竞赛 动态规划 2014-09-01 08:15 458 人阅读 评论(0) 收藏 举报 目录(?)[+] ...
NOIP复习手册.pdf
NOIP复习手册.pdf_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档NOIP复习手册.pdf_学科竞赛_高中教育_教育专区。NOIP 复习手册? ? ? ? ? ...
NOIP2004复赛复习资料
NOIP2004复赛复习资料_计算机软件及应用_IT/计算机_专业资料。noip2004复赛 NOIP 复习资料第一章 Pascal 函数与技巧 一、常用函数与过程: * abs(x):y 取 x 的...
更多相关标签: