没有合适的资源?快使用搜索试试~ 我知道了~
NOIP复习资料(C++版)精编版.doc
需积分: 0 0 下载量 101 浏览量
2023-12-27
21:38:08
上传
评论
收藏 1.79MB DOC 举报
温馨提示
试读
214页
C++ NOIP
资源推荐
资源详情
资源评论
……………………………………………………………最新资料推荐…………………………………………………
0
(C++版)
NOIP 复习资料
主 编 葫芦岛市一高中 李思洋
完成日期 2012 年 8 月 27 日
……………………………………………………………最新资料推荐…………………………………………………
1
前 言
有一天,我整理了 NOIP 的笔记,并收集了一些经典算法。不过我感觉到笔记比较凌乱,并且有很多需要修
改和补充的内容,于是我又搜集一些资料,包括一些经典习题,在几个月的时间内编写出了《NOIP 复习资
料》。
由于急于在假期之前打印出来并分发给同校同学(我们学校既没有竞赛班,又没有懂竞赛的老师。我们大家
都是自学党),《NOIP 复习资料》有很多的错误,还有一些想收录而未收录的内容。
在“减负”的背景下,暑期放了四十多天的假。于是我又有机会认真地修订《NOIP 复习资料》。
我编写资料的目的有两个:总结我学过(包括没学会)的算法、数据结构等知识;与同学共享 NOIP 知识,
同时使我和大家的 RP++。
大家要清醒地认识到,《NOIP 复习资料》页数多,是因为程序代码占了很大篇幅。这里的内容只是信息学
的皮毛。对于我们来说,未来学习的路还很漫长。
基本假设
作为自学党,大家应该具有以下知识和能力:
① 能够熟练地运用 C++语言编写程序(或熟练地把 C++语言“翻译”成 Pascal 语言);
② 能够阅读代码,理解代码含义,并尝试运用;
③ 对各种算法和数据结构有一定了解,熟悉相关的概念;
④ 学习了高中数学的算法、数列、计数原理,对初等数论有一些了解;
⑤ 有较强的自学能力。
代码约定
N、M、MAX、INF 是事先定义好的常数(不会在代码中再次定义,除非代码是完整的程序)。N、M、MAX
针对数据规模而言,比实际最大数据规模大;INF 针对取值而言,是一个非常大,但又与 int 的最大值有一定
差距的数,如 100000000。
对于不同程序,数组下标的下限也是不同的,有的程序是 0,有的程序是 1。阅读程序时要注意。
阅读顺序和方法
没听说过 NOIP,或对 NOIP 不甚了解的同学,应该先阅读附录 E,以加强对竞赛的了解。
如果不能顺利通过初赛,你就应该先补习初赛知识。这本《NOIP 复习资料》总结的是复赛知识。
如果没有学过 C++语言,应该先选择一本 C++语言教材。一般情况下,看到“面向对象编程”一章的前一
页就足够了(NOIP 不用“面向对象编程”,更不用摆弄窗口对话框)。
附录 G 介绍了一些书籍和网站。你应该选择一本书,认真地学习。再选择一个网站,作为练习的题库。
第一单元对竞赛中常用的操作和简单的算法分析进行了总结,算作对 C++语言的巩固。同时,阅读这一单元
之后,你应该选择一个合适的 C++代码编辑器。
第二到第六单元介绍了竞赛常用的算法。阅读每一章时,应该先阅读“小结”——名曰“小结”,实际上是
“导读”。
这五个单元除了经典习题,还有某些思想和算法的具体实现方法。这些信息可能在明处,也可能在暗处,阅
读时要注意挖掘和体会。如果有时间,应该在不看解析和代码的前提下独立完成这些题。
第七单元是第六单元的一个部分,由于它的内容来自《背包九讲》,所以单独放在一个单元。
从第八单元开始,到第十三单元,基本上就没有习题了。换句话说,该“背课文”了。
第八单元介绍了常用的排序算法。你可以有选择地学习,但一定要掌握“STL 算法”和“快速排序”。
第九单元介绍了基本数据结构,你一定要掌握第九单元前五小节的内容(本单元也有应该优先阅读的“小
结”)。有余力的话,第六小节的并查集也应该掌握。
……………………………………………………………最新资料推荐…………………………………………………
2
第十单元介绍了与查找、检索有关的数据结构和算法。你也可以有选择地学习。
第十一单元与数学有关。数学对于信息学来说具有举足轻重的地位。标有“!”的应该背下来,至于其他内
容,如果出题,你应该能把它解决。
第十二单元仍与数学有关。
第十三单元是图论。学习时要先阅读“小结”,把概念弄清楚。之后要掌握图的实现方法。接下来要掌握一
些经典图论算法:Kruskal(克鲁斯卡尔)算法、Dijkstra(迪杰斯特拉)算法、SPFA(Bellman-Ford)、
Floyd(佛洛依德)算法、拓扑排序。
附录 F 总结了 2004 年以来 NOIP 考察的知识点,可以作为选择性学习的参考。
在学习算法和数据结构的同时,应该阅读和学习附录 A。
如果你还有余力,你应该学习第十四单元。第十四单元的内容不是必须要掌握的,但是一旦学会,可以发挥 C++
语言的优势,降低编程复杂度。
临近竞赛时,应该阅读附录 B 和附录 C,以增加经验,减少失误。
面临的问题
1. 这是复赛复习资料——需要有人能用心总结、整理初赛的知识,就像这份资料一样。
2. 潜在的问题还是相当多的,只是时间不够长,问题尚未暴露。
3. 部分代码缺少解说,或解说混乱。
4. 个人语文水平较差,《资料》也是如此。
5. 没有对应的 Pascal 语言版本。
6. 如果有人能为 P 党写一个 Pascal 版的 STL,他的 RP 一定会爆增!
7. 希望有人能用
L
A
T
E
X
整理《资料》,并以自由文档形式发布。
最后,欢迎大家以交流、分享和提高为目的修改、复制、分发本《资料》,同时欢迎大家将《资料》翻译
成 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.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 2
k
进制数 .....................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
……………………………………………………………最新资料推荐…………………………………………………
II
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
剩余213页未读,继续阅读
资源评论
mediavisual
- 粉丝: 0
- 资源: 28
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功