初赛

一只萌新 · 2019-10-10 15:52:27 · 个人记录

历年NOIP提高组初赛选择解析（至2006年）

自整理 初赛

2019CSP初赛基础知识整理

CSP-S 2019 初赛知识点整理

初赛的考点笔记

史上最全NOIP初赛知识点

NOIP初赛知识点集锦

NOIP初赛知识点(大全)

NOIP初赛知识点汇总

• 初赛数学题错题总结

当小球遇上盒子

卡特兰数详讲

卡特兰数 — 计数的映射方法的伟大胜利

2013noip初赛提高组试题解析 详细

NOIP 提高组 初赛 四、阅读程序写结果 习题集（三）NOIP2004-NOIP2005

进制转换

前缀、中缀、后缀表达式转换详解

栈:前缀表达式转中缀表达式

• 图像文件的字节数=图像分辨率*颜色深度/8

• 断电之后仍能保存数据的有 硬盘,ROM

  断电之后不能保存数据的有 寄存器,显存,内存,高速缓存

• NOIP 不推荐使用： Visual C++,Turbo C,Turbo Pascal

• H(Hexadecimal)——16进制 D(Decimal)——10进制 O(Octonary)——8进制 B(Binary)——2进制

第一届竞赛时间

全国青少年信息学奥林匹克竞赛（NOI） 1984

全国青少年信息学奥林匹克联赛(NOIP)  1995

国际信息学奥林匹克竞赛(IOI) 1989

亚太地区信息学奥林匹克竞赛（APIO）2007

人物

冯·诺依曼(Neumann) 
"计算机之父",ENIAC和EDVAC的技术顾问
存储程序原理:将程序像数据一样存储到计算机内部存储器中的一种设计原理

戈登·摩尔(Gordon Moore) 英特尔公司创始人之一,摩尔定律

查尔斯·巴比奇(Babbage)  发明了世界上第一台机械计算机器——差分机

克劳德·香农(Shannon)  信息论之父、发明了术语比特 

姚期智 2000年图灵奖 华裔

阿达·洛芙莱斯(Ada Lovelace) “第一位给计算机写程序的人”

操作系统

操作系统是一种系统软件，直接控制和管理计算机系统的所有软、硬件资源，以方便用户充分而有效地利用这些资源的程序集合

常用的计算机操作系统有：
1.Windows系列操作系统（咱们最常用的）
由微软公司生产；
2.Unix类操作系统
如SOLARIS,BSD系列（FREEBSD，openbsd，netbsd，pcbsd）；
3.Linux类操作系统
如UBUNTU，suse linux，fedora，等
4.Mac操作系统
由苹果公司生产（Darwin），一般安装于MAC电脑。
其他: Symbian(塞班公司为手机而设计) 

Linux下的文件不需要扩展名。一切皆文件

计算机相关

主机:CPU和内储存器

U盘是闪存盘的一种
寄存器是CPU的有限存贮容量的高速存贮部件，它们可用来暂存指令、数据和地址
CPU中 高速缓冲存储器 提高系统整体的执行效率

CPU=控制器+运算器+寄存器
CPU 的主要任务是执行数据运算和程序控制

控制器: 控制机器各个部件协调工作
存储器: 存储各种控制信息 

ROM是只读存储器（Read-Only Memory），只能读出事先所存数据的固态半导体存储器，一旦储存资料就无法再将之改变或删除 
随机存取存储器（英语：Random Access Memory，缩写：RAM） -> 内存、主存

BIOS
Basic Input Output System 基本输入输出系统
保存着计算机最重要的基本输入输出的程序、系统设置信息、开机后自检程序和系统自启动程序
为计算机提供最底层的、最直接的硬件设置和控制

CPU、存储器、I/O设备是通过 总线 连接起来的。

网络相关

为计算机网络中进行数据交换而建立的规则、标准或约定的集合称为网络协议。
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类问题

1、P类问题：如果一个问题能找到一个在多项式时间内解决它的算法，那么这个问题就是P问题。

2、NP类问题：注意：NP问题不是非P类问题，而是在多项式时间内验证一个解的问题。或者，我们可以将其理解为在多项式时间内猜出一个解的问题。

3、NPC类问题：定义如下：如果一个问题是NP问题，而且所有的NP问题都可以约化到它。那么它就是NPC类问题。再来介绍一下关于约化的定义：如果一个问题A可以约化为问题B，含义就是这个问题A可以用问题B的解法来解决。

P是NP,NP不一定是P

语言

C是一种面向过程的高级计算机语言
C++  JAVA C#  Pascal 面向对象 
汇编语言 直接对硬盘 

面向过程程序设计通常采用自顶向下设计方法进行设计

Java、Python、Matlab 解释型语言，不需要编译
C、C++、Pascal 编译型语言 编译的时候直接编译成机器可以执行或调用的程序，如exe、dll或ocx等类型 

第一个高级语言是fortran，Ada是美国军方发明的语言，取名Ada是为了纪念第一个女程序员
第一个支持面向对象的语言是simula67

排序相关

稳定排序:两个相等的数不会交换位置

堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法，
基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法

基数排序 基于桶排序 

希尔排序(缩小增量排序)

数学题汇总

排列组合,卡特兰数

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)方程 ab = (a or b) (a and b)，在 a, b 都取 [0, 31] 中的整数时，共有_____组解。（*表示乘法；or 表示按位或运算；and 表示按位与运算）

13. (2012pj 22)在NOI期间，主办单位为了欢迎来自各国的选手，举行了盛大的晚宴。在第十八桌，有5名大陆选手和5名港澳选手共同进膳。为了增进交流，他们决定相隔就坐，即每个大陆选手左右旁都是港澳选手，每个港澳选手左右旁都是大陆选手。那么，这一桌一共有___种不同的就坐方案。

    注：如果在两个方案中，每个选手左右相邻的选手相同，则视为同一种方案。

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,重复的方案)

时间复杂度计算（数列）

时空复杂度计算

主定理

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)

   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

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

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

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)

   #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)

   #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 输出：_____

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的个数