CSP初赛知识点 学习笔记
$\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}(n2)&\mathcal{O}(n2)&\mathcal{O}(n2)&\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}(n2)&\mathcal{O}(n2)&\mathcal{O}(n2)&\mathcal{O}(n2)&&\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/