CSP初赛知识点学习笔记

2023-09-10 08:09 由 RainPPR 发表于 #其他

$\text{CSP } 初赛知识点$

$\texttt{Linux}$ 基础操作

列出文件：ls
列出隐藏文件：ls -a
列出文件及大小：ls -l
重命名文件：mv old.cpp new.cpp
创建备份：cp file.cpp file.cpp.bak
运行程序：./test
计时运行：time ./test
重定向输入输出：test<in.txt>out.txt
查看目录地址：pwd
创建目录：mkdir dirx
切换上级目录：cd ..
切换目录：cd dirx
删除目录：rm -r dirx
查看所有进程：ps
杀掉后台进程：killall test
终止进程：kill $pid
强制终止运行：Ctrl-C
输入结尾（EOF）：Ctrl-Z

$\texttt{G++/Gcc}$ 基础指令

生成调试信息：-g
生成目标文件：-c
生成可执行文件：-o
包含 cmath 库：-lm
显示警告：-Wall
缺氧、氧气：-O0，-O2
C++11/14：-std=c++11，-std=c++14

计算机设备结构

存储器

访问速度：$寄存器 > 高速缓存 > 内存\texttt{（ROM} + \texttt{RAM）} > 外存$，断电仅保留 $\texttt{ROM} \text{ } 和 \text{ } 外存$ 中的数据。

$\texttt{ASCII}$ 码

$\texttt{ASCII}$ 码（$\texttt{American Standard Code for Information Interchange}$）是美国国家交换标准代吗。

码域	字符	可见性
$0 \sim 31$，$127$	控制字符或通信专用字符	$\texttt{False}$
$32$	空格	$\texttt{False}$ 或 $\texttt{True}$
$48 \sim 57$	数字（$\texttt{0} \sim \texttt{9}$）	$\texttt{True}$
$65 \sim 90$	大写字母（$\texttt{A} \sim \texttt{Z}$）	$\texttt{True}$
$97 \sim 122$	小写字母（$\texttt{a} \sim \texttt{z}$）	$\texttt{True}$
其他（$33 \sim 47$，$58 \sim 64$，$94 \sim 96$，$126$）	特殊字符	$\texttt{True}$
拓展（$128 \sim 255$）	拓展的 $\texttt{ASCII}$ 码	$\texttt{N/A}$

（ $\texttt{PS: } 2^8 - 1 = 255，2^7 - 1 = 127$ ）

机器数与真值

原码：符号位 + 二进制串。

反码：对于一个正数，反码就是其原码；对于一个负数，反码就是除 符号位 外，原码的各位全部取反。

补码：对于一个正数，补码就是其反码（原码）；对于一个负数，补码等于 反码 + 1。

逻辑表达式的右结合性

逻辑表达式：由逻辑运算组合而成，返回值只有 $\texttt{True}$ 和 $\texttt{False}$，其中 $0$ 表示假、非 $0$ 表示真。

如果逻辑表达式由多个组合，需要 从右往左 依次判断，最后得出答案。这种性质被称为 右结合性。

例如：$\texttt{<表达式1>?<表达式2>:<表达式3>?<表达式4>:<表达式5>}$，
执行的时候是从表达式 $3$ 开始判断是否为真，然后从右往左执行每一个表达式，依次向上回溯，最后得出答案。

算法基础

数据结构基础

详见：https://www.luogu.com.cn/blog/334586/csp-pre-knowledge

数学基础

详见：https://www.luogu.com.cn/blog/334586/csp-pre-knowledge

排序算法

选择排序、冒泡排序、插入排序、快速排序、希尔排序、堆排序、归并排序、基数排序

基于比较：通过比较元素来排序数列，如冒泡排序，快速排序等。
不基于比较：不比较元素，通过其他方法（如hash）来进行排序，如基数排序等。

$
\begin{matrix}
&\text{选择排序}&\text{冒泡排序}&\text{插入排序}&\text{快速排序}&\text{希尔排序}&\text{堆排序}&\text{归并排序}&\text{基数排序}&\
\text{一般情况}&\mathcal{O}(n^{2)&\mathcal{O}(n}2)&\mathcal{O}(n^{2)&\mathcal{O}(n\operatorname{log}n)&\mathcal{O}(n})&\mathcal{O}(n\operatorname{log}n)&\mathcal{O}(n\operatorname{log}n)&\mathcal{O}(d(n+r))\
\text{最坏情况}&\mathcal{O}(n^{2)&\mathcal{O}(n}2)&\mathcal{O}(n^{2)&\mathcal{O}(n}2)&&\mathcal{O}(n\operatorname{log}n)&\mathcal{O}(n\operatorname{log}n)&\mathcal{O}(d(n+r))\
\text{最好情况}&\mathcal{O}(n^2)&\mathcal{O}(n)&\mathcal{O}(n)&\mathcal{O}(n\operatorname{log}n)&&\mathcal{O}(n\operatorname{log}n)&\mathcal{O}(n\operatorname{log}n)&\mathcal{O}(d(n+r))\
\text{空间复杂度}&\mathcal{O}(1)&\mathcal{O}(1)&\mathcal{O}(1)&\mathcal{O}(n)&\mathcal{O}(1)&\mathcal{O}(1)&\mathcal{O}(n)&\mathcal{O}(r)\
\text{稳定性}&\text{不稳定}&\text{稳定}&\text{稳定}&\text{不稳定}&\text{不稳定}&\text{不稳定}&\text{稳定}&\text{稳定}\
\end{matrix}
$

复杂度分析

符号：$T(n)$ 表示时间复杂度，$T(n) = $ 后跟一个符号，例：$T(n) = \mathcal{O}(n^2)$。

符号	英文名称	意义
$\Theta$	`theta`	等于
$\mathcal{O}$	`big-oh`	小于等于
$\Omega$	`big-omega`	大于等于（不常用）
$o$	`small-oh`	小于（不常用）
$\omega$	`small omega`	大于（不常用）

详见：https://oi-wiki.org/basic/complexity/