NOIP 初赛知识点整理第2版。

温馨提示：不保证对，但也不保证错。

一、NOI 史

NOI 于 \(1984\) 年首次举行。
NOIP 于 \(1995\) 年首次举行。
NOIP 于 \(2019\) 年暂停。
CSP 于 \(2019\) 年首次举行。
NOIP 于 \(2020\) 年恢复。

二、计算机发展史

\(1944\) 年，美籍匈牙利数学家冯·诺依曼提出计算机基本结构和工作方式的设想，为计算机的诞生和发展提供了理论基础。
\(1946\) 年，世界上第一台电子计算机 ENIAC 在美国宾夕法尼亚大学诞生。

代别	年代	电子元件
第一代	\(1946-1958\)	电子管
第二代	\(1959-1964\)	晶体管
第三代	\(1965-1970\)	集成电路
第四代	\(1970-\text{今}\)	大规模、超大规模集成电路

三、计算机著名人物及奖项

艾伦·麦席森·图灵(Alan Mathison Turing，英国人)

被称为计算机科学之父，人工智能之父。图灵对于人工智能的发展有诸多贡献，例如图灵曾写过一篇名为《计算机器和智能》的论文，提问“机器会思考吗？”（Can Machines Think?），作为一种用于判定机器是否具有智能的测试方法，即图灵测试。至今，每年都有试验的比赛。此外，图灵提出的著名的图灵机模型为现代计算机的逻辑工作方式奠定了基础。

约翰·冯·诺依曼(John von Neumann，美籍匈牙利人)

被后人称为“现代计算机之父”、“博弈论之父”。1945年6月，冯·诺伊曼与戈德斯坦、勃克斯等人，联名发表了一篇长达101页纸的报告，即计算机史上著名的“101页报告”，是现代计算机科学发展里程碑式的文献。明确规定用二进制替代十进制运算，并将计算机分成5大组件，这一卓越的思想为电子计算机的逻辑结构设计奠定了基础，已成为计算机设计的基本原则。1951年，EDVAC计算机宣告完成。

图灵奖(ACM A.M Turing Award)

美国计算机协会（ACM）于1966年设立的奖项，专门奖励对计算机事业作出重要贡献的个人。其名称取自世界计算机科学的先驱、英国科学家、曼彻斯特大学教授艾伦·图灵（A.M. Turing），这个奖设立目的之一是纪念这位现代计算机科学的奠基者。获奖者必须是在计算机领域具有持久而重大的先进性的技术贡献。大多数获奖者是计算机科学家。图灵奖是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。

四、Linux 基本操作

目录切换命令 `cd`

cd xxx/ 切换到该目录下 xxx 目录
cd …/ 切换到上一层目录
cd / 切换到系统根目录
cd ~ 切换到用户主目录

目录操作命令

mkdir xxx 新建名为 xxx 的文件夹（可能需要 sudo）
ls xxx 显示 xxx 下所有文件和目录
ls -a 显示所有文件和目录（包括隐藏文件）
ls -l 显示所有文件和目录（包括详细信息）
find xxx -name 'yyy' 寻找 xxx 目录下名为 yyy 相关的文件
mv xxx yyy 重命名（目录文件均可）
cp -r xxx yyy 把 xxx 拷贝到 yyy 位置
rm [-rf] xxx 删除 xxx

文件操作命令

touch xxx 新建 xxx 文件
cat xxx 显示 xxx 文件
vim xxx 修改 xxx 文件

五、计算机基础架构

现代计算机基本为冯·诺依曼架构，即硬件部分分为五部分：运算器、控制器、存储器、输入设备、输出设备。

运算器

计算机硬件中的运算器主要功能是对数据和信息进行运算和加工。运算器包括以下几个部分：通用寄存器、状态寄存器、累加器和关键的算术逻辑单元。运算器可以进行算术计算（加减乘除）和逻辑运算（与或非）。

控制器

控制器和运算器共同组成了中央处理器\((CPU)\)。控制器可以看作计算机的大脑和指挥中心，它通过整合分析相关的数据和信息，可以让计算机的各个组成部分有序地完成指令。

存储器

顾名思义，存储器就是计算机的记忆系统，是计算机系统中的记事本。而和记事本不同的是，存储器不仅可以保存信息，还能接受计算机系统内不同的信息并对保存的信息进行读取。存储器由主存和辅存组成，主存就是通常所说的内存，分为 \(RAM\) 和 \(ROM\) 两个部分。辅存即外存，但是计算机在处理外存的信息时，必须首先经过内外存之间的信息交换才能够进行。

六、计算机硬件系统

\(CPU\)(中央处理器)

由运算器、控制器和一些寄存器组成；作为计算机系统的运算和控制核心，是信息处理、程序运行的最终执行单元。 \(CPU\) 的主要性能指标是主频和字长。

主频

主频是指计算机 \(CPU\) 的时钟频率，它在很大程度上决定了计算机的运算速度。一般时钟频率越高，运算速度就越快。主频的单位一般是 \(MHz\)（兆赫）或 \(GHz\)（吉赫）。

字长

字长是指一台计算机所能处理的二进制代码的位数。计算机的字长直接影响到它的精度、功能和速度。字长愈长，能表示的数值范围就越大，计算出的结果的有效位数也就越多；字长愈长，能表示的信息就越多，机器的功能就更强。常用的有 \(32\) 位、\(64\) 位字长。

存储器

存储器的主要功能是用来保存各类程序的数据信息。存储器可分为主存储器和辅助存储器两类。

主存储器

主存储器（也称为内存储器），属于主机的一部分。用于存放系统当前正在执行的数据和程序，属于临时存储器。

它和 \(CPU\) 一起构成了计算机的主机部分，它存储的信息可以被 \(CPU\) 直接访问。内存由半导体存储器组成，存取速度较快，但一般容量较小。

内存储器通常可以分为随机存储器 \(RAM\)、只读存储器 \(ROM\) 和高速缓冲存储器 \(Cache\) 三种。

\(RAM(Random\ Access\ Memory)\) 是一种读写存储器，其内容可以随时根据需要读出，也可以随时重新写入新的信息。当电源电压去掉时，RAM中保存的信息都将全部丢失。
\(ROM(Read-Only\ Memory)\) 是一种内容只能读出而不能写入和修改的存储器，其存储的信息是在制作该存储器时就被写入的。在计算机运行过程中，\(ROM\) 中的信息只能被读出，而不能写入新的内容。计算机断电后，\(ROM\) 中的信息不会丢失。它主要用于检查计算机系统的配置情况并提供最基本的输入/输出\((I/O)\)控制程序。
\(Cache\) 是高速缓冲存储器。由于计算机的 \(CPU\) 速度的不断提高，RAM的速度很难满足高速 \(CPU\) 的要求，所以在读/写系统内存都要加入等待的时间，这对高速 \(CPU\) 来说是一种极大的浪费。\(Cache\) 是指在 \(CPU\) 与内存之间设置的一级或两级高速小容量存储器，固化在主板上。在计算机工作时，系统先将数据由外存读入 \(RAM\) 中，再由 \(RAM\) 读入 \(Cache\) 中，然后 \(CPU\) 直接从 \(Cache\) 中取数据进行操作。

辅助存储器

辅助存储器（也称外存储器），它属于外部设备。用于存放暂不用的数据和程序，属于永久存储器。

它的容量一般都比较大，而且大部分可以移动，便于在不同计算机之间进行信息交流。在微型计算机中，常用的外存有软盘、硬盘、闪存和光盘。

软盘存储器由软盘、软盘驱动器和软盘适配器三部分组成。软盘是活动的存储介质，软盘驱动器是读写装置，软盘适配器是软盘驱动器与主机连接的接口。软盘驱动器安装在主机箱内，软盘驱动器插槽暴露在主机箱的前面板上，可方便地插入或取出软盘。
硬盘存储器是由电机和硬盘组成的，一般置于主机箱内。硬盘是涂有磁性材料的磁盘组件，用于存放数据。硬盘的机械转轴上串有若干个盘片，每个盘片的上下两面各有一个读/写磁头，与软盘磁头不同，硬盘的磁头不与磁盘表面接触，它们在离盘片面百万分之一英寸的气垫上。硬盘是一个非常精密的机械装置，磁道间只有百万分之几英寸的间隙，磁头传动装置必须把磁头快速而准确地移到指定的磁道上。
闪存又名优盘，是在存储速度与容量上介于软盘与硬盘之间的一种外部存储器。
光盘的存储介质不同于磁盘，它属于另一类存储器。由于光盘的容量大、存取速度较快、不易受干扰等特点，其应用越来越广泛。光盘根据其制造材料和记录信息方式的不同一般分为三类：只读光盘、一次写入型光盘和可擦写光盘。

七、计算机语言

计算机语言可以分为三类：机器语言、汇编语言、高级语言。

机器语言

计算机最早的语言处理程序是机器语言，它是计算机能直接识别的语言，而且速度快。机器语言是用二进制代码来编写计算机程序，因此又称二进制语言。

汇编语言

由于机器语言的记忆困难，汇编语言开始用一些符号代替机器指令。但是用汇编语言编写的源程序不能被计算机直接识别，必须使用特定程序将用汇编语言写的源程序翻译和连接成能被计算机直接识别的二进制代码。

高级语言

翻译方式

计算机并不能直接地接受和执行用高级语言编写的源程序，源程序在输入计算机时，通过程序翻译成机器语言形式的目标程序，通常有两种方式，即编译方式和解释方式。

编译方式：编译方式的翻译工作由编译程序来完成，它先将整个源程序都转换成二进制代码，生成目标程序，把目标程序和可执行程序连接。
解释方式：源程序进入计算机时，解释程序边扫描边解释，对源程序的语句解释一条，执行一条，不产生目标程序。

面向对象与面向过程

面向过程 (Procedure Oriented)：把事情拆分成几个步骤（相当于拆分成一个个的方法和数据），然后按照一定的顺序执行。
面向对象 (Object Oriented)：面向对象会把事物抽象成对象的概念，先抽象出对象，然后给对象赋一些属性和方法，然后让每个对象去执行自己的方法。

常见语言

语言	面向对象/面向过程	翻译方式
C	面向过程	编译方式
C++	面向对象	编译方式
Java	面向对象	不属于（更接近于解释方式）
Python	面向对象	解释方式
Pascal	面向对象	编译方式
Fortran	面向过程	编译方式

八、网络及网络协议

所谓计算机网络，就是利用通信线路和设备，把分布在不同地理位置上的多台计算机连接起来。计算机网络是现代通信技术与计算机技术相结合的产物。

网络协议

网络中计算机与计算机之间的通信依靠协议进行。协议是计算机收、发数据的规则。

HTTP 协议：基于TCP协议，超文本传输协议，对应于应用层，用于如何封装数据。也就是在底层是基于 socket，http 只不过是在收发数据的时候定义了很多规则，http头信息之类。
TCP/IP 协议：关注的是客户端与服务器之间的数据传输是否成功（三次握手，传输失败会重发）。传输层协议，主要解决数据如何在网络中传输.
TCP/UDP 协议:传输控制协议，对应于传输层，主要解决数据在网络中的传输。
IP 协议：对应于网络层，同样解决数据在网络中的传输。
TCP 协议：对应于传输层，是基于网络层的IP协议。
socket：属于传输层协议，是对TCP/IP协议的封装，Socket本身并不是协议，而是一个调用接口（API），通过Socket，我们才能使用TCP/IP协议。

电子邮件协议(全部隶属于TCP/IP协议)

SMTP 协议：简单邮件传输协议(TCP25端口)；
POP3 协议：POP邮局协议第三版本(TCP110端口)；
IMAP 协议：互联网信息访问协议(TCP143端口)；

网络简述

LAN：局域网
WAN：广域网
MAN：城域网
WLAN：无线局域网
WWAN：无线广域网
WMAN：无线城域网

九、进制转换

概述

常见进制有十进制、八进制、二进制、十六进制。

\(N\)进制逢\(N\)进一，十六进制 \(10-15\) 分别用 \(A-F\) 表示。

\(N\)进制的数一般用 \((\overline{qwq})_{N}\) 表示。

十进制转\(X\)进制

短除法。

\(X\)进制转十进制

\((N)_{X}\) 转为 \((M)_{10}\)。

记 \(N_i\) 表示 \((N)_{X}\) 从低位向高位第 \(i\) 位的数，\(SW_N\) 为 \((N)_{X}\) 的数位数。

\(M = \sum\limits_{i=1}^{SW_N} N_i\times X^{i-1}\)

十、信息编码

二进制编码

原码（原码表示法）：十进制数直接转换来的二进制数。值得注意的是，原码的最高位是符号位：整数为 \(0\)，负数为 \(1\)。 \(x=1100110\)，则\([x]原=01100110\)； \(x=-1100111\)，则\([x]原=11100111\)。
反码：正数的反码是本身，负数的反码是其除符号位之外的所有位按位取反的结果。 \(x=1100110\)，则\([x]反=01100110\)； \(x=-1100111\)，则\([x]反=10011000\)。
补码：正数的补码是其本身，复数的补码是其反码加一。 \(x=1100110\)，则\([x]补=01100110\)； \(x=-1100111\)，则\([x]补=10011001\)。

\(\text{ASCII}\) 码

\(\text{ASCII}\) 编码是由美国国家标准委员会制定的一种包括数字、字母、通用符号和控制符号在内的字符编码集，全称叫美国国家信息交换标准代码。

十一、计算机安全常识

计算机病毒是一种人为制造的能够侵入计算机系统并给计算机带来故障的程序或指令集合。

计算机病毒具有传播性、潜伏性、破坏性与隐蔽性的特点。

十二、运算相关知识

逻辑运算

逻辑与：\(\&\&\) 或 \(∧\)，同 \(T\) 则 \(T\)，否则为 \(F\)。
逻辑或：\(||\) 或 \(∨\)，有 \(T\) 则 \(T\)，否则为 \(F\)。
逻辑非：\(!\) 或 \(┐\)，为 \(T\) 则 \(F\)，反之亦然。
逻辑异或：^ 或 \(⊕\)，同为 \(F\)，异为 \(T\)。

位运算

按位与：\(\&\)，类似于逻辑与。
按位或：\(|\)，类似于逻辑或。
按位反：~，类似于逻辑非。
左移：\(<<\)，左移 \(x\) 位相当于乘 \(2^x\)。
右移：\(>>\)，右移 \(x\) 位相当于除 \(2^x\)。

十三、图论相关

概念

图(Graph) 是一个二元组 \(G=(V(G),E(G))\)，其中 \(V(G)\) 为点集，\(E(G)\) 为边集。
无向图(Undirected Graph)，边是双向的。
有向图(Directed Graph)，边是单向的。
自环(Loop)，对于某条边 \(e=(u,u)\)，则称其为一个自环。
重边(Multiple Edge)，图中存在两个相同的边。
简单图(Simple Graph)，一个图中没有自环和重边。
完全图(Complete Graph)，任意两点都有边相连。若一个图的点为 \(n\)，则边的个数为 \(\frac{n(n-1)}{2}\)
平面图，没有边相交的图。四个点的完全图是一个平面图，五个点完全图任意去掉一条边都是平面图。
连通图(Connected Graph)，任意两点都可以到达。
有向无环图(DAG)，顾名思义。它可以拓扑排序。
树(Tree)，无向无环连通图，且 \(n\) 个节点的树有 \(n-1\) 条边。
森林(forest)：每个连通分量（连通块）都是树的图。按照定义，棵树也是森林。
结点的深度(depth)：到根结点的路径上的边数。
树的高度(height)：所有结点的深度的最大值。
叶结点（leaf node）：没有子结点的结点。
父亲（parent node）：对于除根以外的每个结点，定义为从该结到根路径上的第二个结点。
祖先（ancestor）：一个结点到根结点的路径上，包括它本身 的所有节点。

十四、排列组合

加法原理与乘法原理

加法原理：有 \(n\) 类元素，第 \(i\) 类有 \(c_i\) 个元素，每类选一个元素，求方案数。
乘法原理：有 \(n\) 组元素，第 \(i\) 组有 \(c_i\) 个元素，每组选一个元素，求方案数。
加法原理实际上是分类，乘法原理实际上是分步。

排列与组合

排列

在 \(n\) 个数中有序选择 \(k\) 个数，方案数记为：

\[A_{n}^{k}=\frac{n!}{(n-k)!}\]

组合

在 \(n\) 个数中无序选择 \(k\) 个数，方案数记为：

\[C_{n}^{k}=\frac{n!}{k!(n-k)!}\]

在竞赛中也常记为：

\[{n\choose k} = \frac{n!}{k!(n-k)!}\]

组合数的一些性质：

\({n\choose k}={n\choose n-k}\) 考虑从 \(n\) 个中选 \(k\) 个相当于从 \(n\) 个中不选 \(n-k\) 个。
递推计算：\({n\choose k}={n-1\choose k}+{n-1\choose k-1}\) 从 \(n\) 个物品里面选 \(k\) 个出来，考虑第 \(n\) 个选不选。如果选就变成了从 \(n−1\) 个里选 \(k-1\)；否则就是从 \(n-1\) 个里选 \(k\)。
二项式定理：\((a+b)^n=\sum\limits_{i=0}^{n}{n\choose i}a^ib^{n-i}\)
\(\sum\limits_{i=0}^{n}{n\choose i}=2^n\)
\({a+b\choose k}=\sum\limits_{i=0}^{k}{a\choose i}{b\choose k-i}\)

答题方法

枚举法

最基本的方法，当题目范围不大的时候可以考虑枚举。

插板法

例：学校师生合影，共 \(8\) 个学生，\(4\) 个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式？

解：先排学生共有 \(A_{8}^{8}\) 种排法，然后把老师插入学生之间的空档，共有 \(7\) 个空档可插，选其中的 \(4\) 个空档,共 \(A_{7}^{4}\) 种选法。根据乘法原理，共有的不同坐法 \(A_{8}^{8}A_{7}^{4}\) 种。

捆绑法

例：\(5\) 个男生 \(3\) 个女生排成一排，\(3\) 个女生要排在一起，有多少种不同的排法？

解：因为女生要排在一起，所以可以将 \(3\) 个女生看成是一个人，与 \(5\) 个男生作全排列，有 \(A_{6}^{6}\) 种排法，其中女生内部也有 \(A_{3}^{3}\) 种排法，根据乘法原理，共有 \(A_{6}^{6}A_{3}^{3}\) 种不同的排法。

对等法

例：学校安排考试科目 \(9\) 门，语文要在数学之前考，有多少种不同的安排顺序?

解：不加任何限制条件，整个排法有 \(A_{9}^{9}\) 种，“语文安排在数学之前考”与“数学安排在语文之前考”的排法是相等的，所以语文安排在数学之前考的排法共 \(\frac{1}{2}A_{9}^{9}\)种。

卡特兰数

卡特兰数的定义如下：

\[ \begin{align} \left\{ \begin{array}{ll} C_n=1 &(n=0,1)\\ C_n=\sum\limits_{i=0}^{n-1}C_iC_{n-i-1} &(n\geq 2)\\ \end{array} \right. \end{align} \]

非递推式：

\[ C_n={2n\choose n}-{2n\choose n+1}=\frac{2n\choose n}{n+1} \]

卡特兰数的组合意义：

\(n\) 个点的二叉树
\(n+1\) 个点的区分儿子顺序的树
\(2n+1\) 个点的二叉树，满足没有儿子个数为 \(1\) 的节点
长度为 \(2n\) 的合法括号匹配
长度为 \(2n\) 的字符串的数量，其中有 \(n\) 个 \(0\)，\(n\) 个 \(1\)，且对于任意的 \(i\)，\(0\) 的数量都不少于 \(1\) 的。
\(2\times n\) 的杨表数量。

证明略。

容斥原理

\[\left|\bigcup\limits_{i=1}^{n}S_i\right|=\sum\limits_{m=1}^n(-1)^{m-1}\sum\limits_{a_i<a_{i+1} }\left|\bigcap\limits_{i=1}^mS_{a_i}\right|\]

简单的小应用：

\(|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|B\cap C|-|C\cap A|+|A\cap B\cap C|\)

十五、时空复杂度相关

时间复杂度：算法的时间复杂度\(\text{(Time Complexity)}\)是指算法所需要的计算工作量，用算法所执行的基本运算次数来度量。
空间复杂度：算法的空间复杂度\(\text{(Space Complexity)}\)是指执行这个算法所需要的内存空间。

主定理

在算法分析中，主定理 \(\text{(master theorem)}\) 提供了用渐近符号（大 \(O\) 符号）表示许多由分治法得到的递推关系式的方法。

支配理论

假设有递归关系式：

\[T(n)=aT\left(\frac{n}{b}\right)+f(n),其中a\geq 1,b> 1\]

其中：

\(n\) 为问题规模；
\(a\) 为递归的子问题数量；
\(\frac{n}{b}\) 为每个子问题的规模（假设每个子问题的规模基本相同）；
\(f(n)\) 为递归以外进行的计算工作。

情形一

若 \(f(n)<n^{\log_b a}\)（多项式的小于），则\(T(n)=\Theta(n^{\log_{b}a})\)

情形二

若 \(f(n)=n^{\log_b a}\)，则\(T(n)=\Theta(n^{\log_{b}a}\log n)\)

情形三

若 \(f(n)>n^{\log_b a}\)（多项式的大于），则\(T(n)=\Theta(f(n))\)

常见排序算法与其时空复杂度

排序方法	时间复杂度	辅助存储空间复杂度	稳定性
插入排序	\(O(n^2)\)	\(O(1)\)	稳定
冒泡排序	\(O(n^2)\)	\(O(1)\)	稳定
选择排序	\(O(n^2)\)	\(O(1)\)	不稳定
快速排序	\(O(n\log n)-O(n^2)\)	\(O(\log n)-O(n)\)	不稳定
希尔排序	\(O(n\log n)\)	\(O(1)\)	不稳定
堆排序	\(O(n\log n)\)	\(O(1)\)	不稳定
归并排序	\(O(n\log n)\)	\(O(n)\)	稳定
基数排序	\(O(d(n+r))\)	\(O(rd+1)\)	稳定
桶排序	\(O(\max \{value\})\)	\(O(\max\{value\})\)	稳定

十六、后记

说些什么

又是一年初赛季，回首过去的一篇NOIP初赛知识点整理和过去忐忑的初赛经历，发现很多不足之处，遂写下本篇。仓促之下写完，也许未来还会有修修补补，也祝我们都能在初赛中取得好成绩。

参考与鸣谢

参考

鸣谢

\(\text{EXODUS}\) 对本文的审查。
\(\text{lwj}\) 对本文的勘误。

初赛知识点整理第2版