NOIP 初赛知识点整理。

一、信息学史

第一台电子计算机：\(\text{ENIAC}\)，美国宾夕法尼亚大学，1946年2月14日。
\(\text{NOI}\) 于 1984年 首次举行。
\(\text{NOIP}\) 于 1995年 首次举行。
\(\text{NOIP}\) 于 2019年 暂停。
\(\text{CSP}\) 于 2019年 首次举行。
\(\text{NOIP}\) 于 2020年 恢复。
2022年后，\(\text{NOI}\) 系列赛事将停止对 Pascal，C 语言的支持，仅允许使用 C++ 语言。

二、信息学著名人物与奖项

图灵：艾伦·麦西森·图灵(Alan Mathison Turing)，被称为 计算机科学之父、人工智能之父。
图灵奖：计算机界最高奖。
冯·诺依曼：约翰·冯·诺依曼(John von Neumann)，现代计算机之父，博弈论之父，奠基现代计算机基本结构(冯·诺依曼体系计算机)。
姚期智，唯一一位华籍图灵奖获得者，清华大学人工智能姚班教授。

三、现代计算机基础结构

冯·诺依曼架构

五大部分：

运算器

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

控制器

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

存储器

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

输入设备

略。

输出设备

略。

计算机硬件系统

中央处理器(CPU)

作为计算机系统的运算和控制核心，是信息处理、程序运行的最终执行单元。由运算器和控制器组成。

目前知名品牌有 \(\text{Intel}\) 和 \(\text{AMD}\)。

存储器

只读存储器(ROM)

以非破坏性读出方式工作，只能读出无法写入信息。信息一旦写入后就固定下来，即使切断电源，信息也不会丢失，所以又称为固定存储器。

简要：断电不消失数据。

随机存储器(RAM)

是与CPU直接交换数据的内部存储器。它可以随时读写（刷新时除外），而且速度很快，通常作为操作系统或其他正在运行中的程序的临时数据存储介质。RAM工作时可以随时从任何一个指定的地址写入（存入）或读出（取出）信息。它与ROM的最大区别是数据的易失性，即一旦断电所存储的数据将随之丢失。RAM在计算机和数字系统中用来暂时存储程序、数据和中间结果。

简要：断电消失数据。

四、网络及网络协议

协议简述

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：无线城域网

五、计算机基本常识

存储单位换算

\(1PB=1024TB\);

\(1TB=1024GB\);

\(1GB=1024MB\);

\(1MB=1024KB\);

\(1KB=1024B\);

\(1B=8bit\);

进制转换

短除法。

编程语言

低级语言

汇编语言，机器语言

高级语言

面向对象

C++,Java,EIFFEL,Simula 67等。

面向过程

C,Fortran等。

六、二进制相关知识

原码、补码、反码

原码(原码表示法)：十进制数直接转换来的二进制数。值得注意的是，原码的最高位是符号位：整数为 \(0\)，负数为 \(1\)。
补码：正数的补码是其本身，复数的补码是其反码加一。
反码：正数的反码是本身，负数的反码是其除符号位之外的所有位按位取反的结果。

七、运算相关知识

数学运算

略。

逻辑运算

逻辑与：\(\&\&\) 或 \(∧\)，同 \(T\) 则 \(T\)，否则为 \(F\)。
逻辑或：\(||\) 或 \(∨\)，有 \(T\) 则 \(T\)，否则为 \(F\)。
逻辑非：\(!\) 或 \(┐\)，为 \(T\) 则 \(F\)，反之亦然。
逻辑异或：\(\text{^}\) 或 \(⊕\)，同为 \(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）：一个结点到根结点的路径上，包括它本身 的所有节点。

其余参考OI-Wiki:树，OI-Wiki:图。

~~图论怎么这么多基础概念~~。

二叉树

先序遍历：根—左—右。

中序遍历：左—根—右。

后序遍历：左—右—根

九、基础数据结构理论知识

栈

先进后出(FILO,First In Last Out)，可以想象成一个竖立的木桶。

后缀表达式：可以用栈实现。

队列

先进先出(FIFO,First In First Out)，可以想象成一个队列。

双端队列、优先队列、单调队列略。

链表

访问元素时间复杂度为 \(O(n)\)，但是删除元素时间复杂度为 \(O(1)\)。

十、排列组合

排列数

从 \(n\) 个不同的元素中任取 \(m\) 个元素的所有排列的个数，记作 \(P_{n}^{m}\)。

\[P_{n}^{m} = \frac{n!}{(n-m)!}\]

组合数

从 \(n\) 个不同元素中，任取 \(m\) 个元素并成一组，记作 \(C_{n}^{m}\)。

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

加法原理和乘法原理

感性理解。

题目中的技巧

插入法

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

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

捆绑法

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

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

剩余法

反过来。

对等法

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

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

十一、时空复杂度相关

时间复杂度

时间复杂度的计算，简而言之就是计算循环层数。

例如对于下列代码段：

for(int i = 1; i <= n; i++)
	for(int j = 1; j <= n; j++)
    	ans++;

这里套用了两层到 \(n\) 的循环，所以说时间复杂度为 \(O(n^2)\)。

常见的时间复杂度计算：

二分类：\(O(\log n)\)；
搜索类：\(O(感性理解)\)；
乱搞类：\(O(能过)\)。

值得注意的是，计算时间复杂度一般忽略其中的常数因子。

如：一个算法的时间复杂度为 \(O(2n)\)，则一般写成 \(O(n)\)。

这也是 OIer 常说的 大常数 的由来。常数因子有时也可能导致 \(TLE\)，这就是卡常的由来。

~~扯远了~~

其余更多复杂的时间复杂度可以参考 《具体数学》渐进式。

空间复杂度

类似于时间复杂度，即数组的大小。

例如对于下列代码段：

int a[n];
int b[n][n];

a数组的空间复杂度是 \(O(n)\)，b数组的空间复杂度是 \(O(n^2)\)。

常见基础算法的时空复杂度

为了方便，前面均为时间复杂度，后面均为空间复杂度。

有些算法不提供空间复杂度，用 \(-\) 表示。

\(Dijkstra(无优化)\)：\(O(n^2),-\)；
\(Dijkstra(堆优化)\)：\(O(n+m)\log n,-\)；
\(SPFA\)：\(\text{Worst}O(|V|\cdot|E|),-\)；
\(Floyd\)：\(O(n^3),-\)；
\(0/1背包\)：\(O(VN),O(VN)\);
\(KMP\)：\(O(m+n)\)。

排序算法的时间复杂度与稳定性

排序方法	时间复杂度	稳定性
插入排序	\(O(n^2)\)	稳定
冒泡排序	\(O(n^2)\)	稳定
选择排序	\(O(n^2)\)	不稳定
快速排序	\(期望O(n\log n)\)	不稳定
希尔排序	\(O(n\log n)\)	不稳定
堆排序	\(O(n\log n)\)	不稳定
归并排序	\(O(n\log n)\)	稳定
基数排序	\(O(d(n+r))\)	稳定
桶排序	\(O(\max \{value\})\)	不稳定
~~猴子排序~~	\(O(1)-O(∞)\)	不稳定
~~欧皇排序~~	\(O(\text{NULL})\)	稳定

十二、概率与期望

不会

十三、阅读程序与补全程序相关

先看有没有注释，~~没有注释的都是屑~~；
猜测变量名称，猜测变量的作用；
自己阅读每个语句，理解其作用；
理解代码段的作用；
根据样例猜测作用；
手玩几组数据，模拟代码作用；
认真审题，细致思考。

十四、总结

个人认为前面的计算机基础知识背背即可，重点放在 排列组合题 和 阅读/补全程序题 上，多刷初赛原题。

考场上不要慌张，时间充足，充分利用时间，多检查几遍，~~不会的看顺眼的蒙~~。