【分享】NOIP复习资料（C++）

本人自学党，所在学校没有竞赛班和竞赛教师——所以同学们都是自学党。
于是，我编写了一份《NOIP复习资料》，作为考前必备书，发给了每位同学。
不过当时写得很着急，也没有仔细修改，所以未敢对外发布。
现在，经过一假期的修订，我决定把《NOIP复习资料》分享给各位。由于临近开学，马上上高三了，所以我没有办法再改写成Pascal和C的。欢迎大家改写！
地址：
http://pan.baidu.com/share/link?shareid=7632&uk=2147700581
附带一些其他的东西，如各年试题和数据、USACO测试数据等
说明：
① 有人曾经发布过类似的文档，约170页，那是我的未编写完的草稿，错误很多，内容不全，如果有遇到的同学，希望不要再去下载。
② 《资料》内的第七章实际上来自《背包九讲》。
③ 欢迎自由传播。


目录：
由分割线分成两部分，上半部分算法和习题，下半部分是代码模板。
前 言 ........................... 1
目 录 ........................... I
第一单元 C++语言基础 .............. 1
1.1 程序结构 ...................... 1
1.2 数据类型 ...................... 4
1.3 运算符 ........................ 6
1.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皇后问题 .................... 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 一元三次方程求解 .............. 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 状态压缩类问题：过河 ........... 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 简单排序算法 ................. 87
8.3 线性时间排序 ................. 88
8.4 使用二叉树的排序算法* .......... 89
8.5 小结 ........................ 90
第九单元 基本数据结构 ............ 91
9.1 线性表（顺序结构） ............. 91
9.2 线性表（链式结构） ............. 91
9.3 栈 .......................... 93
9.4 队列 ......................... 94
9.5 二叉树 ....................... 95
9.6 并查集! ...................... 99
9.7 小结 ........................ 102
第十单元 查找与检索 ............. 104
10.1 顺序查找 ................... 104
10.2 二分查找! .................. 104
10.3 查找第k小元素! ............. 105
10.4 二叉排序树 .................. 106
10.5 堆和优先队列* ............... 108
10.6 哈夫曼（Huffman）树 ......... 110
10.7 哈希（Hash）表 .............. 111
第十一单元 数学基础 ............. 116
11.1 组合数学 ................... 116
11.2 组合数的计算! ............... 117
11.3 排列和组合的产生（无重集元素）! 117
11.4 排列和组合的产生（有重集元素） . 120
11.5 秦九韶算法 .................. 122
11.6 进制转换（正整数） ........... 123
11.7 高精度算法（压位存储）! ....... 123
11.8 快速幂! .................... 128
11.9 表达式求值 .................. 129
11.10 解线性方程组* .............. 133
第十二单元 数论算法 ............. 135
12.1 同余的性质! ................. 135
12.2 最大公约数、最小公倍数! ....... 135
12.3 解不定方程ax＋by＝c!* ....... 135
12.4 同余问题* .................. 136
12.5 素数和素数表 ................ 136
12.6 分解质因数 .................. 137
第十三单元 图与图论算法 .......... 139
13.1 图的实现 ................... 139
13.2 图的遍历 ................... 141
13.3 连通性问题 .................. 142
13.4 欧拉回路 [邻接矩阵] ......... 146
13.5 最小生成树（MST） ........... 147
13.6 单源最短路问题（SSSP问题） ... 148
13.7 每两点间最短路问题（APSP问题）!152
13.8 拓扑排序 ................... 152
13.9 关键路径 ................... 155
13.10 二分图初步 ................. 157
13.11 小结 ...................... 160
第十四单元 STL简介 ............. 164
14.1 STL概述 ................... 164
14.2 常用容器 ................... 164
14.3 容器适配器 .................. 170
14.4 常用算法 ................... 171
14.5 迭代器 ..................... 175
14.6 示例：合并果子 .............. 175
附录A 思想和技巧 ............... 177
A.1 时间/空间权衡 ............... 177
A.2 试验、猜想及归纳 ............. 177
A.3 模型化 ..................... 177
A.4 随机化* .................... 178
A.5 动态化静态 .................. 178
A.6 前序和! .................... 179
A.7 状态压缩*................... 180
A.8 抽样测试法* ................. 182
A.9 离散化* .................... 183
A.10 Flood Fill* .............. 184
附录B 调试 .................... 185
B.1 常见错误类型 ................ 185
B.2 调试过程.................... 185
B.3 调试功能.................... 185
B.4 符号DEBUG的应用 ............ 186
B.5 代码审查表 .................. 186
B.6 故障检查表 .................. 187
B.7 命令行和批处理* .............. 188
附录C 竞赛经验和教训 ............ 192
C.1 赛前两星期 .................. 192
C.2 赛前30分钟 ................. 192
C.3 解题表 ..................... 193
C.4 测试数据.................... 195
C.5 交卷前5分钟 ................ 196
C.6 避免偶然错误 ................ 196
C.7 骗分 ....................... 197
附录D 学习建议 ................. 198
D.1 学习方法.................... 198
D.2 学习能力.................... 198
D.3 关于清北学堂 ................ 198
附录E 竞赛简介 ................. 199
E.1 从NOIP到IOI ............... 199
E.2 NOIP简介 .................. 199
E.3 常用语 ..................... 201
E.4 第一次参加复赛…… ........... 202
附录F NOIP复赛知识点分布 ....... 204
附录G 资料推荐 ................. 205
G.1 书籍 ....................... 205
G.2 网站 ....................... 205
参考文献 ....................... 206
计算机专业是朝阳还是夕阳？ ........ 207
杜子德在CCF NOI2012开幕式上的讲话 209
多数奥赛金牌得主为何难成大器 ...... 210


祝大家RP++，竞赛一等奖

= =学长是你么。。。洋

lz是好人。。。

给自己编复习书的神犇跪烂！！！抱走了>o<

宝贵的成果啊

鼓掌

感觉学完就可以进队了。。。顶起，赞个

orz

thank