CSP -J 考前复习一文通

ny_Dacong · 2024-08-17 14:49:25 · 算法·理论

前言

本文算是作者的学习笔记，也可以用于 CSP-J 初赛考前复习，如有错误请在评论指出。

本文写作时间比较紧张，参考了各种资料，包括但不限于百度百科、OI-wiki、洛谷专栏、各类参考书籍等等，在此一并感谢。如有侵权，请联系删除或更换。

本文同步发表于：

博客园：https://www.cnblogs.com/ny-Dacong/p/18658165。
洛谷专栏：https://www.luogu.com.cn/article/jjecw5ib。

常识

计算机发展的代表人物

艾伦·图灵

艾伦·图灵（1912—1954），英国科学家，于 1936 年提出一种抽象的计算模型——图灵机（Turing Machine）。

图灵机将人类数学运算的过程进行了抽象，由虚拟的机器代替人们进行计算。

图灵机证明了通用计算理论，肯定了计算机实现的可能性。同时给出了计算机应有的主要架构，为后来计算机的发明奠定了基础。

1966 年，美国计算机协会（ACM）设立图灵奖，专门奖励为计算机事业做出重要贡献的个人。

图灵对人工智能的发展也贡献显著。有“人工智能之父”的美誉。

莫西利和埃克特

美国宾夕法尼亚大学由埃克特领导的“莫尔小组”，于 1946 年 2 月研制出世界上第一台通用计算机，名为 ENIAC（Electronic Numerical Internal And Calculator）。

ENIAC 体积庞大，耗电高，运算速度每秒几千次。可以按照事先编好的程序自动执行算术运算、逻辑运算和储存数据的功能。

冯·诺依曼

冯·诺依曼，匈牙利裔美籍科学家，于 1945 年 3 月起草《储存程序通用电子计算机方案》，即 EDVAC（Electronic Discrete Variable Automatic Computer）。它对后来计算机的设计产生决定性影响。主要思想有三个：计算机系统的冯·诺依曼结构、利用储存程序运行计算机、采用二进制编码替代十进制。

冯·诺依曼被后人称为“计算机之父”。

戈登·摩尔

戈登·摩尔，美国科学家，于 1965 年提出“摩尔定律”，该定律被称为计算机第一定律。主要有以下 3 种“版本”：

集成电路芯片上所集成的电路的数目，每隔 18 个月就翻一番。
微处理器的性能每隔 18 个月提高一倍，而价格下降一半。
用 1 美元所能买到的计算机的性能，每隔 18 个月翻两番。

摩尔定律揭示了信息技术进步的速度，成为许多工业对于性能预测的基础。

计算机领域奖项

必考：图灵奖。

图灵奖

图灵奖（Turing Award）由美国计算机协会（ACM）于 1966 年设立，专门奖励为计算机事业做出重要贡献的个人。

图灵奖获奖条件极高、评奖程序严格，一般每年只奖励一名计算机科学家，只有极少几年多人共获此奖。

图灵奖是计算机界最负盛名、最崇高的奖项，有“计算机界的诺贝尔奖”之称。

计算机先驱奖

计算机先驱奖（Pioneer Award）首次颁发于 1996 年，旨在表彰那些在计算机领域做出开创性贡献的个人。这些贡献可以是技术、理论或应用方面的突破。

奖项授予那些通过技术创新、重大发明、开创性研究或在计算机领域的领导力，推动了计算机科学与技术发展的个人。

设立机构：计算机历史博物馆（Computer History Museum）。

IEEE 奖

IEEE 奖（IEEE Awards）自 1884 年成立以来，设立了多个奖项，如 IEEE 计算机先驱奖、IEEE 电气和电子工程奖等。IEEE 计算机学会杰出贡献奖特别关注对计算机科学领域的重要贡献。

奖项授予那些在技术、研究、教育或服务方面表现突出的个人，通常这些奖项包括技术创新、学术成就和对 IEEE 组织的贡献等方面。

设立机构：电气和电子工程师协会（IEEE）。

ACM 终身成就奖

ACM 终身成就奖（ACM Lifetime Achievement Award）设立于2010年，表彰那些在计算机科学领域拥有长达数十年的杰出贡献的个人。

获得者必须在其职业生涯中对计算机科学的进步做出深远的影响，并在该领域中获得广泛认可和尊重。

设立机构：美国计算机学会（ACM）。

计算机的基本构成

要想实现计算机的基础功能，计算机必须由运算器、存储器、控制器、输入设备、输出设备构成，缺少前两者就无法正常启动计算机。

冯·诺依曼结构

数学家冯·诺依曼提出了计算机制造的三个基本原则：

采用二进制逻辑。
程序存储执行。
计算机由五个部分组成（运算器、控制器、存储器、输入设备、输出设备）。

这套理论被称为冯·诺依曼体系结构。

CPU

CPU（Central Processing Unit），中央处理器，计算机的核心部件，被称为计算机的“大脑”，又称“微处理器”。

一共有 4 个主要部件：

算术逻辑单元（ALU）
控制单元（CU）
寄存器
缓存（Cache）

算术逻辑单元（ALU）

功能：执行所有算术运算（如加法、减法、乘法、除法）和逻辑运算（如与、或、非）。
运作：ALU 接收两个操作数并根据指令执行相应的运算，结果会被送回寄存器或内存。

控制单元（CU）

功能：负责指挥CPU的所有操作，包括指令的解码和执行。
运作：控制单元从内存中取出指令，解码指令的操作类型，然后控制 ALU 、寄存器和其他组件以执行指令。

寄存器

功能：提供高速的数据存储和处理空间。寄存器用于存储操作数、结果、指令等。
类型：
- 通用寄存器：用于存储操作数和计算结果。
- 专用寄存器：如程序计数器（PC），存储下一条要执行的指令的地址；指令寄存器（IR），存储当前正在执行的指令。

缓存（Cache）

功能：提供比主内存更快的数据访问速度，用于临时存储频繁访问的数据和指令。
级别：
- L1 缓存：直接集成在 CPU 内部，访问速度最快，但容量较小。
- L2 缓存：通常较大，但访问速度略慢于 L1 缓存。
- L3 缓存：多个核心共享，容量更大，但访问速度最慢。

内储存器

内存储器，简称“内存”，用于电脑内部的存储。相对外存而言，读写速度快，但是存储空间小。

内存通常分为两大类：只读存储器（ROM）和随机存取存储器（RAM）。

只读存储器 ROM

只读存储器主要用于存储不需要频繁更改的数据，如固件、启动程序等。即使在断电时，数据也不会丢失。通常只能读取，不能修改，但现代一些 ROM 类型允许有限的写入操作。

随机存取存储器 RAM

随机存取存储器主要用于存储和快速访问正在使用的数据和程序。断电时，数据会丢失，但是可以随时读取和写入数据，允许随机访问。

RAM 用于存储正在运行的操作系统、应用程序和数据。在 CPU 和主内存之间提供高速数据访问，减少数据传输延迟。

外储存器

外存储器简称“外存”，用于处置长期保存的数据，一般处于电脑外部，断电后数据不会丢失。相对内存而言，外存读写速度慢，但存储容量大。主要包括硬盘、光盘、U 盘（USB闪存盘）等类型。

输入设备

输入设备指在计算机与人交互时，接收外部命令或者需要加工的数据的设备。常用的输入数据包括键盘、鼠标、麦克风、摄像头等。

输出设备

输出设备指在计算机与人交互时，将处理结果以人类能够识别/感受的方式呈现出来的设备。常有的输出设备包括显示器、音响、打印机等。

计算机网络和 Internet 的基本概念

定义

计算机网络是由多个计算机和网络设备通过通信链路相连，形成的一个信息交换和资源共享的系统。网络可以是局域网（LAN）或广域网（WAN），并且支持不同的通信协议。

历史

1960 年代：网络概念最初由美国国防部的 ARPA （高级研究计划局）提出，发展了 ARPANET，这是早期的网络之一。
1970 年代：TCP/IP 协议的诞生，成为现代互联网的基础。
1980 年代：互联网技术逐步向学术界和商业界开放，TCP/IP 协议成为标准。
1990 年代：万维网（WWW）的发明，使得互联网进入大众生活。

组成

互联网协议（IP）：为每个连接到互联网的设备分配唯一的 IP 地址，用于标识和定位。
传输控制协议（TCP）：确保数据在互联网上的可靠传输，将数据分割成包并重新组合。
域名系统（DNS）：将人类易读的域名（如 www.example.com ）转换为机器可识别的 IP 地址。
路由器：负责在网络中转发数据包，将信息从源地址传送到目标地址。

NOI 以及相关活动的历史

NOI（National Olympiad in Informatics）：全国青少年计算机程序设计竞赛，开办于 1984 年，现更名全国青少年信息学奥林匹克竞赛。

NOIP（National Olympiad in Informatics in Provinces）：全国青少年信息学奥林匹克联赛，自 1995 年至 2018 年已举办 24 次。复赛可使用 C、C++、Pascal 语言，2022 年后只能使用 C++。2019 年，由于某种原因，NOIP 暂停，在 2020 年恢复。

特别的，如果题目询问了 NOIP 举办了多少届，需要扣除一届，因为 CSP 举行的时候 NOIP 还没有举行。

APIO（Asia-Pacific Informatics Olympiad）：亚洲与太平洋地区信息学奥林匹克竞赛。

IOI（International Olympiad in Informatics）：国际信息学奥林匹克竞赛，等级最高的信息学竞赛。

NOI 以及相关活动的规则

详见 https://www.noi.cn/gynoi/tlgd/2009-09-17/710430.shtml。本文将陈列其中常考的部分。

竞赛组织者将在竞赛场地为选手提供草稿纸、饮水、以及必要的食品。

对于交互式程序题和非交互式程序题，对选手程序使用内存大小的限制包括运行代码、程序运行时所需的栈和堆在内的所有工作内存的总和。

对选手程序运行时间的限制一般均大于标准答案程序所需最长运行时间的 50 \% 以上，以避免测试中的超时判断误差。

NOI 的竞赛分为两场，每场竞赛的时间为 5 小时。两场竞赛之间应间隔一天。

选手可以携带书写工具，如钢笔、铅笔等，以及手表和适量的衣物等进入赛场。有特殊情况需要携带其他物品者需事先取得竞赛委员会的批准。

选手不可以携带上述规定之外的其他物品，如纸张、书籍、食品、饮料等进入赛场。选手被严格禁止携带软盘、光盘、U 盘等存储设备和介质，以及手机、电子辞典、PDA 等电子及通信设备。凡携带上述被严格禁止的设备进入竞赛场地者，在竞赛开始后一经发现，无论是否使用，均以作弊论处，取消其该场竞赛的资格和成绩。

单位换算

常用的单位有两种，分别是 xxxxbinary byte 与 xxxx byte。

Binary Byte

小单位	大单位
8 \text{ bit(比特)}	1 \text{ B(Byte / 字节)}
1024 \text{ B}	1 \text{ KiB(\underline{k}ilob\underline{i}nary \underline{b}yte)}
1024 \text{ KiB}	1 \text{ MiB(\underline{m}egab\underline{i}nary \underline{b}yte)}
1024 \text{ MiB}	1 \text{ GiB(\underline{g}igab\underline{i}nary \underline{b}yte)}
1024 \text{ GiB}	1 \text{ TiB(\underline{t}erab\underline{i}nary \underline{b}yte)}

这些数据单位的英文全称的第一个单词代表着这个数据单位的字节数。kilo，mega，giga，tera 是英文中的单位名，后面的 binary 代表着“在二进制下”。

我们常把这些单位中的 i 省去，如：KB、MB。

Byte

小单位	大单位
8 \text{ bit(比特)}	1 \text{ B(Byte / 字节)}
1000 \text{ B}	1 \text{ KB(\underline{k}ilo \underline{b}yte)}
1000 \text{ KB}	1 \text{ MB(\underline{m}ega \underline{b}yte)}
1000 \text{ MB}	1 \text{ GB(\underline{g}iga \underline{b}yte)}
1000 \text{ GB}	1 \text{ TB(\underline{t}era \underline{b}yte)}

这些数据单位的英文全称中少了“binary”，所以这里的数量单位代表着十进制下的数据单位。

注意到，这些数据单位和上一种数据单位的简写是相同的。若无特殊说明，使用第一种数据单位，即 KB 默认代表 1024 字节，MB 默认代表 1024 KiB。

我们常常会遇到硬盘标注大小和计算机内显示大小不同的问题。这其实是硬盘厂商为了节约成本玩的文字游戏。他们在硬盘上标注的 GB 其实代表 giga byte，而不是我们默认的 gigabinary byte。

这样一来，硬盘大约缩水了 7 \%。

程序设计语言

程序设计语言是一种用于编写计算机程序的语言，它允许程序员向计算机发出指令来执行特定的任务或解决问题。

机器语言（机器码）是最早的语言，也是计算机能识别的语言，由二进制数字组成，速度快，人类编码难度高，一般由计算机自动转换。

汇编语言使用符号代替二进制数，计算机不能直接识别汇编语言，需要用编译器进行编译，难度依然很大，目前除了对性能要求极高的需求以外不被使用。

高级语言比如如今的编程语言（C++，JAVA 等），需要用编译器，难度小，分为编译方式和解释方式两种编译方式。

编译方式（例如 C++）：先对整个程序进行编译（会进行多次分析），再执行程序。速度快（进行多次编译对程序进行优化）。
解释方式（例如 Python/PHP）：扫描一行解释一行，速度慢（无法进行优化）。

程序基本概念

标识符

标识符是程序中用于命名各种元素（如变量、函数、类、对象等）的名称。标识符的名称通常由字母、数字和下划线组成，但不能以数字开头，并且大小写敏感，不能使用编程语言的关键字来命名。

关键字

关键字是编程语言预定义的保留字，用于表示语言中的特定语法结构或操作。关键字具有特殊的意义，不能用作标识符。

关键字通常是编译器或解释器解析语法的基础部分。

常量

常量是程序中值不变的量。在程序执行期间，其值不会改变。常量通常用于表示固定的、不变的数据。

常量的值在定义后不能更改。

变量

变量是程序中用于存储可变数据的名称。

变量必须在使用前声明。

变量的值可以在程序执行期间改变。

变量的类型决定了它可以存储的数据类型（例如整型、浮点型、字符串等），且定义后不可改变。

头文件

头文件是一个包含声明和宏定义的文件，通常用于声明函数、类、变量等，以便在多个源文件中使用。

头文件通常以 .h 或 .hpp 扩展名结尾。

使用头文件可以避免重复代码和简化程序的结构。

命名空间

命名空间是一个作用域，用于组织代码并防止命名冲突。它可以包含变量、函数、类等。

命名空间可以嵌套，即一个命名空间可以包含其他命名空间。

可以使用 :: 操作符访问命名空间中的元素。

使用命名空间可以帮助避免不同库或模块中的名称冲突。

编辑、编译、解释、调试

编辑

编辑是编写和修改源代码的过程。源代码通常以文本文件的形式存在，编辑过程中使用的工具称为文本编辑器或集成开发环境（IDE）。

调试

调试是检测和修复程序错误的过程。调试可以帮助开发人员理解程序的运行状态，并找出导致程序行为异常的原因。

编译

先对整个程序进行编译（会进行多次分析），再执行程序。速度快（进行多次编译对程序进行优化）。例如 C++。通常编译后会生成一个可执行文件。

解释

逐行读取和执行源代码，不生成中间的可执行文件。解释器在程序运行时逐步解析和执行代码。

也就是说读一行做一行。例如 Python 语言。

基本数据类型

整型

int：基本整数类型，占有 4 字节。范围一般是 -2147483648 到 2147483647，也就是 -2^{31} \sim 2^{31}-1。
short：短整型，通常有 2 字节。范围一般是 -32768 到 32767，也就是 -2^{15} \sim 2^{15}-1。
long long：长整型，占有 8 字节。范围一般是 -9223372036854775808 到 9223372036854775807,也就是 -2^{63} \sim 2^{63}-1。

无符号整型

unsigned int：无符号整数，通常有 4 字节。范围是 0 到 4294967295，也就是 0 \sim 2^{32}-1。
unsigned short：无符号短整型，通常有 2 字节。范围是 0 到 65535，也就是 0 \sim 2^{16}-1。
unsigned long long：无符号更长整型，至少有 8 字节。范围通常是 0 到 18446744073709551615，也就是 0 \sim 2^{64}-1。

字符型

char：基本字符类型，通常有 1 字节。范围通常是 -128 到 127，也就是 -2^{8} \sim 2^{8}-1。

浮点型

float：单精度浮点型，通常有 4 字节，精度大约是 6 \sim 7 位有效数字。
double：双精度浮点型，通常有 8 字节，精度大约是 15 \sim 16 位有效数字。

布尔型

bool：用于表示布尔值，只有两个可能的值：true 和 false。占用的字节数说法不一，通常认为是 1 字节。

估算空间

确定一个数组的空间通常分为 4 个步骤：

确定单个元素的大小。
确定元素数量。
计算空间。
转换单位。

以 int num[100000] 为例：

数据类型是 int，所以一个元素占据 4 个字节的大小。

元素总数是 10^5，所以所占空间是 10^5 \times 4 = 400000 \text{ (byte)}。

然后转换为其他单位。

因为 1 \text{ KiB} = 1024 \text{ byte}，所以 400000 \text{ byte} = 390.625 \text{ KiB}。

结构体与联合体

结构体

定义结构体示例：

struct note{
    int num;
    char chr;
};

结构体可以包含多个不同类型的数据成员，每个成员都有自己的内存空间。相较于联合体，每个成员可以同时存在。

访问结构体示例：

struct note{
    int num;
    char chr;
};

note a;
a.num = 10;
a.chr = 'A';

cout<<a.num<<' '<<a.chr;//10 A

联合体

定义联合体示例：

union note{
    int num;
    char chr;
};

可以包含多个不同类型的数据成员，但同一时间只能有一个成员存储有效数据。

访问联合体示例：

union note{
    int num;
    char chr;
};

note a;

a.num = 10;
cout<<a.num<<endl;//10

a.chr = 'A';//会覆盖之前的 10
cout<<a.chr<<endl;

树

定义：树是一棵连通且无环的图，边数 = n-1。（n 表示节点数）。

根节点：树最上层的节点，一棵树有且只有一个。
深度：某个节点到根结点的路径上的边数叫这个节点的深度。（根节点的深度可以是 1 也可以是 0，通常会特殊说明。其余节点的深度据此推算。）
高度：所有结点的深度的最大值。
叶节点：没有子结点的结点。
父节点：对于除根以外的每个结点，从该结点到根路径上的第二个结点。根结点没有父结点。
祖先：一个结点到根结点的路径上，除了它本身外的结点。根结点的祖先集合为空。
子节点：如果 u 是 v 的父亲，那么 v 是 u 的子结点。子结点的顺序一般不加以区分，二叉树是一个例外，有左儿子/右儿子之分。
子树：删掉与父亲相连的边后，该结点所在的子图。

二叉树

二叉树是一种每个节点最多只有两个子节点的树形数据结构。

完全二叉树（Complete Binary Tree）：除了最后一层，其他层的节点都是满的，且最后一层的节点从左到右填满。
满二叉树（Full Binary Tree）：每个节点要么是叶子节点，要么有两个子节点，且所有叶子节点都在同一层。有另外一种名字叫“完美二叉树”，请注意与完全二叉树的区分。若根节点深度为 1，且这棵满二叉树的高度为 k，则总结点数为 2^k-1。

二叉树的遍历

必考的有 3 种：前序遍历、中序遍历、后序遍历。

前序遍历：访问根节点，然后递归遍历左子树，最后递归遍历右子树。
中序遍历：递归遍历左子树，然后访问根节点，最后递归遍历右子树。
后序遍历：递归遍历左子树，然后递归遍历右子树，最后访问根节点。

知道前序遍历+中序遍历或者后序遍历+中序遍历可以推出这棵二叉树。注意：前序遍历+后序遍历不可以推出二叉树！

举例：

.    b
   /   \
  a     c
 / \   /
e   g f
       \
        d

前序遍历：baegcfd。
中序遍历：eagbfdc。
后序遍历：egadfcb。

假如只知道前序遍历以及中序遍历，推出整棵二叉树：

确定根节点。前序遍历的第一个字符就是根节点。这里是 b。
找出它的左右子树。中序遍历中，根节点的左边是左子树，右边是右子树。这里 b 的左边 eag 是左子树，fdc 是右子树。
对于刚刚的每一棵子树，重复步骤 1、2，直到只剩下叶节点。比如，我们刚刚确定了 eag 在同一棵子树里，那么我们通过前序遍历确定 a 是这棵子树的根节点，然后通过中序遍历确定 e 在 a 的左子树，g 在 a 的右子树。

前/中/后缀表达式

在日常生活中，我们习惯把表达式的运算符号写在两个参与运算的元素的中间。

比如 114*514、2+3*5、4+(5+3)*8/2-6 等等。

这样的表达式称为“中缀表达式”。

如果把表达式的运算符号写在两个参与运算的元素的前面，比如把 114*514 写成 * 114 514，这样的表达式我们称为“前缀表达式”，也称为“波兰式”。

刚刚的三个例子的前缀表达式分别是：

* 114 514。
+ 2 * 3 5。
- + 4 / * + 5 3 8 2 6。

同理，如果把表达式的运算符号写在两个参与运算的元素的后面，我们称为“后缀表达式”，也称为“逆波兰式”。

比如：

114 514 *。
2 3 5 * +。
4 5 3 + 8 * 2 / + 6 -。

前/后缀表达式的好处是不用括号就可以体现优先级，有利于计算机的计算。但是同一个前/后缀表达式不一定有唯一的一个中缀表达式与之对应。原因见下面的“表达式树”。

表达式树

如何已知中缀表达式，快速求出其他两种？

这里有两种方法。第一种就是瞪眼法。按照定义一步一步计算即可。

还有一种方法称为“表达式树”法。这里着重介绍。

所谓“表达式树”是指一棵二叉树，其叶节点为参与运算的元素，其他节点为运算符号的一棵树。左儿子表示第一个运算元素，右儿子表示第二个运算元素。

比如中缀表达式 4+(5+3)*8/2-6 的表达式树是：

.      -    
      / \   
     +   6  
    / \     
   4   /（这是除号）
      / \   
     *   2  
    / \     
   +   8    
  / \       
 5   3

请注意，括号不包括在内，因为优先级已经在节点的父子关系中体现。

对这棵树做前序遍历，可得到前缀表达式。同理，中序可得中缀（注意添加括号），后序可得后缀。这也解释了为什么“同一个前/后缀表达式不一定有唯一的一个中缀表达式与之对应”。因为它们本质上就是前/中/后序遍历。

哈夫曼编码及哈夫曼树

哈夫曼编码（Huffman Coding）是一种用于数据压缩的算法，由大卫·哈夫曼（David A. Huffman）在 1952 年提出。它通过给频繁出现的字符分配较短的编码，给不常见的字符分配较长的编码，从而有效地减少数据的总体长度。

对于同一组数据，最优的哈夫曼编码方案可能不止一种。

哈夫曼编码的基本步骤：

统计频率：
- 计算每个字符或符号在数据中出现的频率或概率。
构建优先队列：
- 将每个字符及其频率作为一对（字符，频率）插入优先队列。优先队列是按频率升序排列的。
构建哈夫曼树：
- 从优先队列中取出两个频率最小的节点。
- 创建一个新节点，其频率为两个取出的节点频率之和，并将这两个节点作为新节点的子节点。
- 将新节点插回优先队列中。
- 重复这个过程，直到优先队列中只剩下一个节点，即哈夫曼树的根节点。
生成编码：
- 从哈夫曼树的根节点开始，对每个左分支分配 0，对每个右分支分配 1（不一定非得是这样），生成每个字符的哈夫曼编码。
编码数据：
- 使用哈夫曼编码表将原数据转换为压缩后的数据。

示例：

假设有一组字符 g,h,i,j,k,l，它们对应的频率分别为 8 \%,14 \%,17 \%,20 \%,23\%,18 \%。

构建哈夫曼树：

首先确定节点：创建一个优先队列（也就是堆），将这些字符从小到大排序。

g: 8%
h: 14%
i: 17%
l: 18%
j: 20%
k: 23%

合并最小的两个节点，并插入队列：

i:  17%
l:  18%
j:  20%
gh: 22%
k:  23%

此时的哈夫曼树为：

.      gh: 22%
      /    \
    g: 8%   h: 14%

继续执行上述步骤，合并 i、l。

此时的队列：

j:  20%
gh: 22%
k:  23%
il: 35%

此时的哈夫曼树：

.     gh: 22%             il: 35%    
      /    \              /    \     
    g: 8%   h: 14%     i: 17%  l: 18%

继续合并 j、gh。

此时的队列：

k:   23%   
il:  35%
ghj: 42%

此时的哈夫曼树：

.        ghj: 42%         il: 35%    
        /    \            /    \     
     gh: 22%  j: 20%   i: 17%  l: 18%
    /    \                           
  g: 8%   h: 14%

以此类推，最后可得：

.             ROOT: 100%
            /            \
        ghj: 42%        ilk: 58%
       /       \       /        \
    gh: 22%  j: 20%  il: 35%   k: 23%
   /     \          /       \
 g: 8%   h: 14%   i: 17%   l: 18%

现在以节点 i 为例，从根节点到 i 的路径是“右左左”。

假如往右走为 1，往左走为 0，则 i 的编码为 100。

其他节点的编码：

g:000
h:001
j:01
i:100
l:101
k:11

当然最优的编码不止一种，也可以假设往右走为 0，往左走为 1。

组合数学

加法原理

定义：加法原理（也称为“总数原则”）用于计算多个互不重叠事件的总数。具体来说，如果一个问题可以被分解为若干个互不重叠的情况，并且这些情况之间没有交集，那么总的可能性就是各个情况可能性的总和。

形式化描述：

假设有一个任务可以被分解为 k 个互不重叠的事件，每个事件 E_i 的可能性数为 n_i（即事件 E_i 的总数）。那么任务的总可能性数是：

n_1 + n_2 + \cdots + n_k

示例：你有 3 件毛衣以及 2 件夹克衫，你要选一件来穿，一共有 3+2 = 5 种方案。

乘法原理

定义：乘法原理（也称为“连乘原则”）用于计算多个独立事件的总可能性数。具体来说，如果一个任务可以被分解为若干个连续发生的步骤，并且每一步的选择不影响其他步骤的选择，那么总的可能性就是每一步可能性的乘积。

形式化描述：

假设有一个任务可以被分解为 k 个步骤，其中第 i 步有 n_i 种选择。如果每个步骤的选择是独立的，那么总的可能性数是：

n_1 \times n_2 \times \cdots \times n_k

示例：你有 3 件上衣以及 2 条裤子，那么你一共有 3 \times 2 = 6 种方案。

排列

定义：排列指从一组元素中选取若干个元素，并考虑这些元素的先后顺序。

表示：从 n 个元素中选择 m(0 \le m \le n) 个元素，排列的方案数表示为 A^m_n。

公式：

A^m_n = \frac{n!}{(n-m)!}

### 组合定义：组合指从一组元素中选取若干个元素，**但不考虑这些元素的顺序**。表示：从 $n$ 个元素中选择 $m(0 \le m \le n)$ 个元素，组合的方案数表示为 $C^m_n$。公式： $$C^m_n = \frac{n!}{m!(n-m)!}$$ 特殊性质：$C^m_n = C^{n-m}_n$。你可以这么理解：我在 $n$ 个人中间选 $m$ 个人请他们吃饭，等同于我在 $n$ 个人中间选 $n-m$ 个人不请他们吃饭。 ### 技巧 #### 特殊优先把特殊情况的元素拿出来优先考虑。然后考虑一般情况。 #### 捆绑法如果有多个元素需要挨在一起，可以考虑把他们看作一个整体。不要忘记“这个整体”也有不同的排列情况。 #### 插空法如果有多个元素不能挨在一起，可以考虑先把其他元素排列好然后插空。 #### 隔板法要将 $n$ 个**相同的**元素划分为 $m$ 个集合，且集合不为空，求方案数。可以考虑在 $n$ 个元素中插入 $m-1$ 块板子。因为每个元素都相同，所以相当于只用考虑数量。该方案可行。 **如果元素不同，则不可以。同时集合不可以为空**。 #### 虚拟法问题同上。但是这次集合可以为空。可以考虑先在每个集合当中放入一个隐形的球，然后转化为：将 $n+m$ 个**相同的**元素划分为 $m$ 个集合，且集合不为空，求方案数。再来一个例子：你有 3 顶帽子、2 件上衣、4 条裤子以及 3 双鞋子。帽子可以选择不戴，求方案？帽子可选，那么相当于多出一顶“隐形的”帽子。相当于一共有 4 顶帽子。通过乘法原理易得方案：$4 \times 2 \times 4 \times 3 = 96$ 种方案。 # 算法 ## 排序算法常考的有插入排序、冒泡排序、快速排序、归并排序。小知识：排序算法的“稳定性”指的是在排序过程中，相等的元素在排序后的相对位置是否保持不变。比如，如果两个元素在排序前是**相等的**，并且它们的相对顺序是 A 在 B 前面，那么在排序后 A 仍然会在 B 前面。稳定性对于需要保持原始数据顺序的场景特别重要，例如在多次排序时。 --- ### 插入排序插入排序将数组分为两个部分，前半部分的元素已排好序，后半部分的元素待排序。每次进行时，先选择后半部分的第一个元素作为“插入元素”。然后将“插入元素”与其前面的元素逐一比较，找到合适的位置。接着将前面的元素向后移动一位，为“插入元素”腾出位置。最后插入“插入元素”到找到的位置。重复执行上述步骤，直到待排序部分为空。 - **时间复杂度：** $O(n^2)$。 - **空间复杂度：** $O(1)$。 - **稳定性：稳定。** 小优化：使用**二分查找**来确定“插入元素”在已排序部分中的插入位置。这个优化减少了比较次数，但对总复杂度影响有限。示例代码： ```cpp int n; int num[10005]; for(int i = 2; i <= n; i++){ int pos = lower_bound(num+1,num+i,num[i])-num,tp = num[i]; for(int j = i; j > pos; j--){ num[j] = num[j-1]; } num[pos] = tp; } ``` --- ### 冒泡排序每次检查相邻两个元素，如果前面的元素与后面的元素满足给定的排序条件，就将相邻两个元素交换。由于在算法的执行过程中，较小的元素像是气泡般慢慢“浮”到数列的顶端，故叫做冒泡排序。 - **时间复杂度：** $O(n^2)$。 - **空间复杂度：** $O(1)$。 - **稳定性：稳定。** 小优化：使用剪枝的思想，当没有相邻的元素需要交换时，排序就完成了。使用通用方法计算一个数组通过冒泡排序最少需要交换几次元素才能保证达成有序的状态：交换次数等于逆序对数。当然也可以反着来：**求逆序对数等于记录交换次数。** 示例代码： ```cpp int n,a[1005]; bool flag = 1; while(flag){ flag = 0; for(int i = 1; i < n; i++){ if(a[i] > a[i+1]){ flag = 1; swap(a[i],a[i+1]); } } } ``` --- ### 快速排序快速排序的工作原理是通过分治的方式来将一个数组排序。步骤如下： 1. 将数列划分为两部分，左半部分元素的范围小于右半部分元素的范围。且两部分元素范围交集为空。 1. 将两个部分分别再次执行上一步，直到每个部分只剩一个元素。 - **时间复杂度：** $O(n \log n)$，**但最坏情况下为** $O(n^2)$。 - **空间复杂度：不同实现方式空间不同**。 - **稳定性：不稳定。** 如何实现第一步？为了保证平均时间复杂度，一般是随机选择一个数 $m$ 来当作两个子数列的分界。之后，维护一前一后两个指针 $p$ 和 $q$，依次考虑当前的数是否放在了应该放的位置（前还是后）。如果当前的数没放对，比如说如果后面的指针 $q$ 遇到了一个比 $m$ 小的数，那么可以交换 $p$ 和 $q$ 位置上的数，再把 $p$ 向后移一位。当前的数的位置全放对后，再移动指针继续处理，直到两个指针相遇。示例代码： ```cpp int a[1005]; void qsort(int L,int R){ int p = L,q = R; int mid = a[L+(R-L>>1)]; while(p <= q){ while(a[p] < mid){ p++; } while(a[q] > mid){ q--; } if(p <= q){ swap(a[p],a[q]); p++,q--; } } if(L < q){ qsort(L,q); } if(p < R){ qsort(p,R); } } ``` 快速排序有更多的优化，这些优化可以保证最坏复杂度为 $O(n \log n)$。从 2000 年 6 月起，SGI C++ STL 的 `stl_algo.h` 中 `sort()` 函数的实现采用了优化后的快速排序算法。 **线性查找第 $k$ 大的数：** 在快速排序的「划分」结束后，原数列被分成了两部分，此时可以按照左边元素的个数和 $k$ 的大小关系来判断是**只**在左边还是**只**在右边递归地求解。这个方法的平均时间复杂度是 $O(n)$。 --- ### 归并排序运用了分治的思想。步骤如下： 1. 把原数组**平分**成两部分。 1. 重复第一步，直到分为若干个长度为 $1$ 的部分。 1. 合并分开的部分 - **时间复杂度：** $O(n \log n)$。 - **空间复杂度：** $O(n)$。 - **稳定性：稳定。** 归并排序的核心是合并。因为待合并的两个部分一定是有序的，所以我们可以定义两个指针 $i,j$，比较左半部分的第 $i$ 个元素与右半部分的第 $j$ 个元素，较小者放入合并后的数组，然后指向这个数的指针往后移。直到其中一个部分为空，再把另外一个部分的剩余元素全部放入合并后的数组。示例代码： ```cpp int a[1005],tp[1005]; void merge(int L,int mid,int R){ int Left = L,Right = mid+1,now = L; while(Left <= mid && Right <= R){ if(a[Left] < a[Right]){ tp[now++] = a[Left++]; }else{ tp[now++] = a[Right++]; } } while(Left <= mid){ tp[now++] = a[Left++]; } while(Right <= R){ tp[now++] = a[Right++]; } for(int i = L; i <= R; i++){ a[i] = tp[i]; } return; } void mergesort(int L,int R){ if(L < R){ int mid = L+(R-L>>1); mergesort(L,mid); mergesort(mid+1,R); merge(L,mid,R); } return; } ``` 计算逆序对：归并排序的合并操作中，每次后段首元素被作为当前最小值取出时，前段剩余元素个数之和即合并操作减少的逆序对数量。因此只需简单修改 `merge` 函数即可。 ![](https://cdn.luogu.com.cn/upload/image_hosting/7p5m22ev.png?x-oss-process=image/resize,m_lfit,h_500) ## 二分 ### 原理二分查找的对象必须满足**单调性**。以在一个升序数组中查找一个数为例，二分查找每次检查数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。 **二分的时间复杂度是 $O(\log n)$**。二分巧妙地把线性查找的时间复杂度 $O(n)$ 转化为 $O(\log n)$。 ### 细节处理二分的思路不复杂，但是细节需要注意。二分的基本代码是这样写的，它用于查找一个数是否存在于区间当中。若有则返回位置，否则返回 $-1$： ```cpp int l = 1,r = n,mid; while(l <= r){//1 mid = l+(r-l>>1);//2 if(num[mid] == target){ return mid; } if(num[mid] < target){ l = mid+1;//3 }else{ r = mid-1;//4 } } return -1; ``` 现在先注意到第 2 处。求 `mid` 的最好方法是代码当中这一种。如果使用 `mid = (l+r)>>1`，那么 `l+r` 可能会溢出。然后是第 1 处。这段代码中 l,r 表示的是闭区间，因此当 $l = r$ 时，区间 [l,r] 是有效的，应当继续循环。如果表示左闭右开区间，那么当 $l = r$ 时，区间 [l,r) 就是空区间，应该停止，不用等号。最后是第 3,4 处。如果 mid 指向的数比目标小，那么**它本身**与它前面的数都不可能是目标。因此剩下的区间就是 [mid+1,r]。反之同理。加减 1 的原因就在于排除 mid 本身这个数。理解了这一点之后，它的扩展理解起来就很简单。如果我们想要查找连续相同元素中最左边的位置，那么首先要确定区间的边界。当 mid 指向的数大于等于目标时，区间为 [l,mid]，否则为 [mid+1,r]。第一种情况不减 1 的原因是，有可能 mid 所指向的就是答案，因此不应该排除这里的 mid。那么最终 $l = r$ 的时候，区间 [l,r] 只剩下了一个数，没有必要继续循环，可以退出，因此代码中第 1 处不用等于。 ### 二分答案二分答案是在一个已知的有序数据集上进行二分查找，一般满足下列特征： - 答案在一个区间内，一般情况下，区间会很大，暴力超时。 - 非常容易判断一个答案的可行性。 - 该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。一般来说，这类题目的朴素做法的时间复杂度是 $O(n^2)$，其中第一个 $n$ 用于遍历答案区间，第二个 $n$ 用于检测答案的可行性。二分查找可以优化第一个 $n$。因为答案区间中的元素具有单调性，所以二分枚举答案，然后验证可行性即可。这样可以把时间降到 $O(n \log n)$。