CSP-S 初赛知识点

Sheep_YCH · 2024-09-14 11:26:30 · 个人记录

基础知识

排序算法
图论（强连通，点双，边双，完全，二分，简单）
set 以及平衡树
时间复杂度

Some \space tricks

递归时间复杂度可以用主定理
完全图的边数为 \dbinom{n}{2}
求方案数可以用递推或者组合排列等解决
满二叉树的节点个数为 2 ^ h - 1
递归可以先弄清其作用的，然后再算
取模运算无论除数是正数还是负数，统统按正数算，取模结果的正负号与被除数相同。例如 a \space mod \space b 等价于 |a| \space mod \space |b| ，结果的符号 =a 的符号。
概率问题一般有以下两种情况：
- Q1：每一轮小A赢的概率为 P_A ，小B赢的概率为 P_B ，一共比 g 局，求小A至少赢 x 局的概率？
- A1：概率为 C_g^x * P_A{^x} * P_B{^{g - x}} + C_g^{x + 1} * P_A{^{x + 1}} * P_B{^{g - x - 1}} ……
- Q2：每一轮小A赢的概率为 P_A ，小B赢的概率为 P_B ，求小A先赢的概率？
- A2：设小A赢的概率为 x ，小B赢的概率为 P_B * x ，列出方程式 x + P_B * x = 1 ，解出 x 即为 ans 。

芝士

主定理

主定理的式子如下:

T(n) = aT(n/b)+f(n^d)

当 d < \log_ba ，时间复杂度为 O(n^{\log_b a})

当 d = \log_b a ，时间复杂度为 O(n^d \space \log \space n)

当 d > \log_b a ，时间复杂度为 O(n^d)

！！！注意：

当 f(n) 带 \log 时，应使用主定理的以下形式：

T(n) = aT(n/b)+O(n^d \log^k n)

d<\log_ba$ ，$O(n^{\log_ba} \log^kn)
d = \log_ba$ ， $O(n^d \log^{k+1}n)
d>\log_ba$ ，$O(n^d \log^k n)

数据类型

表示范围：

int:-2^{31} \space到\space 2^{31}-1

long \space long:-2^{63} \space到\space 2^{63}-1

char:-128 \space到\space 127 \space

short:-32768 \space到\space 32767

注意：在数据类型前加 unsigned ，则其只能表示 0 到其表示范围。例如 unsigned \space char 表示 0 到 255 。

占字节大小：

$bool$：$1$ 字节 $int$：$4$ 字节 $float$：$4$ 字节 $long long$：$8$ 字节 $double$：$8$ 字节 $unsigned$：跟后面所加的数据类型相同。例如 $unsigned \space char$：$1$ 字节。若 $unsigned \space int \space i=-1$ ，则 $i=2^{32}-1

排序算法

十大排序算法

Linux系统命令

关键知识：

ls：显示目录信息或者文件信息

cd：切换目录

find：搜索文件

mkdir：创建目录

cat：显示文件内容

cp：复制文件或目录

mv：移动或重命名文件或目录

more：分页显示文件内容

rm：删除文件或目录

head：显示文件开头内容

tail：显示文件末尾内容

vi：编辑（使用Vi编辑器打开文件）

ps：显示当前正在运行的进程

kill：终止指定进程

pwd：显示当前工作目录的绝对路径

set 和 multiset

定义：set<数据类型> s;

插入：s.insert(key_value)

删除某个值：s.erase(s.find(key_value)) 或者 s.erase(key_value)

s.lower_bound(key_value)：返回第一个大于等于key_value的定位器

s.upper_bound(key_value)：返回最后一个大于等于key_value的定位器

s.rbegin()：返回的值和 end() 相同

s.rend()：返回的值和 rbigin() 相同

set 和 multiset 的区别：set 不允许元素重复，multiset 允许元素重复。注意：set 会自动去重

set 的各种操作为 \log n ，例如 s.count() 的时间复杂度是 O(\log n)

set 的比较：按元素大小比，且只跟元素大小有关。

附：map 的比较规则：按照键值对进行比较。例如map<int,string> a, b; 会先按照 int 进行比较，再按照 string 进行比较

图论

无向连通图：无向图中每个节点可以互相到达

强连通图：有向图中的节点两两互相可达

边双连通图：无向图的点两两间都有两条不重合的路径

点双连通图：无向图点两两间存在两条不相交（没有公共点）的路径

割边（桥）：无向图中若删去 cnt 这条边，图不再连通，则称 cnt 为割边（桥）。

割点：无向图中若删去 u 这个点，图不再连通，则称 cnt 为割点。

××分量：表示一个图满足××的子图。无向图中这些子图由割连接，有向图中由点或边连接

稀疏图：一张图的边数远小于其点数的平方

稠密图：一张图的边数接近其点数的平方

自环：一条 (u,u) 的边

重边：两条 (u,v) 的边

简单图：不含自环和重边

多重图：含自环或重边

二分图：一个图的点分成两部分，每部分的点两两没有边连接

完全图：一个图的所有节点两两有边连接

极大连通分量：极大是要求该连通子图包含其所有的边（暗指无向图）

极小连通分量：极小是在保持连通的情况下使边数最少的子图（暗指无向图）

生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图

生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林。

树：根、父节点、儿子节点、兄弟节点、祖先、叶子节点、子树、左子树、右子树……

树的直径：最长的连通边

树的深度：层数

完全二叉树：一棵二叉树至多只有最下面两层的结点的度数可以小于 2 ，并且最下层的结点都集中在该层最左边的若干位置上

满二叉树：一颗二叉树所有节点的度要么为 0 ，要么为 2 ，且所有的叶子节点都在最后一层

节点的度：子树的个数

树的度：所有节点度中的最大值

节点的高度：从当前节点到最远叶子节点的路径上的节点总数

树的高度：所有节点高度中的最大值

另：树一定是二分图

最后祝 CSP-S 2024 第一轮 rp++！