初赛

[历年NOIP提高组初赛选择解析（至2006年）](https://blog.csdn.net/qq_42037034/article/details/82973488) [自整理 初赛](https://www.luogu.org/paste/8b1f7oy0) [2019CSP初赛基础知识整理](https://www.cnblogs.com/zhengchang/p/chusai.html) [CSP-S 2019 初赛知识点整理](https://www.luogu.org/blog/Setsugesuka/csp-s-2019-chu-sai-zhi-shi-dian-zheng-li) [初赛的考点笔记](https://www.luogu.org/blog/for1-666/chu-sai-di-kao-dian-bi-ji) [史上最全NOIP初赛知识点](https://www.cnblogs.com/fusiwei/p/11559403.html) [NOIP初赛知识点集锦](https://blog.csdn.net/qq_42369449/article/details/82928382) [NOIP初赛知识点(大全)](https://wenku.baidu.com/view/3857d87ec77da26924c5b057.html) [NOIP初赛知识点汇总](https://blog.csdn.net/holyromanempire/article/details/52870113) * [初赛数学题错题总结](https://www.cnblogs.com/logic-yzf/p/7642963.html) [当小球遇上盒子](https://www.luogu.org/blog/chengni5673/dang-xiao-qiu-yu-shang-he-zi) [卡特兰数详讲](https://blog.csdn.net/wookaikaiko/article/details/81105031) [卡特兰数 — 计数的映射方法的伟大胜利](http://lanqi.org/skills/10939/) [2013noip初赛提高组试题解析 详细](http://www.docin.com/p-963170477.html) [NOIP 提高组 初赛 四、阅读程序写结果 习题集（三）NOIP2004-NOIP2005](https://blog.csdn.net/zhuofeilong/article/details/75262325) [进制转换](http://xinzhi.wenda.so.com/a/1537180588200142) [前缀、中缀、后缀表达式转换详解](https://blog.csdn.net/walkerkalr/article/details/22798365) [栈:前缀表达式转中缀表达式](https://blog.csdn.net/sunshare77/article/details/80668634) --- + 图像文件的字节数=图像分辨率*颜色深度/8 + >断电之后仍能保存数据的有 硬盘,ROM >断电之后不能保存数据的有 寄存器,显存,内存,高速缓存 + NOIP 不推荐使用： Visual C++,Turbo C,Turbo Pascal + >H(Hexadecimal)——16进制 >D(Decimal)——10进制 >O(Octonary)——8进制 >B(Binary)——2进制 --- ### 第一届竞赛时间 ```cpp 全国青少年信息学奥林匹克竞赛（NOI） 1984 全国青少年信息学奥林匹克联赛(NOIP) 1995 国际信息学奥林匹克竞赛(IOI) 1989 亚太地区信息学奥林匹克竞赛（APIO）2007 ``` --- ### 人物 ```cpp 冯·诺依曼(Neumann) "计算机之父",ENIAC和EDVAC的技术顾问 存储程序原理:将程序像数据一样存储到计算机内部存储器中的一种设计原理 戈登·摩尔(Gordon Moore) 英特尔公司创始人之一,摩尔定律 查尔斯·巴比奇(Babbage) 发明了世界上第一台机械计算机器——差分机 克劳德·香农(Shannon) 信息论之父、发明了术语比特 姚期智 2000年图灵奖 华裔 阿达·洛芙莱斯(Ada Lovelace) “第一位给计算机写程序的人” ``` --- ### 操作系统 ```cpp 操作系统是一种系统软件，直接控制和管理计算机系统的所有软、硬件资源，以方便用户充分而有效地利用这些资源的程序集合 常用的计算机操作系统有： 1.Windows系列操作系统（咱们最常用的） 由微软公司生产； 2.Unix类操作系统 如SOLARIS,BSD系列（FREEBSD，openbsd，netbsd，pcbsd）； 3.Linux类操作系统 如UBUNTU，suse linux，fedora，等 4.Mac操作系统 由苹果公司生产（Darwin），一般安装于MAC电脑。 其他: Symbian(塞班公司为手机而设计) Linux下的文件不需要扩展名。一切皆文件 ``` --- ### 计算机相关 ```cpp 主机:CPU和内储存器 U盘是闪存盘的一种 寄存器是CPU的有限存贮容量的高速存贮部件，它们可用来暂存指令、数据和地址 CPU中 高速缓冲存储器 提高系统整体的执行效率 CPU=控制器+运算器+寄存器 CPU 的主要任务是执行数据运算和程序控制 控制器: 控制机器各个部件协调工作 存储器: 存储各种控制信息 ROM是只读存储器（Read-Only Memory），只能读出事先所存数据的固态半导体存储器，一旦储存资料就无法再将之改变或删除 随机存取存储器（英语：Random Access Memory，缩写：RAM） -> 内存、主存 BIOS Basic Input Output System 基本输入输出系统 保存着计算机最重要的基本输入输出的程序、系统设置信息、开机后自检程序和系统自启动程序 为计算机提供最底层的、最直接的硬件设置和控制 CPU、存储器、I/O设备是通过 总线 连接起来的。 ``` --- ### 网络相关 ```cpp 为计算机网络中进行数据交换而建立的规则、标准或约定的集合称为网络协议。 HTTP、TCP/IP、FTP是网络协议。 TCP属于传输层协议 IP 属于网络层协议 TCP/IP: 数据链路层：ARP,RARP 网络层： IP,ICMP,IGMP 传输层：TCP ,UDP,UGP 应用层：Telnet,FTP,SMTP,SNMP. 属于电子邮件收发的协议 SMTP,IMAP,POP3 SMTP-发送 IMAP,POP3-接收 IP地址 先判断它是不是由4段数字用点号“.”分隔开，再判断每段数字的十进制是不是在0-255之间，满足条件就是正确的IP地址 IP地址是一个32位的二进制数，通常被分割为4个“8位二进制数”（也就是4个字节） 每一个字节都为0的地址（“0.0.0.0”）对应于当前主机； IP地址中的每一个字节都为1的IP地址（“255.255.255.255”）是当前子网的广播地址 IP地址中不能以十进制“127”作为开头 IPv4 协议使用 32 位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被 使用 128 位地址的 IPv6 协议所取代 ``` --- ### P类/NP类/NPC类问题 ```cpp 1、P类问题：如果一个问题能找到一个在多项式时间内解决它的算法，那么这个问题就是P问题。 2、NP类问题：注意：NP问题不是非P类问题，而是在多项式时间内验证一个解的问题。或者，我们可以将其理解为在多项式时间内猜出一个解的问题。 3、NPC类问题：定义如下：如果一个问题是NP问题，而且所有的NP问题都可以约化到它。那么它就是NPC类问题。再来介绍一下关于约化的定义：如果一个问题A可以约化为问题B，含义就是这个问题A可以用问题B的解法来解决。 P是NP,NP不一定是P ``` --- ### 语言 ```cpp C是一种面向过程的高级计算机语言 C++ JAVA C# Pascal 面向对象 汇编语言 直接对硬盘 面向过程程序设计通常采用自顶向下设计方法进行设计 Java、Python、Matlab 解释型语言，不需要编译 C、C++、Pascal 编译型语言 编译的时候直接编译成机器可以执行或调用的程序，如exe、dll或ocx等类型 第一个高级语言是fortran，Ada是美国军方发明的语言，取名Ada是为了纪念第一个女程序员 第一个支持面向对象的语言是simula67 ``` --- ### 排序相关 ```cpp 稳定排序:两个相等的数不会交换位置 堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法， 基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法 基数排序 基于桶排序 ``` [希尔排序(缩小增量排序)](https://www.cnblogs.com/chengxiao/p/6104371.html) --- ## 数学题汇总 ### 排列组合,卡特兰数 1. (2014tg 21)数字1,1,2,4,8,8所组成的不同的四位数的个数是_____. 2. (2015tg 22)结点数为 5 的不同形态的二叉树一共有___种.（结点数为 2 的二叉树一共有 2 种：一种是根结点和左儿子，另一种是根结点和右儿子。） 3. (2008tg 22)书架上有21本书，编号从1到21，从其中选4本，其中每两本的编号都不相邻的选法一共有______种. 4. (2009tg 21)拓扑排序是指将有向无环图G中的所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前，这样的线性序列成为拓扑序列。如下的有向无环图，对其顶点做拓扑排序，则所有可能的拓扑序列的个数为______  5. (2007tg 21)给定n 个有标号的球，标号依次为1，2，…，n。将这n 个球放入r 个相同的盒子里，不允许 有空盒，其不同放置方法的总数记为S(n,r)。例如，S(4,2)=7，这7 种不同的放置方法依次为 {(1),(234)}, {(2),(134)}, {(3),(124)}, {(4),(123)}, {(12),(34)}, {(13),(24)}, {(14),(23)}。当n=7,r=4 时，S(7,4)= _____________。 6. (2013pj 21)7 个同学围坐一圈，要选2 个不相邻的作为代表，有_________种不同的选法。 7. (2014pj 21)把M个同样的球放到N个同样的袋子里，允许有的袋子空着不放，问共有多少种不同的放置方法？(用K表示)。 例如，M＝7，N＝3时，K＝8；在这里认为和是同一种放置方法。 问：M＝8，N＝5时，K＝___ 。 8. (2010pj 22)队列快照是指在某一时刻队列中的元素组成的有序序列。例如，当元素1、2、3入队，元素1出队后，此刻的队列快照是"2 3"。当元素2、3也出队后，队列快照是""，即为空。现有3个正整数元素依次入队、出队。已知它们的和为8，则共有_________种可能的不同的队列快照（不同队列的相同快照只计一次）。例如，"5 1"、"4 2 2"、""都是可能的队列快照；而"7"不是可能的队列快照，因为剩下的2个正整数的和不可能是1。 9. (2004tg 2)由3个a，5个b和2个c构成的所有字符串中，包含子串“abc”的共有（ ）个。 > A. 40320 B. 39600 C. 840 D. 780 E. 60 10. (2017tg 8)由四个不同的点构成的简单无向连通图的个数是（ ）。 A. 32 B. 35 C. 38 D. 41 11. (2001tg 22)平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成____个不同四边形 12. (2018tg 17)方程 a*b = (a or b) * (a and b)，在 a, b 都取 [0, 31] 中的整数时，共有_____组解。（*表示乘法；or 表示按位或运算；and 表示按位与运算） 13. (2012pj 22)在NOI期间，主办单位为了欢迎来自各国的选手，举行了盛大的晚宴。在第十八桌，有5名大陆选手和5名港澳选手共同进膳。为了增进交流，他们决定相隔就坐，即每个大陆选手左右旁都是港澳选手，每个港澳选手左右旁都是大陆选手。那么，这一桌一共有_______种不同的就坐方案。 注：如果在两个方案中，每个选手左右相邻的选手相同，则视为同一种方案。 ```cpp 1.102 (分情况, A(4,4) + 2*C(3,2)*A(2,2)* (C(3,1)+C(3,2)) + (C(3,1)+C(3,2)) ) 2.42 (卡特兰数经典题,n个结点的树的同构数目是卡特兰数的第n项) 3.3060 (反向考虑，17本插入4本不相邻) 4.432 (（c(8,1)+c(8,2)）* c(6,1)*2 ) 5.350 (https://www.zybang.com/question/67df89c725b679eedcfa84345b27d353.html 第二类斯特林数) 6.14 ( C(7,2)-7 ) 7.18 (自然数拆分问题 枚举/递推 https://www.luogu.org/blog/chengni5673/dang-xiao-qiu-yu-shang-he-zi /五边形数) 8.49 (先枚举和为8的三个数,再分情况 1(空集)+6(取一个)+(3+3)*3+(A(3,2)+A(3,3))*2 ) 9.D 1. 捆绑"abc",把1个"abc",2个"a",4个"b",1个"c"排列,"不尽相异元素排列",总方案数8!/(2!*4!)=840 2. 2个"a",4个"b",1个"c"也可以组成"abc",840里有重复情况,比如(abc)abcabbb,abc(abc)abbb 3.2个"abc",1个"a",3个"b",方案数6!/(2!*3!)=60 4.故答案为840-60=780 (两个元素的容斥原理) 10.C (最少3条,最多6条, C(6,3)+C(6,4)+C(6,5)+C(6,6) - 4(三条边时有4种情况不能构成连通图) ) 11.2250 ( C(7,2)*C(6,2)+C(7,2)*C(5,2)+C(5,2)*C*(6,2)+C(7,2)*C(6,1)*C(5,1)+C(7,1)*C(6,2)*C(5,1)+C(7,1)*C(6,1)*C(5,2) ) 12.454 ( 较小值的二进制一定是较大值的二进制的子集,有序数对,减去重复 2∑i=0~5 C(5,i)*2^(5-i) - 32 = 454 ) 13.2880 ( 5!*5!/5 大陆选手和港澳选手的就坐方案,相乘后,再除以5,重复的方案) ``` --- ### 时间复杂度计算（数列） [时空复杂度计算](https://www.luogu.org/blog/Chanis/master) [主定理](https://blog.csdn.net/lanchunhui/article/details/52451362) 1. (2013tg 4)斐波那契数列的定义如下：$F1 = 1, F2 = 1,Fn=Fn-1+Fn-2 (n ≥ 3)$如果用下面的函数计 算斐波那契数列的第 n 项，则其时间复杂度为 （） A. O(1) B. O(n) C. O(n2) D. O(Fn) ```cpp int F(int n) { if (n <= 2) return 1; else return F(n - 1) + F(n - 2); } ``` 2. (2013tg 15)T(n)表示某个算法输入规模为 n 时的运算次数。如果 T(1)为常数，且有递归式 T(n) = 2*T(n / 2) + 2n，那么 T(n) = （ ） A. Θ(n) B. Θ(n log n) C. Θ(n2) D. Θ(n2 log n) 3. (2013tg 22)现有一只青蛙，初始时在 n 号荷叶上。当它某一时刻在 k 号荷叶上时，下一时刻将等概 率地随机跳到 1, 2, …, k 号荷叶之一上，直至跳到 1 号荷叶为止。当 n = 2 时，平均一共 跳 2 次；当 n = 3 时，平均一共跳 2.5 次。则当 n = 5 时，平均一共跳________ 次。 4. (2017tg 6)若某算法的计算时间表示为递推关系式： $T(N) = 2T(N / 2) + N log N$ $T(1) = 1$ 则该算法的时间复杂度为（ ）。 A. $O(N)$ B. $O(NlogN)$ C. $O(Nlog^2N)$ D. $O(N^2)$ 5. (2017tg 10)若 $f[0] = 0, f[1] = 1, f[n + 1] = (f[n] + f[n - 1]) / 2$， 则随着 i 的增大，$f[i]$将接近于( )。 A. $1/2$ B. $2/3$ C. (√5 − 1)/2 D. $1$ ```cpp 1.D (https://www.luogu.org/blog/Chanis/master) 2.B (类似二分) 3. 37/12 ( 递推 https://www.cnblogs.com/zhukaiyuan/p/11610329.html) 4.C 5.B (https://blog.csdn.net/Eirlys_North/article/details/80664747) ``` --- ### 平均次数（期望） 1. (2014tg 7)对长度位n的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为( ). A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/4 2. (2008tg 10)对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（ ）。 A. 35/11 B. 34/11 C. 33/11 D. 32/11 E. 34/10 ```cpp 1.B ( n*(n+1)/2 * (1/n) ) 2.C ( 所有数的二分查找的比较次数之和/个数 ) ``` --- ### 其它 1. (2009tg 22)某个国家的钱币面值有1, 7, 7^2, 7^3共计四种，如果要用现金付清10015元的货物，假设买卖双方各种钱币的数量无限且允许找零，那么交易过程中至少需要流通_______张钱币。 2. (2014tg 12)同时查找2n 个数中的最大值和最小值，最少比较次数为( ). A. 3(n-2)/2 B. 4n-2 C. 3n-2 D. 2n-2 3. (2017tg 4) 2017年10月1日是星期日，1949年10月1日是( )。 A. 星期三 B. 星期日 C. 星期六 D. 星期二 4. (2015tg 14)对图 G 中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图 G 的一个正常 着色。正常着色图 G 所必需的最少颜色数，称为 G 的色数。那么下图的色数是（ ）。 A. 3 B. 4 C. 5 D. 6  5. (2007tg 22)N 个人在操场里围成一圈，将这 N 个人按顺时针方向从1 到N 编号，然后，从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直 到操场只剩下一个人，记这个人的编号为J(N) ，例如，J(5)=3 ，J(10)=5 ，等等。则 J(400)=______________。 （提示：对N=2^m+r进行分析，其中0≤r<2^m） 6. (2010tg 23)记T为一队列，初始时为空，现有n个总和不超过32的正整数依次入列。如果无论这些数具体为何值，都能找到一种出队的方式，使得存在某个时刻队列T中的数之和恰好为9，那么n的最小值是___________。 7. (2010tg 22)无向图G有7个顶点，若不存在由奇数条边构成的简单回路，则它至多有____条边。 8. (2011tg 21)平面图可以在画在平面上，且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至多有6条边，如下图所示。那么，5个顶点的平面图至多有_____条边。  9. (2011tg 22)定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串“BCA”可以将A移到B之前，变字符串“ABC”。如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要________次操作。 10. (2012tg 21)本题中，我们约定布尔表达式只能包含 p, q, r 三个布尔变量，以及“与”（∧）、“或”（∨）、“非”（¬）三种布尔运算。如果无论 p, q, r 如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，(p∨q)∨r 和 p∨(q∨r)等价，p∨¬p 和 q∨¬q 也等价；而 p∨q 和 p∧q 不等价。那么，两两不等价的布尔表达式最多有_________个。 11. (2012tg 22)对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图 1 有 5 个不同的独立集（1 个双点集合、3 个单点集合、1 个空集），图 2 有 14 个不同的独立集。那么，图 3 有_________个不同的独立集。  12. (2011pj 22)定义字符串的基本操作为：删除一个字符＼插入一个字符和将一个字符修改成另外一个字符这三种操作。将字符串Ａ变成字符串Ｂ的最少操作步数，称为字符串Ａ到字符串Ｂ的编辑距离。字符串“ABCDEFG”到字符串“BADECG”的编辑距离为_____。 13. (2015pj 21)重新排列 1234 使得每一个数字都不在原来的位置上，一共有__种排法。 14. (2015pj 22)一棵结点数为 2015 的二叉树最多有___个叶子结点。 15. (2006tg 21)将2006个人分成若干不相交的子集，每个子集至少有3个人，并且： > （1）在每个子集中，没有人认识该子集的所有人。 > （2）同一子集的任何3个人中，至少有2个人互不认识。 > （3）对同一子集中任何2个不相识的人，在该子集中恰好只有1个人认识这两个人。 > 则满足上述条件的子集最多能有___________个？ 16. (2016tg 8)G 是一个非连通简单无向图，共有 28 条边，则该图至少有（ ）个顶点。 A. 10 B. 9 C. 8 D. 7 ```cpp 1.35 (被幂次的显示坑的肯定不止我一个! 答案:贪心 https://zhidao.baidu.com/question/188403632.html ) 2.C ( https://zhidao.baidu.com/question/426499895347085212.html ) 3.C ( https://blog.csdn.net/Eirlys_North/article/details/80664747 ) 4.A (最小环为3,必须要3个颜色) 5.289 (找规律,J(2^m)=1,J(2^m+1)=3,接下来是5,7,9,...) 6.18 (抽屉原理 https://www.zybang.com/question/882aaa8d96794135677dd8c6208297d0.html) 7.12(二分图做法http://www.docin.com/p-501877626.html 自行构造做法http://blog.sina.com.cn/s/blog_62d8450c0100x138.html) 8.9 (平面图 https://wenku.baidu.com/view/8f79d21ce55c3b3567ec102de2bd960590c6d93d.html) 9.4 (最长的正序串为ACEGI，还剩下4个字符) 10.256 (主要是看懂题意,不等价->p,q,r取值不同,或取值相同时结果不同 p,q,r可以取0,1中的任意一个数，总共有2^3=8种情况，每种情况对应一个不同的值，0或1,保证值不等，两两都不等价，至少有2^8种取法) 11.5536 (树形dp https://www.cnblogs.com/logic-yzf/p/7642963.html) 12.3 ( 删除A,将C替换成A,将F替换成C) 13.9 (枚举) 14.1008 (二叉树:叶子节点 = 度为2的节点数+1) 15.401 (图论转化,枚举,发现五边形满足条件 2006/5=401 https://www.zybang.com/question/7d364e02b9acabe93190e3f1ceb44a2d.html) 16.B (非连通图 C(8,2)=28 答案为8+1=9) ``` --- ### 读程序写结果中的数学题 1. (2017tg 26) ```cpp #include <iostream> using namespace std; int main() { int n, m; cin >> n >> m; int x = 1; int y = 1; int dx = 1; int dy = 1; int cnt = 0; while (cnt != 2) { cnt = 0; x = x + dx; y = y + dy; if (x == 1 || x == n) { ++cnt; dx = -dx; } if (y == 1 || y == m) { ++cnt; dy = -dy; } } cout << x << " " << y << endl; return 0; } ``` 输入 1：4 3 输出 1：_________（2 分） 输入 2：2017 1014 输出 2：_________（3 分） 输入 3：987 321 输出 3：_________（3 分） 2. (2012tg 25) ```cpp #include <iostream> using namespace std; const int SIZE = 20; int data[SIZE]; int n, i, h, ans; void merge() { data[h-1] = data[h-1] + data[h]; h--; ans++; } int main() { cin>>n; h = 1; data[h] = 1; ans = 0; for (i = 2; i <= n; i++) { h++; data[h] = 1; while (h > 1 && data[h] == data[h-1]) merge(); } cout<<ans<<endl; } ``` （1） 输入：8 输出：_________ （2） 输入：2012 输出：_________ ```cpp 1. 输出1: 1 3 输出2: 2017 1 输出3: 1 321 https://www.cnblogs.com/nnszoi/p/7685998.html 求出输入的两个数(两个数都-1)的最小公倍数 然后用最小公倍数分别除以两个输入的数 如果结果是单数，则输出的是输入的这个数本身 如果结果是偶数，则输出的是1 2.(1)7 (2)2004 数n中二进制下1的个数,答案为n-1的个数 ```