猫咪 023-526互联

CSP 2023 第一轮复习讲义

1. 竞赛环境

NOI 机试使用的操作系统是 Linux。

Linux 终端命令

在 Linux 中：

cd （change directory）命令用于更改当前工作目录（工作目录即所有命令在哪一个文件夹下生效）。命令语法是 cd 目标目录名。
- 返回上一级目录（父目录）使用的是 cd ..。
- 返回根目录使用的是 cd /。
ls（list）命令用于显示当前工作目录下的文件或者文件夹。命令语法是 ls [选项]。
- 可以查看包括隐藏文件的所有文件的是 ls -a（all）。
- 可以输出文件详细信息（例如大小、最后修改时间、权限）的是 ls -l（long）。
- 可以按文件修改时间排序的是 ls -t（time）。
- 可以将输出结果反转的是 ls -r（reverse）。
- 上述后缀可以一起使用，例如 ls -la 显示所有文件的详细信息。
- 可以将当前目录下的文件名打印到 tmp 文件中的命令是 ls > tmp。
cp（copy）命令用于复制文件。命令语法是 cp [选项] 源文件或目录目标文件或目录，例如要将 test.txt 文件复制一份到 Documents 文件夹，命令为 cp test.txt Focuments。
mv（move）命令用于将一个文件从一个目录移动到另一个目录。命令语法是 mv [选项] 源文件名目标目录名，例如要将 test.txt 文件移动到 Documents 文件夹，命令为 mv test.txt Focuments。
- mv 命令也可以用于给文件重命名（改名）。这种情况下命令语法是 mv 旧文件名新文件名，也即第二个参数是文件名而不是目录名。
- mv 命令具体做的事只取决于第二个参数是已存在的目录名还是文件名。例如你可以将一个目录改名，只需要使得新目录名并不在当前工作目录中已存在过即可。如果你要移动，也可以移动一个目录，只需要保证目标目录名是存在过的即可。
- 在使用 mv 做移动操作时，可以接受多个第一参数，表示将若干个文件移动到一个目录内，系统会接受最后一个字符串作为第二参数。
- -u （update）选项，希望只有源文件比目标文件的最后更改时间更新时才移动。
kill 命令可以终止（也称杀死）指定的进程。
killall 命令和 kill 类似，也是杀死进程用的，其区别是 killall 接受的参数是进程名字，而 kill 接受的参数是进程的编号，killall 会将所有名字等于接受参数的进程杀掉。可以类比在 multiset 中传入指针和名字的效果。
sudo （superuser do）前缀，用于获取管理员权限。
rm（remove）命令用于删除目录下的文件，命令语法是 rm [选项] 文件名/目录名。
- -i （interactive）选项，交互模式，在删除每一个文件的操作前有确认提示。
- -r （recursive）选项，参数传入目录名，递归地删除目录中的所有文件和目录。
- -f （force）选项，强制删除，忽略不存在的文件或目录。
- sudo rm -rf * 是一个火出圈的梗，在使用管理员权限加了 -r -f 两个选项之后删掉了根目录下的所有文件和目录，~~电脑清理大师~~。
rmdir 命令和 rm 类似，但是它传入的参数必须是一个空目录才能删除。
pwd 命令输出当前所在的子文件夹的全路径。例如目前在 F:\code 目录下，执行 pwd 命令就会输出 F:\code。
ps 命令用于查看当前正在运行的进程。
- Linux 下的进程有五种状态：运行、终端、不可中断、僵死、停止状态。其中 ps 查看的是正在运行的状态。
- ps 命令不仅可以查看现在正在运行的所有进程名称，还可以看到运行状态，例如进程号码、发起者、CPU 利用率、内存使用率等。
mkdir 命令用于创建一个新目录。该命令需要一个参数：新目录的名称。例如，若要在当前目录中创建一个名为 test 的新目录，可以使用以下命令：mkdir test。

g++ 命令

linux 中编译 C++ 程序的编译器是 g++。
g++ 的命令语法是 g++ [选项] 编译文件名 -o 可执行文件别名。
和很多 Linux 的命令不一样的是，g++ 的选项有单字符选项例如 -l，也有多字符选项例如 -ansi，但是不能直接将若干个单字符选项写在一起，例如 -pg 不等于 -p 和 -g 的组合。
如果 C++ 程序中使用了 math.h 中的函数，使用 g++ 编译时需要加入选项 -lm。-l 选项是指定需要的链接库名称的，而 m 是数学库 math.h 的意思。如上条所述的是，这个 -lm 选项是一个独立的选项。
其实 -o 也是一个选项，它是用来指定输出文件名字的。如果不加 -o，例如我直接 g++ H.cpp，它会把 H.cpp 编译出来的可执行文件默认叫做 a.exe，而加上 -o 你才能指定编译出来的东西叫什么。
-g 用来生成调试信息。
-c 的作用是编译生成目标文件（是二进制程序，也就是机器语言的程序，扩展名为 .o）而不是可执行文件。

Vim 命令

Vim 的一个设计理念就是让所有操作都在键盘下完成，避免使用鼠标，淡化方向键。因此设计了许多被称之为“命令”的快捷键。
Vim 编辑器有三个运行模式：普通模式、编辑模式和命令模式。其中刚打开的时候默认是普通模式，普通模式下键盘输入 i 或 a 等可以切换到编辑模式；普通模式键盘输入 : 可以切换到命令模式（会在屏幕最下端出现一行可以输入命令的命令行，出现一个 :）；按一下（或者多下）键盘 esc（Escape）键可以从其他模式切换到普通模式。
普通模式下的一些命令：
- hjkl：方向键，分别是左下上右。前面加数字，比如 4k 就是向上跳 $4$ 行，4h 就是向左 $4$ 格。
- w（word）：可以跳转到下一个单词的开头。b（beginning）：可以跳转到上一个单词的开头。2b：向上移动 2 个单词。e：同 w，但是光标停在单词末尾；ge：同 b，但是光标停在单词末尾。
- gg：跳转到文档最上方（第一行第一个字符），对应 vscode 的 Home。G：跳转到文档最下方，对应 vscode 的 End。
- Ctrl + U 对应向上翻页，Ctrl + D 对应向下翻页。
- f（find），后面跟一个字符，跳转到下一个该字符处，例如 fr 跳转到下一个 r 字符的位置。
- y（yank）用于复制，后面跟着表示范围的字符。普通模式下光标在某一个单词上的时候输入 yaw（yank all word），就可以复制一整个单词，然后 p（paste）粘贴。也可以 y4j，会复制当前行在内的下 $4$ 行（一共 $5$ 行）内容。之所以不用 copy 是因为将 c 留给了下面说的 change。yy 复制当前行内容。
- d（delete）删除内容，例如 d8j 删除了下 $8$ 行的内容，dfr 删除了到下一个 r 为止的内容。dd 删除一整行的内容。D 或者 d$，删除当前字符到行尾的所有内容。
- u（undo）撤销上一个操作。R（redo）在 vscode 上叫做重做，也就是撤销的撤销。
- 0 移动到行首；$ 移动到行尾。
- v（Visual）进入到可视模式，这个模式就是可以选中多个字符然后可以复制粘贴，没有特别的地方。
在编辑模式中，输入字符就是直接在代码中输入字符，但是有一些进入、退出编辑模式的快捷键，有 iacoIAO 这几个键。普通模式下光标指向一个字母，而编辑模式下光标指向两个字母之间的间隔。
- i （insert）在当前光标之前的间隔开始进入编辑模式。可以联想 list 在 insert 的时候会插入到当前 iterator 前面这个奇怪的特性。
- a （append）在当前光标之后的间隔开始进入编辑模式。
- I 从当前行开头进入编辑模式。
- A 从当前行末尾进入编辑模式。
- c（change）字面意义是修改内容，实际上就是删除当前的内容然后进入插入模式。例如 caw 会删掉目前的单词之后进入编辑模式。cc 会直接删除整行并进入编辑模式。c4j 会删除下 $4$ 行同时进入编辑模式。
- o 在当前行之后插入一行，并进入编辑模式。
- O 在当前行之前插入一行，并进入编辑模式。
因此例如你想要在行末进入编辑模式的话，可以有 $a、o退格、A 三种按键组合。
在命令模式中，命令以 : 开始。
- :q（quit）：退出 vim；:q!：强制退出并不保存修改。
- 要保存该文件，:w（write）。保存并退出：:wq。另外 ZZ 和 :x 也是保存并退出。

杂项

linux 中文件的权限：用 10 个字符表示，第 $2 \sim 10$ 个字符是有意义的，它们分为三组三个字符，前三个是所有者的权限，中间三个是与所有者在同一组的用户的权限，后三个是其他用户的权限。

例如：-rw-r--r--；-rw-r--r--；-rwx------。

每一组的三个字符，如果有对应权限该字符分别是 rwx，没有则是 -。r 表示 Read，也即拥有读取内容的权限。w 表示 Write，也即拥有写入内容的权限。x 表示 Execute，也即拥有执行该文件的权限。

对于目录来说，这三种权限的意义分别是：有浏览目录的权限；有删除、移动目录内文件的权限；有进入目录的权限。

如果“例如”中的三个都是文件权限的话，只有第三个是可以执行的文件。
linux 终端的快捷键：
- ctrl + c：可以强制终端正在运行的程序。
- ctrl + l：可以清空屏幕内容。
- 在 linux 的各个虚拟终端之间切换的快捷键是 Ctrl + Alt + Fn，也就是左下角同一行的那三个键（没有 Shift）。
- 从虚拟终端切换到桌面环境的快捷键是 Alt + F2。
linux 中区分文件和目录的大小写，例如目录 EAR 和目录 Ear 被认为是不同的目录。
linux 中拥有最高权限的用户是 root。
当前目录下有一个编译好的可执行文件 a.out，执行它使用的命令是 ./a.out。
要从某一个程序读入/要输出到某一个程序，使用 < 和 > 连接，但是其符号和 cin 相反，例如 cin >> x; 是读入，但是 ./prog_1 > 1.out 是要将程序输出结果保存到 1.out 的意思。
linux 中可以调试程序的程序是 gdb。
在 linux 系统中，文件夹中的文件可以与该文件夹同名。
shell 是一类程序的统称，只要这个程序能够按照用户的需求去调用操作系统就是 shell。NOI Linux 中默认使用的 shell 是 bash。
linux 中使用 time 命令计算一个程序运行时间，其输出的是三个时间：real, user, sys。
- real = cpu 用时 + 其他因素时间
- cpu 用时 = user + sys
- real > user + sys（单核情况下）。real 表示的是实际经过的时间，所以如果拿秒表和 time 一起对某个程序在单核 CPU 上的运行时间计时，那么秒表测的时间最接近 real 的时间。

2. 竞赛纪律

带入考场物品规定：参加者仅可以携带笔、饮用水和食品进入赛场，不得把手机、优盘等电子设备、书包、书籍、纸等带入赛场，如发现违规，不管是否使用，均按作弊处理。
考试前后：在考试正式开始前，参加者不得操作机器、使用鼠标键盘等设备。考试结束铃声响后，参加者立即停止答题，不关闭计算机，按照监考员的要求离开考场。
考试期间：不得提前交卷，考试结束后不得带走答卷和试卷。如需去洗手间、身体不适或其他帮助，参加者须举手示意。
作弊及处罚：凡在考试期间有抄袭、主动被抄袭、暗示、传递纸条、通信、夹带、替考等行为者，均按作弊处理。如被抄袭者知情但不报告，也同样以作弊处理。作弊者被禁赛三年，并全国通报。
监督和举报：如发现有违规行为，现场可向监考员举报，赛后可向 CCF 实名投诉（noi@ccf.org.cn）。
突发情况：考试期间如遇到特殊情况或突发事件，务必听从监考员指挥。

3. 计算机常识和 NOI 历史

一个完整的计算机系统包括硬件系统和软件系统。
目前微型计算机中采用的逻辑组件是大规模和超大规模集成电路。
软件和程序的区别是：软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序是软件的一部分。
IT 表示信息技术。
计算机中央处理器的简称为 CPU。
计算机内存的一般作用是存放当前正在运行或使用的程序和数据。
今年是 CCF-NOI 第 $5$ 次举办 CSP-J/S 计算机非专业级别软件能力认证。
ASCII 的含义是美国信息交换标准代码（American Standard Code for Information Interchange）。一个 ASCII 码只需要 $1$ 个字节就可以存放。
- 可显示字符的范围是 $32 \sim 126$。
- $32$ 是空格。
- $48 \sim 57$ 是阿拉伯数字。
- $65 \sim 90$ 是大写字母。
- $97 \sim 122$ 是小写字母。
RAM 是随机存取存储器（Random Access Memory），ROM 是只读存储器（Read-Only Memory）。RAM 在断电后数据会变化，ROM 在断电后数据不会变化。
LAN 是局域网（Local Area Network），WAN 是广域网（Wide Area Network），WLAN 是无线局域网（Wireless Local Area Network），其 W 不表示 Wide 而表示 Wireless。
计算机直接识别和执行的语言是机器语言。使用高级语言编写的程序称为源程序。
NOI 的中文含义是全国青少年信息学奥林匹克竞赛。

4. 排序算法

一般考的排序算法有八大排序算法，首先按照是否依赖比较进行排序分为两类。
排序的稳定性就是两个值相等的元素是否在最后不会交换顺序。

其实如果你拿 $(值, 位置)$ 二元组去排序，那么所有排序算法肯定都是稳定的，这里说的是如果在比较过程中不特意去选择位置较前的数据（可以感性理解一下，要使得它稳定的话，花费的代价是否非常不大，~~例如你只需要让算法的某一个细节是你钦定的那样，那就是稳定的~~。其实是否稳定对应的是一个具体算法，而一般一个算法名称对应了很多种实现细节，你只需要根据教科书的分类方式钦定一种实现细节记下来就好了 /cf）的话是否还能保持顺序。
非比较排序算法一般有计数排序和基数排序，都是稳定的。

计数排序是使用一个额外的计数数组 $C$，根据数组 $C$ 将原数组 $A$ 中的元素放到正确的位置。其算法流程是：
- 统计 $A$ 中每一个元素的出现次数。
- 给出现次数做前缀和。
- 反向填充目标数组 $B$，将 $A_i$ 放到 $B$ 中的第 $C_{A_i}$ 位，然后将 $C_{A_i}$ 递减。
所以区分计数排序和桶排序的时候，只要看到有对 $C$ 做前缀和的就一定是计数排序。如果是直接统计出现次数然后用一个 cnt 扫一遍过去的，那才是桶排序。

基数排序（Radix Sort）就是将数据分割出一些独立的位，使得高位比较出的大小完全覆盖低位比较出的大小，然后对每一位做计数排序。怎么分位其实没有那么死板，比如你要对一个 $10^9$ 之内的数据排序，你完全可以直接分成 $x \times 10^5 + y$。重要的是数据可以分割出独立的位。所以不是什么数据都可以基数排序的。
比较排序算法中，要掌握的有冒泡、插入、归并、快速、堆排、选择。前三个是稳定的、后三个是不稳定的。

冒泡排序的过程是第 $i$ 轮让第 $i$ 小的元素自动浮到最后去。只要你钦定在 $a= b$ 的时候不发生交换，那么显然是稳定的，时间复杂度 $O(n^2)$，最好情况 $O(n)$（带上检查那一步）。

插入排序的过程经常用理牌来比喻。考虑目前的一个有序序列里加入一个数，你只需从后往前去检查直到有一个数 $\le $ 它了，插到这个数后面就好了。知道算法流程之后显然知道是稳定的，因为你只会插入在第一个大于它的数前面。时间复杂度也是 $O(n^2)$ 的，因为插入一个逆序序列就是 $O(n^2)$ 的。最好情况也是 $O(n)$ 的，插入顺序序列就是。

归并排序也是比较熟知且广泛运用的算法了，只要你钦定前后在队首的数据一样大的时候选择前面的，就可以做到稳定，因此它也是稳定排序。时间复杂度是严格 $O(n \log n)$ 的。因为你必须每层都扫满 $n$ 个数，必须做 $O(\log n)$ 层。（这里就不考虑什么先检查一遍范围内是否有序的逃课方式了）

快速排序是一种平均情况下 $O(n \log n)$ 并且平均情况下能够跑得比其他 $O(n \log n)$ 算法快的排序算法，所以 sort 内部实现的是一种基于快速排序的算法。该排序方法采用分治策略，第 $i$ 轮找到第 $\cfrac{mid}{2}$ 位上的数作为基变量，然后按照“某个数 $<$ 和 $\ge$”的判断将其分为两边，然后递归下去。在这种实现细节下，就是一个不稳定的排序算法，因为如果你选择了一段相同的数的中间一个作为基变量，那么所有等于它的（不管原来在它左边还是右边）都会分到右边去。

堆排序就是直接使用堆这个数据结构，插入弹出。插入的时候每一个元素的下标已经被打的很乱了，它是不稳定的，时间复杂度 $O(n \log n)$。

选择排序就是每一次把 $a_{i + 1} \sim a_n$ 中的 $\min$ 跟 $a_i$ 交换一下，你可以在取 $\max$ 的时候，钦定交换第一个（和冒泡排序一个策略），但是你会把 $a_i$ 换到后面去，这样就铁定是不稳定的了。时间复杂度也是 $O(n^2)$，每一轮要找一次 $\min$。

5. 指针的运用

“存储器”的概念。文件柜 $\rightarrow $ 文件柜上的抽屉 $\rightarrow $ 抽屉上的编号，对应存储器（例如内存） $\rightarrow $ 存储单元（例如整型变量，也就是存储整数的单元） $\rightarrow $ 存储单元的地址（例如指向变量的指针）
关于指针，有两个运算符号：& 和 *。而 int *b; 中的 * 是声明 $b$ 是一个指针变量用的，和运算符号 * 不是同一个东西。& 一般被称为“取地址”运算。而 * 可以看成 & 的逆运算。
在一个内存条中，有一个整型变量 $a = 5$，放 $a$ 的地方假设叫做 $\mathtt{0x123}$，那么 &a 就等于 $\mathtt{0x123}$。我们可以 int *b; 定义一个指针 $b$。这个指针 $b$ 在内存条中也有一个相应的存放位置，姑且称 $\mathtt{0x234}$。那么我们可以（这里认为下面若干行是递进关系，前面的操作对后面有影响）：
- b = &a; 就是将 $b$ 赋值为 $a$ 的地址也即 $\mathtt{0x123}$。
- cout << b; 会输出 $\mathtt{0x123}$。cout << (*b); 会输出 $a$ 的值 $5$。
- cout << (&a); 会输出 $\mathtt{0x123}$。cout << (&b); 会输出 $\mathtt{0x234}$。
- 于是你还可以套娃，定义 c = &b，等等，因为指针它也是数据，也有存放的地方。
对于一个数组 $arr$，直接输出 arr 其实和 & (arr[0]) 的结果是一样的，也就是数组名等于首元素地址。同理 arr + 3 也就是 & (arr[3])。
- ```
int a[] = {5, 4, 3, 2, 1}; 
auto p = a + 3; 
auto q = &p; 
(*q) ++; 
auto k = *p; 
```
  观察这份代码，$*q$ 也就是 $p$，$*q$ 加 $1$ 对应的是 $p$ 从 $a+ 3$ 变成了 $a+4$，那么 $*p$ 就是 $a$ 数组的下标为 $4$ 元素 $1$ 了。

6. 数据的存储与计算

音频的数据量是由采样率 $\times $ 位深 $\times$ 时长 $\times$ 通道数计算的，其中采样率指的是每秒钟采多少个样，单位为 Hz（也就是次/秒）。位深指的是每一个采样点的位数，单位为 bit（位）。通道数就是要做多少个同时播放的音频。那么一段采样率为 44.1kHz，位深为 16 位，时长为 60 秒的双通道音频文件大小就是 $44100 \times 16 \times 60 \times 2 $ Bit。

如果有问数据率，数据率 $= $ 数据量 $\div $ 时间。
图像的数据量是由分辨率 $\times $ 位深计算的，其中分辨率就是图片长、宽的大小，位深则是一格有多少位。那么一个分辨率为 $800 \times 600$，$16$ 位的位图，它的大小就是 $800 \times 600 \times 16$ Bit。
视频的数据量可以看做图像的数据量乘以图像的个数，等于帧率 $\times$ 视频长度 $\times $ 图像数据量。帧率就是每一秒有多少帧，单位为 fps，也即 frames per second。24fps 也就是一秒钟有 24 帧的意思。

如果是有声音的视频文件可能还需要加上音频文件的大小。

如果给的是“音频码率、视频码率”，那么码率就是上面说的数据率，按照 (音频码率 + 视频码率) $\times$ 时长计算。
一些常用的文件扩展名：
- 图片：gif, jpg, png
- 视频：wmv, mov, mp4
- 音频：wav, mp3
- 文档：txt, doc, pdf...
- 压缩文件：jar, zip, rar, 7z
- 源代码：c, cpp, js, java
其中对于 wav, wmv 的 w 都是 windows，是微软开发的。m 是 media（媒体的意思），而 a 是 audio（音频的意思）。

7. 语言的类型

语言的基本分类：机器语言 $\rightarrow$ 汇编语言 $\rightarrow $ 高级语言。

机器语言编程的程序称为目标程序。

一般有名字的例如 BASIC 等都是高级语言。
高级语言按翻译时间不同分为编译型语言和解释型语言，编译型语言是先翻译成可执行文件，之后每次执行只需要找可执行文件即可；解释型语言是边解释边执行。

编译型语言有 C, C++, Go, Fortran, Delphi, Pascal, 汇编等。

解释型语言有 Python, Java, Javascript, Perl, Ruby 等。
高级语言按数据类型是否重要分为强类型语言和弱类型语言。

强类型语言有 C, C++, Go, PHP, Java, C#, python 等。

弱类型语言有 Rust, PHP, Javascript 等。

8. 哈夫曼编码

哈夫曼树的构造我们都知道是每次选择两个较小的叶子合并，这是因为一般要求的是编码为二进制。
建出哈夫曼树之后我们按照 trie 树的记号法则从上到下进行标号即可（而不是其他的什么方法）。我们的一个要求是不允许存在一个东西的编码是另一个的前缀。注意到我们要编码的所有东西在哈夫曼树上都是叶子，所以这种编码方式满足这个要求。

9. 一些分了八类还不能归类的小猫咪

取模：a % b 的定义就是 a - b * (a / b)。
一些基本的变量类型大小：char 1, short 2, int 4, long long 8, float 4, double 8, long double 16, void*（万能指针）8。
联合体：多个数据需要共享内存，每次只取其一生效的时候，使用联合体，节省内存和空间。

联合体的内存怎么算：要满足两个条件，一是大小大于等于占用字节最大的元素，二是必须能被其包含的所有基本类型的大小所整除。

例如：
```
union Mao {
    int n; //4 Bytes
    char s[11]; //1 Bytes * 11 
    double d; //8 Bytes
};
```
最大元素大小为 $11$，需要被 $1, 4, 8$ 整除，因此内存为 $16$。
结构体的内存怎么算：这个东西就不简单了，它是依靠对齐来算的。简单来说，从前往后，某一个变量占 $k$ 字节，那么它会选择大于目前被占用最后一个位置的且是 $k$ 的倍数的这一位存储。

举个例子：
```
struct Niang {
    char a; //1 Bytes
    int b; //4 Bytes
    short c; //2 Bytes
}; 
```
$a$ 会选择 $0$ 号内存存下（$0 \sim 0$）。$b$ 会选择 $\ge 1$ 的被 $4$ 整除的最小的 $4$ 号内存存下（$4 \sim 7$），$c$ 会选择 $8 \sim 9$，因此 Niang 的 size 为 $10$。

如果改成：
```
struct Niang {
    char a; 
    short c; 
    int b; 
};
```
$a$ 会选择 $0 \sim 0$，$c$ 会选择 $2 \sim 3$，$b$ 会选择 $4 \sim 7$，可见这样的话会改变 Niang 的 size 变成 $8$。

CSP 2023 J/S1, RP++！