CSP-S1 2024 注意事项

---

Linux操作系统

• cd进入目录，cd ..返回上一级目录。
• ls查看目录，-a用于查看隐藏文件。
• mv修改文件名。
• >将结果打印到文件。
• ./文件名执行可执行文件。
• time ./文件名测量可执行文件运行时间。
• mkdir创建新目录。
• killall 进程名杀掉后台进程

---

寻址空间

32位系统最大支持 $4$ GB内存，64位系统很大。
指针变量：32位机上长度为 $4$ 字节，64位机上长度为 $8$ 字节。

---

存储空间

KB、MB等是以 $10$ 为底的，进率 $1000$；KiB、Mib是以 $2$ 为底的，进率 $1024$。

---

数据类型

• bool类型只有true和false两种值，不是 $0$ 和 $1$。
• short二字节，int=long四字节，long long八字节。

---

原码、补码和反码

原码

符号位+真值的绝对值。
$+3\rightarrow 0000\ 0011$
$-3\rightarrow 1000\ 0011$

反码

在原码的基础上，除符号位以外，各位取反。
$+3\rightarrow 0111\ 1100$
$-3\rightarrow 1111\ 1100$

补码

正数的补码是其本身。
$+3\rightarrow 0000\ 0011$
负数的补码是除符号位外，各位取反后加 $1$，即反码 $+1$。
$-3\rightarrow 1111\ 1101$

---

表达式

先根据结构将运算拆分成表达式树。

• 前序遍历 - 前缀表达式 - 波兰式
• 中序遍历 - 中缀表达式
• 后序遍历 - 后缀表达式 - 逆波兰式

---

运算顺序

详见OI-Wiki。

---

排序算法

稳定排序

在排序时不改变其序列，相等元素的相对位置不变。

对于序列 ${a_n}$，设其排序后为 ${b_n}$。
设 $a_{i_1}=b_{i_2},\ a_{j_1}=b_{j_2}$，对于所有的 $a_{i_1}=a_{i_2}$，若满足 $i_1<i_2$ 且 $j_1<j_2$，则称该排序算法是稳定的。

稳定的排序算法有插入排序、基数排序、归并排序、冒泡排序、计数排序等。
不稳定的排序算法有快速排序、希尔排序、简单选择排序、堆排序等。

---

图的着色

点着色

对无向图顶点着色，且相邻顶点不能同色。

边着色

对无向图的边着色，要求相邻的边涂不同种颜色。

---

拓扑排序

无向图，将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。

每次先将入度为 $0$ 的点删除后放入列表，再将其连接的所有边删除，新产生的入度为 $0$ 的点进入队列。重复直到队列为空。
若列表元素个数 $=n$，则说明原图无环，列表里即为已排序的点；
若列表元素个数 $<n$，则说明原图有环。

---

待学习

• CCF成立时间、NOI系列赛事开始时间等。
• 期望和概率。
• 信息学相关奖项。
• 信息学历史人物。
• 计算机基本结构和发展历程。