CSP初赛知识点 学习笔记

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

$\texttt{Linux}$ 基础操作

  1. 列出文件:ls
  2. 列出隐藏文件:ls -a
  3. 列出文件及大小:ls -l
  4. 重命名文件:mv old.cpp new.cpp
  5. 创建备份:cp file.cpp file.cpp.bak
  6. 运行程序:./test
  7. 计时运行:time ./test
  8. 重定向输入输出:test<in.txt>out.txt
  9. 查看目录地址:pwd
  10. 创建目录:mkdir dirx
  11. 切换上级目录:cd ..
  12. 切换目录:cd dirx
  13. 删除目录:rm -r dirx
  14. 查看所有进程:ps
  15. 杀掉后台进程:killall test
  16. 终止进程:kill $pid
  17. 强制终止运行:Ctrl-C
  18. 输入结尾(EOF):Ctrl-Z

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

  1. 生成调试信息:-g
  2. 生成目标文件:-c
  3. 生成可执行文件:-o
  4. 包含 cmath 库:-lm
  5. 显示警告:-Wall
  6. 缺氧、氧气:-O0-O2
  7. 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)&amp;\mathcal{O}(n2)&\mathcal{O}(n2)&amp;\mathcal{O}(n\operatorname{log}n)&amp;\mathcal{O}(n)&\mathcal{O}(n\operatorname{log}n)&\mathcal{O}(n\operatorname{log}n)&\mathcal{O}(d(n+r))\
\text{最坏情况}&\mathcal{O}(n2)&amp;\mathcal{O}(n2)&\mathcal{O}(n2)&amp;\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/

推荐阅读

热门相关:如果能少爱你一点   网游三国之城市攻略   我是仙凡   网游三国之城市攻略   重生成偏执霍少的小仙女