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

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

一、NOI 史

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

二、计算机发展史

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

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

三、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 文件

四、计算机语言

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

机器语言

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

汇编语言

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

高级语言

翻译方式

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

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

面向对象与面向过程

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

常见语言

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

五、进制、编码和运算

进制

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

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

常见的基本字符的 \(\text{ASCII}\) 码：

0：\(48\)；
A：\(65\);
a：\(97\)；

运算符

C++ 中的运算符可以分为以下几类：算术运算符、位运算符、逻辑运算符、比较运算符、自增自减运算符等；

运算符的优先级：

优先级	运算符	描述
1	`::`	作用域解析
2	`a++ a--`	后缀自增与自减
2	`a()`	函数调用
2	`a[]`	下标
2	`. ->`	成员访问
3	`++a --a`	前缀自增与自减
3	`+a -a`	单目加减运算符
3	`! ~`	逻辑非和逐位非
3	`(type)`	C 风格转换
3	`*a`	间接（解引用）
3	`&a`	取址
5	`a*b a/b a%b`	乘法、除法与取模
6	`a+b a-b`	加法与减法
7	`<< >>`	左移与右移
9	`< <= > >=`	关系运算符
10	`== !=`	相等性运算符
11	`a&b`	按位与
12	`^`	按位异或
13	`\\|`	按位或
14	`&&`	逻辑与
15	`\\|\\|`	逻辑或
16	`=`	赋值

总体来说，数学运算符>关系运算符>位运算符>逻辑运算符，注意这个总结并不完备，因为有特例出现。

六、图论相关

图

图(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）：一个结点到根结点的路径上，包括它本身 的所有节点。

二叉树

先序遍历：根→左→右。
中序遍历：左→根→右。
后序遍历：左→右→根。
得到中序遍历序列和先、后任意一个遍历序列均可以得到确定的二叉树。
满二叉树/完美二叉树：所有叶结点的深度均相同，且所有非叶节点的子节点数量均为 \(2\) 的二叉树称为完美二叉树。
完全二叉树：只有最下面两层结点的度数可以小于 \(2\)，且最下面一层的结点都集中在该层最左边的连续位置上。

七、排列组合

加法原理与乘法原理

加法原理：有 \(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)}\)是指执行这个算法所需要的内存空间。

渐进符号

\(\Theta\)：给定的函数的上下界；
\(O\)：给定的函数的渐进上界；
\(\Omega\)：给定的函数的渐进下界；
\(o\)：若 \(O\) 相当于小于等于号，那么 \(o\) 就相当于小于号；
\(\omega\)：若 \(\Omega\) 相当于大于等于号，那么 \(omega\) 就相当于大于号。

主定理

在算法分析中，主定理 \(\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(n+w),w\)为值域	\(O(w)\)	稳定
桶排序	\(O(\max \{value\})\)	\(O(\max\{value\})\)	稳定

初赛知识点整理第3版