NOIP复习资料(C++).pdf

所需积分/C币:50 2017-08-24 19:15:07 5.71MB PDF
收藏 收藏
举报

NOIP复习资料
前 第十单元介纽了与査找、检索有关的数据结构和算法。你也可以有选择地学习 第|一单元与数学有关。数学对」信息学来说具有举足轻重的地位。标有“!”的应该背卜来,至于其他 内容,如果出题,你应该能把它解决。 第十单元仍与数学有关 第十三单元是图论。学习时要先阅读“小结”,把概念弃清楚。之后要掌握图的实现方法。接下来要掌握 经典图论算法:κ rus l算法、 ijkstra算法、sPFA、 Floyd算法、拓扑排序。 附录F总结了2004年以来NOIP考察的知识点,可以作为选择性学习的参考 在学习算法和数据结构的同时,应该阅读和学习附录A。 如果你还有余力,你应该学习第四单元。第|四单元的内容不是必须要掌握的,但是一旦学会,可以发 挥C++语言的优势,降低编程复杂度。 临近竞赛吋,应该阅读附录B和附录C,以增加经验,减少失误。 面临的问题 工.这是复赛复习资料——需要有人能用心总结、整理初赛的知识,就像这份资料一样 2.潜在的问题还是相当多的,只是时间不够长,问题尚未暴露。 3.部分代码缺少解说,或解说混乱。 A.个人语文水平较差,《资料》也是如此 5.没有对应的asCa1语言版本。 如果有人能为P党写一个 Pasca1版的SrL,他的RP一定会爆增 6.希望有人能用玲IBX整理《资料》,并以自由文档形式发布。 最后,欢迎大家以交流、分享和提高为目的修改、复制、分发本《资料》,同时欢迎大家将《资料》翻译 成 Pasca1语言版供更多orex阅读! 谢谢大家的支持! 葫芦岛市一高中李思洋 2012年8月27日 目录 目录 标题上的符号: 1.!:表示读者应该熟练掌握这些内容,并且在竞赛时能很快地写出来。换句话说就是应该背下来。 2.x:表示内容在NOIP中很少涉及,或者不完全适合NOP的难度。 3.#:表示代码存在未更正的错误,或算法本身存在缺陷。 前言 ..1第五单元分治算法∴ 目录 工 5.1一元三次方程求解..... 51 第一单元C++语言基础 5.2快速幂∴ 5.3排序 1.1程序结构 5.4最长非降子序列 .,53 1.2数据类型... 5.5循环赛日程表问题,......, 1.3运算符 5.6棋盘覆盖.....,..., 54 .4函数. 5.7删除多余括号 5输入和输出! 5.8聪明的质监员 ······· 1.6其他常用操作! 10 5.9模板,........, 58 1.7字符串操作 0小结 8文件操作! 9简单的算法分析和优化 第六单元动态规划 60 工.10代码编辑器.....,,,.,,16 6.1导例:数字三角形 ··章 第二单元基础算法 17 6.2区间问题:石子合并 63 6.3坐标问题.... 65 2.1经典枚举问题. 6.4背包问题..... 2.2火柴棒等式..,, 18 6,5编号问题.... 2.3梵塔问题 19 6.6递归结构问题.... 68 2.4斐波那契数列. 。.19 6.7DAG上的最短路径 71 2.5常见的递推关系 20 6.8树形动态规划 2.6选择客栈 22 6,9状态压缩类问题:过河 74 2.72k进制数 23 6.10 Bi tonic旅行 2.8 Healthy Holsteins 24 77 2.9小结.. 6.11小结 25 第三单元搜索 第七单元背包专题 78 27 7.1部分背包问题.. 3.1N皇后问题 27 3.2走迷宫 7.20/1背包问题! 29 完全背包问题 3.38数码问题.,, 7.4多重背包问题..... 3.4埃及分数 ,,。。,,,,,,.34 7.5二维费用的背包问题 3.5 Mayan游戏 36 3.6预处理和优化.. 分组的背包问题 40 7.7有依赖的背包问题 3.7代码模板 。,,,,,,,,,,41 7.8泛化物品...... 81 3.8搜索题的一些调试技巧 ,43 82 3.9小结 7.9混合背包问题 44 7.10特殊要求. 第四单元贪心算法....... 46 7.11背包问题的搜索解法 83 4.1装载问题 46 7.12子集和问题.......,,...84 4.2区间问题.. 46第八单元排序算法 85 4.3删数问题∴...... 47 8.1常用排序算法. 4.4工序问题.. 47 8.2简单排序算法... 87 4.5种树问题. 47 8.3线性时间排序 4.6马的哈密尔顿链 .47 8.4使用二叉树的排序算法为 .89 4.7三值的排序 ....49 8.5小结... 90 A.8田忌赛马. 50 4.9小结 ,,,.50 第九单元基本数据结构 目录 9.1线性表(顺序结构) 91 14.6示例:合井果子.., ..175 9.2线性表(链式结构) 附录A思想和技巧 9.3栈 93 9.4队列.. A.1时间/空间权衡.. ·;······· 177 94 9.5二叉树 177 95 A.2试验、猜想及归纳 9.6并查集! 99 A.3模型化 177 9.7小结. 102 A.4随机化大 A.5动态化静态 第十单元查找与检索. 104 A.6前序和! 10.1顺序查找 .,..104 A.7状态压缩 180 0.2二分查找 104 Δ,8抽样测试法*∴.,, 182 10.3查找第k小元素!.105 A.9离散化大∴. 183 10.4二叉排序树 .,,,,.106 A. 10 Flood Fill ,,,.184 10.5堆和优先队列 …108附录B调试, 185 10.6哈夫曼( Huf man)树 110 B.1常见错误类型 .···.··.. 185 10.7哈希(Hash)表..,,,,,111 B.2调试过程. 第十一单元数学基础 ,116 B 调试功能 185 11.1组合数学,.....,,,,,,,116 B.4符号DEBG的应用 186 11.2组合数的计算! ,.117 B.5代码审查表 n,186 11.3排列和组合的产生(无重集元素)!117 B.6故障检查表 .187 11.∠排列和组合的产生(有重集元素).120 命令行和批处理*..,,,188 11.5秦九韶算法 122附录C竞赛经验和教训.192 11.6进制转换(正整数)..., 123 1.7高精度算法(压位存储)!....123 C.1赛前两星期 192 192 11.8快速幂! C.2赛前30分钟..., ,,,,,,128 C.3解题表 ....193 11.9表达式求值 129 11.10解线性方程组大, C.4测试数据. 。,,,,。,,,,。,,,。195 133 C.5交卷前5分钟.............196 第十二单元数论算法 135 C.6避免偶然错误 196 12.1同余的性质! 135 C.7骗分 197 12.2最大公约数、最小公倍数!…135附录D学习建议 198 工2.3解不定方程ax十by=c!*.....135 198 12.4同余问题大 D.1学习方法 136 12.5素数和素数表...,,,..,,,136 D.2学习能力. ,,.198 12.6分解质因数.... D.3关于清北学堂...........198 137 第十三单元图与图论算法 附录F竞赛简介 139 13.1图的实现 E.1从NOIP到IOI 139 13.2图的遍历 E.2NOIP简介.................199 。,,,。,,.141 13.3连通性问题.. 常用语 。,,,,201 ...142 E.4第一次参加复赛 202 13.4欧拉回路[邻接矩阵]......146 13.5最小生成树(MsT) 147 附录 F NOIP复赛知识点分布 。204 13.6单源最短路问题(sP问题)…148附录G资料推荐 205 13.7每两点间最短路问题(APSP问题)!152 书籍 13.8拓扑排序. 20 ..152 G.2网站. ,,,。,,,205 3.9关键路径∴,.,,,,. 155 10二分图初步 157 参考文献 206 1小结 160计算机专业是朝阳还是夕阳? 207 第十四单元SL简介 164杜子德在 CCE NOI2012开幕式上的讲话209 14.1STL概述 …164多数奥赛金牌得主为何难成大器 210 14.2常用容器 164 14.3容器适配器. l70 14.4常用算法......171 14.5迭代器. 175 第一单元C++语言基础 第一单元C++语言基础 1.1程序结构 (1)程序框架 ·注释:注释有两种,一种是“//”,另一种是“/*…*/”。“//”必须单独放置一行,或代码所在行 的后面;而“/”、“*/”成对存在,可以插入到代码的任意位置。 引用头文件:在代码开头写“#inc_ude<头文件名>”。如果想引用自己的头文件,需要把尖括号(表 示只从系统目录搜索头文件)换成双引号(表示先从cpp所在文件夹搜索,然后再到系统文件夹报索) 命名空间:很多C++的东西都要引用sa命名空间,所以代码中会有“ using namespace std main():所有程序都要从main()开始 在所有的算法竞赛中,main()的返回值必须是0,否则视为程序异常结束,得分为0分。 语句和语句块 工.语句:一般情况下,一条语句要用一个分号“;”结東。为了美观和可读性,可以把一条语句扩展成 几行,也可以把多个语句写到同一行上 2.语句块:用“(”和“}”包围的代码是语句块。无论里面有多少代码,在原则上,语句块所在的整体 都视为·条语句 (2)选择结构 1.if语句:if表示判断。如果条件为真,就执行接在if后的语句(语句块),否则执行e1se后的语句(语 句块)。如果没有else,就直接跳过。if有以下几种格式: if(条件) //如果条件成立,就执行if后面的语句或语句块 语句或语句块 if(条件) //如果条件成立,就执行i后面的A,否则执行B 语句或语句块 else 语句或语句块B if(条件1) //实际上,这是立f语句内的f语句,即i的嵌套。所以e1se和if中间要有空格 语句或语句块A clsc if(条件2) 语句或语句块B else 语句或语句块N 2. switch语句: switch表小选择。它根据条件的不同取值来执行不冋的语句。格式如下: switch(表达式) casc值1: 代码段A break case值2 代码段B break 第一单元C++语言基础 default 代码段N break 如果表达式的值是值1,就执行代码段A;如果表达式的值是值2,就执行代码段B……否则执行代码段N。 注意: de fault一部分可以省略。 如果不使用 break,那么紧随其后的αas◎部分代码也会被执行,直到遇到。reaκ或 switch语句 结束为止 switch结尾要有一个分号。 、 switch都可以嵌套使用。 【问题描述】输入一个日期,判跡它所在年份是否为闰年,并输出所在月份的天数。闰年的判断方法:四年一 闰,百年不闰,四百年又闰。 int year, month, day; bool b=false cin>>year>>month>>dayi /判断是否为闰年 if(n400==0) b=true; e1seif(n3_00!=0&&n84==0) b=truc if (b) ccut<<y<<"是闰年。"<<endl; else cct<<y<<"不是闰年。"<<end; //判断所在月份的天数 switch (month) casc 1: case 3: casc 5: case 7: case 8: casc 10: casc 12 ccut<<"这个月有31大。"<<endl; break case 4: case 6: case 9: case ll ccut<<"这个月有30天。"<<endl; break case 2: ccut<<"这个月有"<<(?29:28)<<"天。"<<endl breaki }; (3)循环结构 1. While语句:如果条件成立,就继续循环,直到条件不成立为止。格式如下: While(条件) 循环体(语句或语句块) 第一单元C++语言基础 2.do… while语句:如果条件成立,就继续循环,直到条件不成立为止。它与 While的最大区别在于,do… while循环中的语句会被执行至少一次,而 while中的语句可能一次都没有被执行。格式如下 循环体 while(条件); /注意分号 4.fαr语句:for分四部分,有初始条件、继续循环的条件、状态转移的条件和循环体。格式如下: for(初始条件;继续循环的条件;状态转移的条件) 循环体 转换成 While循坏,即: 初始条件 while(继续循环的条件 循环体 状态转移 fcI后三个条件不是必需的,可以省略不写,但分号必须保留。 5.在循环语句內部使用¤reaκ,可以跳岀循环;使用coη tinue,可以忽略它后面的代码,上进入下一轮 循环。 注意,这两个语句只对它所在的一层循坏有效 6.写for循环时,一定要注意: 不要把计数器的字母打错,尤其是在复制/粘贴一段代码的时候 根据算法要明确不等号是 “>”,还是 逆序循环时,不要把自减“--”写成自增“++”! 【问题描述】输入n,输出n!(n!=1×2×3×4X……×n)。结果保证小于1ong1ong的范。当输入值 为负数时结束程序 int n: longlong r=l; cin>>n while (n>-1) =1F for (int i=l; i<=n; 1++) i cout<<n<<! -w<<r<<endl cin>>n (4)goto语句 gto语句用于无条件跳转。要想跳转,首先要定义标签(在代码开头的一段标识符,后面紧跟冒号), 然后才能qoto那个标签。 很多教程不提倡使用无条件跳转,因为它破坏了稈序结构,还容易给代码阅读者带来麻烦。不过,这不代 表goto没有使用价值。got。的一个用途是珧出多层循环: for (int 1=0; 1<9; 1++) fcr (int 3=0: 3<9;3++) 第一单元C++语言基础 for ( int k-0; k<9; k++) if(满足某种条件) goto exited; exited (5)c与c++的区别 C++语言是以¢语言为基础开发出来的,C语言的大多数内容保留了下来。在信息学竞赛领域,很多情 况下C和C++可以互相转化,甚至不用对代码进行任何修改。 下面是信息学竞赛领域中C和C++的重要区别: C++支持用流输入输出,而C只能用 scanf和 printf再见了,号d! C++非常支持血向对象编程,而C已经“out”了 《资料》中的“高精度算法”就只能用C++完成,因为在sruc七内定义了成员函数。 +可以用更强大的 string类处理字符串,而不必担心发生某些低级错淏。 C++有强人的STL,而C没有(有一个小小的qsor和 bsearch算是补偿了)。 STL是很多人从C转到C++的重要原因 C的头文件名仍然可以用在C++中,不过可能会收到警报一一应该去掉“.h”,前面再加一个“c” 如< stdio.h>应该改成< cstdio>。 C程序运行速度稍优于C++。不过也没快多少。 总之,C能做的一切事情,C++也能做;C++能做的一切事情,℃不一定能做。 1.2数据类型 (1)基本数据类型 名称 占用空间别名 数据范围 nt signed, signed int, 2,147,483,648~2,147,483;647 long, long int unsigned int 4 unsigned, unsigned 0~4,294,967,295 long, unsigned long int char char -128127 unsigned char unsigned char 0~255 short short int -32,768~32,767 signed short int unsigned short unsigned short int 0≈65,535 longlong signed long long 9,223,372C36,854,775,808 9,223,372,036,854,775,807 unsigned long long 8 0~18;446,744,073,709,551,615 bool ue或alse har 128~127 signed char 128--127 一般都使用有符号整数,除非范围不够大,或者你确定你的减法运算不会岀现ν小数减大〃。 ≌一般来说,使用int、1cng1ng更保险·些,除非内存不够用 ③不要使用“int64”!它是 Visua1C++特有的关键字。 侵如a是1ong1ong类型,把超过23的值赋给它时要使用字面值L(UL):a=123456789012345LL。 第一单元C++语言基础 unsigned char 0~255 float 3.4E+/-38(7位有效数字) doub I l ong double 7E+/-308(15位有效数字) (2)变量与常量 1.定义变量:“变量类型标识符”,如“inti;”定义了一个名字为i的整型变量。 注意,此时主并未初始化,所以主的值是不确定的。 2.定义常量:“ const变量类型标识符-初始值”,如: const int N-90; 3.合法的标识符: 标识符不能和关键字(在ID中会变色的词语)相同。 标识符只能包括字母、数字和下划线“”,并且开头只能是字或下划线。 标识符必须先定义后使用。 在同一作用域内,标识符不能重复定义(即使在不同作用城内乜不应重复,否则容易产生歧义)。 C++区分大小写。所以和a是两个不同的标识符。 (3)数组 1.定义一个一维数组:inta[10 这个数组一共10个元素,下标分别为 问某个元素时,直接用a加方括号,如a[5] 2.定义一个二维数组:intb[5][3]; 这个数组一共5×3=15个元素,分别是b[C][0]、b[0][1]、b0][2]、[1][0]…b[4][2] 访问某个元素时要用两个方括号,如b[2][1]。 多维数组的定义和使用方法与此类似 3.数组名和元素的寻址:以上面的a、o为例 数组名是一个指针,指向整个数组第一个元素所在的地址。如a就是6a[0]、b就是&b[0][0]。 多维数组的本质是数组的数组,所以b[0]实际上是b[0[C]、b[0][1]…的数组名,b[0]就是 b[0][C] 在内存中,数组中每个元素都是紧挨着的,所以可以直接进行指针的运算。如a+3就是&a[3],x*(D+1) 就是b[1][C],(大(b+3)+2)就是b[3][2]。 在竞赛中要尽可能回避这些功能。 4.字符串: 字符串实际上是chax的数组 字符串最后一位必须是∵\0,否则会在进行输出、使用字符串函数时发生意外。 数组,包括字符串,不可以整体地赋值和比较。如果需要,应使用π ency和τmemcπ(字符串是strp 和 strcmp)。 5.C++中数组的下标只能从0开始(当然可以闲置不用),并且inta[10]中a的最后一个元素是a[9], 不是a[10]! 6.C++不检査数组下标是否越界!如果下标越界,程序很有可能会崩溃! (4)指针 1.取地址运算符和取值运算符: 取地址运算符“&”:返回变量所在的地址。一般用于变量。(而数组名本身就是指针,无需“”) 取值运算符“★”:返回地址对应的值,或用于改变指针所指内存空间的值。只能用于指针。 2.指针的意义:保存力一个变量的内存地址。 3.定义指针:int*p;

...展开详情
试读 127P NOIP复习资料(C++).pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
  • GitHub

    绑定GitHub第三方账户获取
关注 私信 TA的资源
上传资源赚积分or赚钱
最新推荐
NOIP复习资料(C++).pdf 50积分/C币 立即下载
1/127
NOIP复习资料(C++).pdf第1页
NOIP复习资料(C++).pdf第2页
NOIP复习资料(C++).pdf第3页
NOIP复习资料(C++).pdf第4页
NOIP复习资料(C++).pdf第5页
NOIP复习资料(C++).pdf第6页
NOIP复习资料(C++).pdf第7页
NOIP复习资料(C++).pdf第8页
NOIP复习资料(C++).pdf第9页
NOIP复习资料(C++).pdf第10页
NOIP复习资料(C++).pdf第11页
NOIP复习资料(C++).pdf第12页
NOIP复习资料(C++).pdf第13页
NOIP复习资料(C++).pdf第14页
NOIP复习资料(C++).pdf第15页
NOIP复习资料(C++).pdf第16页
NOIP复习资料(C++).pdf第17页
NOIP复习资料(C++).pdf第18页
NOIP复习资料(C++).pdf第19页
NOIP复习资料(C++).pdf第20页

试读结束, 可继续阅读

50积分/C币 立即下载 >