- 1、本文档共217页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
前 言
前 言
1
1
主 编 葫芦岛市一高中 李思洋完成日期
主 编 葫芦岛市一高中 李思洋
完成日期 2012年8月27日
NOIP复习资料
(C++版)
前 言
有一天,我整理了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算法”和“快速排序”。
第九单元介绍了基本数据结构,你一定要掌握第九单元前五小节的内容(本单元也有应该优先阅读的“小结”)。有余力的话,第六小节的并查集也应该掌握。
第十单元介绍了与查找、检索有关的数据结构和算法。你也可以有选择地学习。
第十一单元与数学有关。数学对于信息学来说具有举足轻重的地位。标有“!”的应该背下来,至于其他内容,如果出题,你应该能把它解决。
第十二单元仍与数学有关。
第十三单元是图论。学习时要先阅读“小结”,把概念弄清楚。之后要掌握图的实现方法。接下来要掌握一些经典图论算法:Kruskal算法、Dijkstra算法、SPFA、Floyd算法、拓扑排序。
附录F总结了2004年以来NOIP考察的知识点,可以作为选择性学习的参考。
在学习算法和数据结构的同时,应该阅读和学习附录A。
如果你还有余力,你应该学习第十四单元。第十四单元的内容不是必须要掌握的,但是一旦学会,可以发挥C++语言的优势,降低编程复杂度。
临近竞赛时,应该阅读附录B和附录C,以增加经验,减少失误。
面临的问题
这是复赛复习资料——需要有人能用心总结、整理初赛的知识,就像这份资料一样。
潜在的问题还是相当多的,只是时间不够长,问题尚未暴露。
部分代码缺少解说,或解说混乱。
个人语文水平较差,《资料》也是如此。
没有对应的Pascal语言版本。如果有人能为P党写一个Pascal版的STL,他的RP一定会爆增!
希望有人能用 eq \o(L, \s\up3( A))T\s\do3(E)X整理《
您可能关注的文档
- Mr.Dohetty-Builds-His-Dream-Life原文和翻译培训教材.docx
- MR:女性盆腔疾病应用讲解学习.ppt
- MRI临床应用教程文件.ppt
- MRI软组织肿瘤的影像诊断讲课教案.ppt
- MRI在腹部疾病中的应用幻灯片课件.ppt
- MSDS-培训(特气部分)复习课程.ppt
- MSHUO服饰品牌商业计划文章讲解材料.doc
- MS中文教程说课材料.ppt
- My-First-Ride-on-a-Train全课讲解学习.pptx
- My-First-Ride-On-a-Train外研版高一英语必修一讲解学习.ppt
- AN024_星历原始观测数据协议.pdf
- APM32F051x6x8数据操作说明 V1.6中文.pdf
- AN1086_APM32F4xx_ISP应用笔记中文.pdf
- APM32F051R8 EVAL Board使用调试操作说明V1.0中文.pdf
- APM32F4xxx用户操作说明 V2.2中文.pdf
- APM32F411xCxE 数据操作说明 V1.3中文.pdf
- AN019_NMEA0183协议说明_北云科技.pdf
- AGP21系列电容式薄膜真空规说明书 A1-20240628.pdf
- AHT40温湿度传感器说明书中文版 A1-202406.pdf
- AN1096_APM32F035_HvMOTOR EVAL无感矢量控制方案_V1.1中文.pdf
文档评论(0)