没有合适的资源?快使用搜索试试~ 我知道了~
首页NOIP复习资料(C++版).doc
中小学信息学奥赛(noip)学习的好资料,纯word版的,对广大的信息奥赛① 能够熟练地运用C++语言编写程序(或熟练地把C++语言“翻译”成Pascal语言); ② 能够阅读代码,理解代码含义,并尝试运用; ③ 对各种算法和数据结构有一定了解,熟悉相关的概念; ④ 学习了高中数学的算法、数列、计数原理,对初等数论有一些了解; ⑤ 有较强的自学能力。
资源详情
资源推荐
前 言
0
(C++版)
NOIP 复习资料
前 言
前 言
有一天,我整理了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++代码编辑器。
第二到第六单元介绍了竞赛常用的算法。阅读每一章时,应该先阅读“小结”——名曰“小结”,实际上是“导
读”。
这五个单元除了经典习题,还有某些思想和算法的具体实现方法。这些信息可能在明处,也可能在暗处,阅
读时要注意挖掘和体会。如果有时间,应该在不看解析和代码的前提下独立完成这些题。
第七单元是第六单元的一个部分,由于它的内容来自《背包九讲》,所以单独放在一个单元。
从第八单元开始,到第十三单元,基本上就没有习题了。换句话说,该“背课文”了。
1
前 言
第八单元介绍了常用的排序算法。你可以有选择地学习,但一定要掌握“STL算法”和“快速排序”。
第九单元介绍了基本数据结构,你一定要掌握第九单元前五小节的内容(本单元也有应该优先阅读的“小
结”)。有余力的话,第六小节的并查集也应该掌握。
第十单元介绍了与查找、检索有关的数据结构和算法。你也可以有选择地学习。
第十一单元与数学有关。数学对于信息学来说具有举足轻重的地位。标有“!”的应该背下来,至于其他内容
如果出题,你应该能把它解决。
第十二单元仍与数学有关。
第十三单元是图论。学习时要先阅读“小结”,把概念弄清楚。之后要掌握图的实现方法。接下来要掌握一些
经典图论算法:Kruskal算法、Dijkstra算法、SPFA、Floyd算法、拓扑排序。
附录F总结了2004年以来NOIP考察的知识点,可以作为选择性学习的参考。
在学习算法和数据结构的同时,应该阅读和学习附录A。
如果你还有余力,你应该学习第十四单元。第十四单元的内容不是必须要掌握的,但是一旦学会,可以发挥
C++语言的优势,降低编程复杂度。
临近竞赛时,应该阅读附录B和附录C,以增加经验,减少失误。
面临的问题
1. 这是复赛复习资料——需要有人能用心总结、整理初赛的知识,就像这份资料一样。
2. 潜在的问题还是相当多的,只是时间不够长,问题尚未暴露。
3. 部分代码缺少解说,或解说混乱。
4. 个人语文水平较差,《资料》也是如此。
5. 没有对应的Pascal语言版本。
如果有人能为P党写一个Pascal版的STL,他的RP一定会爆增!
6. 希望有人能用L整理《资料》,并以自由文档形式发布。
最后,欢迎大家以交流、分享和提高为目的修改、复制、分发本《资料》,同时欢迎大家将《资料》翻译
成Pascal语言版供更多OIer阅读!
谢谢大家的支持!
2
目 录
目 录
标题上的符号:
1. !:表示读者应该熟练掌握这些内容,并且在竞赛时能很快地写出来。换句话说就是应该背下来。
2. *:表示内容在NOIP中很少涉及,或者不完全适合NOIP的难度。
3. #:表示代码存在未更正的错误,或算法本身存在缺陷。
前 言
.................................................................1
目 录
.................................................................I
第
1
单元
C++
语言基础
...................................................1
1.1 程序结构................................................................1
1.2 数据类型................................................................4
1.3 运算符..................................................................6
1.4 函数...................................................................8
1.5 输入和输出!.............................................................9
1.6 其他常用操作!...........................................................10
1.7 字符串操作!............................................................12
1.8 文件操作!..............................................................13
1.9 简单的算法分析和优化.....................................................14
1.10 代码编辑器............................................................15
第
2
单元 基础算法
.....................................................17
2.1 经典枚举问题............................................................17
2.2 火柴棒等式.............................................................18
2.3 梵塔问题...............................................................19
2.4 斐波那契数列............................................................19
2.5 常见的递推关系!.........................................................20
2.6 选择客栈...............................................................21
2.7 2
k
进制数...............................................................23
2.8 Healthy Holsteins.....................................................24
2.9 小结..................................................................25
第
3
单元 搜索
........................................................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
第
4
单元 贪心算法
.....................................................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
I
目 录
4.9 小结..................................................................50
第
5
单元 分治算法
.....................................................52
5.1 一元三次方程求解........................................................52
5.2 快速幂.................................................................52
5.3 排序..................................................................52
5.4 最长非降子序列..........................................................54
5.5 循环赛日程表问题........................................................54
5.6 棋盘覆盖...............................................................55
5.7 删除多余括号............................................................56
5.8 聪明的质监员............................................................57
5.9 模板..................................................................59
5.10 小结.................................................................60
第
6
单元 动态规划
.....................................................61
6.1 导例:数字三角形........................................................61
6.2 区间问题:石子合并.......................................................64
6.3 坐标问题...............................................................66
6.4 背包问题...............................................................68
6.5 编号问题...............................................................68
6.6 递归结构问题............................................................69
6.7 DAG 上的最短路径........................................................71
6.8 树形动态规划*...........................................................72
6.9 状态压缩类问题:过河.....................................................75
6.10 Bitonic 旅行..........................................................76
6.11 小结.................................................................77
第
7
单元 背包专题
.....................................................79
7.1 部分背包问题............................................................79
7.2 0/1 背包问题!...........................................................79
7.3 完全背包问题............................................................80
7.4 多重背包问题............................................................80
7.5 二维费用的背包问题.......................................................81
7.6 分组的背包问题..........................................................82
7.7 有依赖的背包问题........................................................82
7.8 泛化物品...............................................................82
7.9 混合背包问题............................................................83
7.10 特殊要求..............................................................83
7.11 背包问题的搜索解法......................................................84
7.12 子集和问题............................................................85
第
8
单元 排序算法
.....................................................86
8.1 常用排序算法............................................................86
8.2 简单排序算法............................................................88
8.3 线性时间排序............................................................89
8.4 使用二叉树的排序算法*....................................................90
8.5 小结..................................................................91
第
9
单元 基本数据结构
.................................................92
9.1 线性表(顺序结构).......................................................92
9.2 线性表(链式结构).......................................................92
9.3 栈....................................................................94
9.4 队列..................................................................95
9.5 二叉树.................................................................96
9.6 并查集!...............................................................100
9.7 小结.................................................................103
第
10
单元 查找与检索
.................................................105
II
剩余63页未读,继续阅读
dqcsm1964
- 粉丝: 58
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功