1、 前 言 0 （ C+版） NOIP复习资料 主 编 葫芦岛市一高中 李思洋 完成日期 2012年 8月 27日 前 言 1 前 言 有一天，我整理了 NOIP 的笔记，并收集了一些经典算法。不过我感觉到笔记比较凌乱，并且有很多需要修改和补充的内容，于是我又搜集一些资料，包括一些经典习题，在几个月的时间内编写出了 NOIP 复习资料。 由于急于在假期之前打印出来并分发给同校同学 （ 我们学校既没有竞赛班，又没有懂竞赛的老师。我们大家都是自学党 ） ， NOIP 复习资料有很多的错误，还有一些想收录而未收录的内容。 在“减负”的背景下，暑期放了四十多天的假。于是我又有机会认真地修订 NOIP 复
2、习资料。 我编写资料的目的有两 个：总结我学过（ 包括没学会 ）的算法、数据结构等知识；与同学共享 NOIP 知识，同时使 我和 大家 的 RP+。 大家 要清醒地认识到， NOIP 复习资料页数多，是因为程序代码占了很大篇幅。这里 的内容 只是信息学的皮毛。对于我们来说，未来 学习 的路还很漫长。 基本假设 作为自学党， 大家 应该具有以下知识和能力： 能够熟练地运用 C+语言编写程序（ 或熟练地把 C+语言“翻译”成 Pascal 语言 ）； 能够阅读代码，理解代码含义，并尝试运用； 对各种算法和数据结构有一定了解，熟悉相关的概念； 学习了高中数学的算 法、数列、计数原理，对初等数论有一些
3、了解 ； 有较强的自学能力。 代码约定 N、 M、 MAX、 INF是事先定义好的常数 （ 不会在代码中 再次定义 ，除非代码是完整的 程序 ） 。 N、 M、 MAX针对数据规模而言，比实际最大数据规模大 ； INF 针对取值而言，是一个非常大，但又与 int 的最大值有一定差距的数，如 100000000。 对于不同程序， 数组下标的下限 也是不同的， 有的程序是 0，有的程序是 1。 阅读程序时要注意。 阅读顺序 和方法 没听说过 NOIP，或对 NOIP 不甚了解的同学，应该先阅读附录 E，以加强对竞赛的了解。 如果 不能顺利通过初赛，你 就应该 先补习初赛知识。这本 NOIP 复习资
4、料总结的是复赛知识。 如果没有学过 C+语言，应该先选择一本 C+语言教材。一般情况下，看到“面向对象编程”一章的前一页就足够了（ NOIP 不用“面向对象编程” ，更不用摆弄窗口对话框 ）。 附录 G介绍了一些书籍和网站。你应该选择一本书，认真地学习。再选择一个网站，作为练习的题库。 第一单元对竞赛中常用的操作和简单的算法分析进行了总结，算作对 C+语言的巩固。 同时，阅读这一单元之后，你应该选择一个合适的 C+代码编辑器。 第二到第六单元介绍了竞 赛常用的算法。 阅读每一章时，应该先阅读“小结” 名曰“小结”，实际上是“导读”。 这五个单元除了经典习题，还有某些思想和算法的具体实现方法。这
5、些信息 可能在明处，也可能在暗处 ，阅读时要注意 挖掘和体会 。如果有时间，应该在不看解析和代码的前提下独 立 完成这些题。 第七单元是第六单元的一个部分，由于它的内容来自背包九讲，所以单独放在一个单元。 从第八单元开始，到第十 三 单元，基本上就没有习题了 。 换句话说，该“背课文”了 。 第八单元介绍了常用的排序算法。你可以有选择地学习，但一定要掌握“ STL 算法 ”和“快速排序” 。 第九单元介绍了基本数据结构，你一定要掌握第九单元前五小节的内容（ 本单元也有应该优先阅读的“小结” ）。 有余力的话，第六小节的并查集也应该掌握。 前 言 2 第十单元介绍了与查找、检索有关的数据结构和算
6、法。你也可以有选择地学习。 第十一单元与数学有关。数学对于信息学来说具有举足 轻重的地位。标有“！”的应该背下来 ，至于其他内容，如果出题，你应该能把它解决。 第十二单元仍与数学有关。 第十三单元是图论。学习时要先阅读“小结”，把概念弄清楚。之后要掌握图的实现方法。接下来要掌握一些经典图论算法： Kruskal 算法、 Dijkstra 算法、 SPFA、 Floyd算法、拓扑排序 。 附录 F总结了 2004 年以来 NOIP 考察的知识点，可以作为选择性学习的参考。 在学习算法和数据结构的同时，应该阅读和学习附录 A。 如果你还有余力，你应该学习 第十四单元 。 第十四单元的 内容不是必须
7、要掌握的，但是一旦学会，可以发挥 C+语言的优势，降低编程复杂度。 临近竞赛时，应该阅读附录 B和附录 C，以增加经验，减少失误。 面临的问题 1. 这是复赛复习资料 需要有人能 用心 总结、整理初赛的知识，就像这份资料一样。 2. 潜在的问题还是相当多的，只是时间不够长，问题尚未暴露 。 3. 部分代码缺少解说 ，或解说混乱 。 4. 个人语文水平较差，资料也是如此。 5. 没有对应的 Pascal 语言版本。 如果有人能为 P党写一个 Pascal 版 的 STL，他的 RP 一定会爆增！ 6. 希望有人 能 用 L ATEX整理 资料 ，并以自由文档形式发布。 最后，欢迎大家以交流、分享
8、和提高为目的修改、复制、分发本资料，同时欢迎大家将资料翻译成 Pascal 语言版供更多 OIer 阅读！ 谢谢大家的支持！ 葫芦岛市一高中 李思洋 2012 年 8月 27日 目 录 I 目 录 标题 上的符号 ： 1. !：表示读者应该熟练掌握这些内容， 并且 在竞赛时能很快地写出来。换句话说就是应该背下来。 2. *：表示内容在 NOIP 中很少涉及，或者不完全适合 NOIP 的难度。 3. #：表示代码存在未更正的错误 ，或算法本身存在缺陷 。 前 言 . 1 目 录 . I 第一单元 C+语言基础 . 1 1.1 程序结构 . 1 1.2 数据类型 . 4 1.3 运算符 . 6 1
9、.4 函数 . 8 1.5 输入和输出 ! . 9 1.6 其他 常用操作 ! . 10 1.7 字符串操作 ! . 13 1.8 文件操作 ! . 13 1.9 简单的算法分析和优化 . 14 1.10 代码编辑器 . 16 第二单元 基础算法 . 17 2.1 经典枚举问题 . 17 2.2 火柴棒等式 . 18 2.3 梵塔问题 . 19 2.4 斐波那契数列 . 19 2.5 常见的递推关系 ! . 20 2.6 选择客栈 . 22 2.7 2k进制数 . 23 2.8 Healthy Holsteins . 24 2.9 小结 . 25 第三单元 搜索 . 27 3.1 N 皇后问题
10、 . 27 3.2 走迷宫 . 29 3.3 8 数码问题 . 31 3.4 埃及分数 . 34 3.5 Mayan 游戏 . 36 3.6 预处理和优化 . 40 3.7 代码模板 . 41 3.8 搜索题的一 些调试技巧 . 43 3.9 小结 . 44 第四单元 贪心算法 . 46 4.1 装载问题 . 46 4.2 区间问题 . 46 4.3 删数问题 . 47 4.4 工序问题 . 47 4.5 种树问题 . 47 4.6 马的哈密尔顿链 . 47 4.7 三值 的 排序 . 49 4.8 田忌赛马 . 50 4.9 小结 . 50 第五单元 分治算法 . 51 5.1 一元三次方程
11、求解 . 51 5.2 快速幂 . 51 5.3 排序 . 51 5.4 最长非降子序列 . 53 5.5 循环赛日程表问题 . 53 5.6 棋盘覆盖 . 54 5.7 删除多余括号 . 55 5.8 聪明的 质监员 . 56 5.9 模板 . 58 5.10 小结 . 59 第六单元 动态规划 . 60 6.1 导例：数字三角形 . 60 6.2 区间问题：石子合并 . 63 6.3 坐标问题 . 65 6.4 背包问题 . 67 6.5 编号问题 . 67 6.6 递归结构问题 . 68 6.7 DAG 上的最短路径 . 71 6.8 树形动态规划 * . 72 6.9 状态压缩类问题：
12、过河 . 74 6.10 Bitonic 旅行 . 76 6.11 小结 . 77 第七单元 背包专题 . 78 7.1 部分背包问题 . 78 7.2 0/1 背包问题 ! . 78 7.3 完全背包问题 . 79 7.4 多重背包问题 . 79 7.5 二维费用的背包问题 . 80 7.6 分组的背包问题 . 81 7.7 有依赖的背包问题 . 81 7.8 泛化物品 . 81 7.9 混合背包问题 . 82 7.10 特殊要求 . 82 7.11 背包问题的搜索解法 . 83 7.12 子集和问题 . 84 第八单元 排序算法 . 85 8.1 常用排序算法 . 85 8.2 简单排序算
13、法 . 87 8.3 线性时间排序 . 88 8.4 使用二叉树的排序算法 * . 89 8.5 小结 . 90 第九单元 基本数据结构 . 91 目 录 II 9.1 线性表（顺序结构） . 91 9.2 线性表（链式结构） . 91 9.3 栈 . 93 9.4 队列 . 94 9.5 二叉树 . 95 9.6 并查集 ! . 99 9.7 小结 . 102 第十单元 查找与检索 . 105 10.1 顺序查找 . 105 10.2 二分查找 ! . 105 10.3 查找第 k 小元素 !. 106 10.4 二叉排序树 . 107 10.5 堆和优先队列 * . 109 10.6 哈夫
14、曼（ Huffman）树 . 111 10.7 哈希（ Hash）表 . 113 第十一单元 数学基础 . 117 11.1 组合数学 . 117 11.2 组合数的计算 ! . 118 11.3 排列和组合的产生（无重集元素） ! 118 11.4 排列和组合的产生（有重集元素） . 121 11.5 秦九韶算法 . 123 11.6 进制转换（正整数） . 124 11.7 高精度算法（压位存储） ! . 124 11.8 快速幂 ! . 129 11.9 表达式求值 . 130 11.10 解线性方程组 * . 134 第十二单元 数论算法 . 136 12.1 同余的性质 ! . 13
15、6 12.2 最大公约数、最小公倍数 ! . 136 12.3 解不定方程 ax by c!* . 136 12.4 同余问题 * . 137 12.5 素数和素数表 . 137 12.6 分解质因数 . 138 第十三单元 图与图论算法 . 140 13.1 图的实现 . 140 13.2 图的遍历 . 142 13.3 连通性问题 . 143 13.4 欧拉回路 邻接矩阵 . 147 13.5 最小生成树 （ MST） . 148 13.6 单源最短路问题 （ SSSP 问题 ） . 149 13.7 每两点间最短路问题（ APSP 问题） !153 13.8 拓扑排序 . 153 13.
16、9 关键路径 . 156 13.10 二分图初步 . 158 13.11 小结 . 161 第十四单元 STL简介 . 165 14.1 STL 概述 . 165 14.2 常用容器 . 165 14.3 容器适配器 . 171 14.4 常用算法 . 172 14.5 迭代器 . 176 14.6 示例：合并果子 . 176 附录 A 思想和技巧 . 178 A.1 时间 /空间权衡 . 178 A.2 试验、猜想及归纳 . 178 A.3 模型 化 . 178 A.4 随机化 * . 179 A.5 动态化静态 . 179 A.6 前序和 ! . 180 A.7 状态压缩 * . 181
17、A.8 抽样测试法 * . 183 A.9 离散化 * . 184 A.10 Flood Fill* . 185 附录 B 调试 . 186 B.1 常见错误类型 . 186 B.2 调试过程 . 186 B.3 调试功能 . 186 B.4 符号 DEBUG 的应用 . 187 B.5 代码审查表 . 187 B.6 故障检查表 . 188 B.7 命令行和批处理 * . 189 附录 C 竞赛经验和教训 . 193 C.1 赛前两星期 . 193 C.2 赛前 30 分钟 . 193 C.3 解题表 . 194 C.4 测试数据 . 196 C.5 交卷前 5 分钟 . 197 C.6 避
18、免偶然错误 . 197 C.7 骗分 . 198 附录 D 学习建议 . 199 D.1 学习方法 . 199 D.2 学习能力 . 199 D.3 关于清北学堂 . 199 附录 E 竞赛简介 . 200 E.1 从 NOIP 到 IOI. 200 E.2 NOIP 简介 . 200 E.3 常用语 . 202 E.4 第一次参加复赛 . 203 附录 F NOIP 复赛知识点分布 . 205 附录 G 资料推荐 . 206 G.1 书籍 . 206 G.2 网站 . 206 参考文献 . 207 计算机专业是朝阳还是夕阳？ . 208 杜子德在 CCF NOI2012 开幕式上的讲话 21
19、0 多数奥赛金牌得主为何难成大器 . 211 第 一 单元 C+语言 基础 1 第 一 单元 C+语言 基础 1.1 程序结构 (1) 程序框架 注释：注释有两种，一种是“ /”，另一种是“ /* */”。“ /”必须单独放置一行，或代码所在行的后面；而 “ /*”、“ */”成对存在，可以插入到代码的任意位置。 引用头文件：在代码开头写“ #include ”。如果想引用自己的头文件，需要把尖括号 （ 表示只从系统目录搜索头文件 ） 换成双引号 （ 表示先从 cpp 所在文件夹 搜索 ，然后再到系统文件夹搜索 ） 。 命名空间：很多 C+的东西都要引用 std 命名空间，所以代码中会有“ u
20、sing namespace std;”。 main()：所有程序都要从 main()开始。 在所有的算法竞赛中， main()的返回值必须是 0，否则视为程序异常结束，得分为 0分。 语句和语句块： 1. 语句：一般情况下，一条语句要用一个分号“ ;”结束。为了美观和可读性，可以把一条语句扩展成几行，也可以把多个语句写到同一行上。 2. 语句块：用“ ”和“ ”包围的代码是语句块。无论里面有多少代码，在原则上，语句块所在的整体都视为一条语句。 (2) 选择结构 1. if 语句： if 表示判断。如果条件为真，就执行 接在 if 后的语句 （ 语句块 ），否则执行 else 后的语句（ 语句
21、块 ）。如果没有 else，就直接跳过。 if 有以下几种格式： if (条件 ) / 如果条件成立，就执行 if后面的语句或语句块。 语句或语句块 if (条件 ) / 如果条件成立，就执行 if后面的 A，否则执行 B。 语句或语句块 A else 语句或语句块 B if (条件 1) / 实际上，这是 if语句内的 if语句，即 if的嵌套。所以 else和 if中间要有空格。 语句或语句块 A else if (条件 2) 语句或语句块 B else 语句或语句块 N 2. switch 语句： switch 表示选择。它根据条件的不同取值来执行不同的语句。 格式如下： switch
22、(表达式 ) case 值 1: 代码段 A break; case 值 2: 代 码段 B break; 第 一 单元 C+语言 基础 2 default: 代码段 N break; ; 如果表达式的值是值 1，就执行代码段 A；如果表达式的值是值 2，就执行代码段 B否则执行代码段 N。 注意： default 一部分可以省略。 如果不使用 break，那么紧随其后的 case 部分代码也会被执行 ，直到遇到 break 或 switch 语句结束为止 ！ switch 结尾要有一个分号。 3. if、 switch 都可以嵌套使用。 【问题描述】输入一个 日期 ，判断 它所在年份 是否为
23、闰年，并输出 所在 月 份 的天数。 闰年的判断方法：四年一闰，百年不闰， 四百年又闰。 int year,month,day; bool b=false; cinyearmonthday; / 判断是否为闰年 if (n%400=0) b=true; else if (n%100!=0 if (b) cout” ，还是 “ =”。 逆序循环时，不要把自减“ -”写成自增“ +”！ 【问题描述】输入 n，输出 n!（ n! 1 2 3 4 n） 。结果保证小于 long long的范围。 当输入值为负数时结束程序。 int n; long long r=1; cinn; while (n-1)
24、 r=1; for (int i=1; in; (4) goto 语句 goto 语句用于无条件跳转。 要想跳转，首先要定义标签 （在代码开头的一段标识符，后面紧跟冒号） ，然后才能 goto 那个标签。 很多教程不提倡使用无条件跳转，因为它破坏了程序结 构，还容易给代码阅读者带来麻烦。 不过， 这不代表 goto 没有使用价值。 goto 的一个用途是跳出多层循环： for (int i=0; i应该改成 。 C程序运行速度稍优于 C+。 不过也没快多少。 总之， C能做的一切事情， C+也能做； C+能做的一切事情， C不一定能做。 1.2 数据类型 (1) 基本数据类型 名称 占用 空间
25、 别名 数据范围 int 4 signed, signed int, long, long int 2,147,483,648 2,147,483,647 unsigned int 4 unsigned, unsigned long,unsigned long int 0 4,294,967,295 char 1 char 128 127 unsigned char 1 unsigned char 0 255 short 2 short int, signed short int 32,768 32,767 unsigned short 2 unsigned short int 0 65,53
26、5 long long 8 signed long long 9,223,372,036,854,775,808 9,223,372,036,854,775,807 unsigned long long 8 0 18,446,744,073,709,551,615 bool 1 true 或 false char 1 128 127 signed char 1 128 127 一般都使用有符号整数，除非范围不够大，或者你确定你的减法运算不会出现 小数减 大数 。 一般来说，使用 int、 long long更保险一些 ，除非内存不够用。 不要使用“ _int64”！ 它是 Visual C+特
27、有的关键字。 假如 a是 long long类型，把超过 231的值赋给它时要使用字面值 LL（ ULL）： a=123456789012345LL。 第 一 单元 C+语言 基础 5 unsigned char 1 0 255 float 4 3.4E +/- 38 (7位有效数字 ) double 8 long double 1.7E +/- 308 (15位有效数字 ) (2) 变量与常量 1. 定义变量：“变量类型 标识符”，如“ int i;”定义了一个名字为 i的整型变量。 注意，此时 i并未初始化，所以 i的值是不确定的 。 2. 定义常量：“ const 变量类型 标识符 =初
28、始值”，如： const int N=90; 3. 合法的 标识符： 标识符不能和关键字 （在 IDE 中会变色的词语） 相同。 标识符只能包括字母、数字和下划线“ _”，并且开头只能是字母或下划线。 标识符必须先定义后使用。 在同一作用域内，标识符不能重复定义 （ 即使 在不同作用域内 也不 应 重复， 否则容易 产生 歧义） 。 C+区分大小写 。所以 A和 a是两个不同的标识符。 (3) 数组 1. 定义 一个 一维数组： int a10; 这个数组一共 10 个元素，下标分别为 0 9。访问某个元素时，直接用 a加方括号，如 a5。 2. 定义一个二维数组： int b53; 这个数组一共 5 3 15 个元素，分别是 b00、 b01、 b02、 b10 b42。 访问某个元素时要用两个方括号，如 b21。 多维数组的 定义和使用方法与此 类似。 3. 数组名 和元素的寻址 ：以上面的 a、 b为 例 数组名是一个指针，指向整个数组第一个元素所在的地址。如 a就是
