CSP-J 总结

杰杰

2026-08-18 15:51:55

发布于：香港

11阅读

0回复

0点赞

CSP-J 总结

内存数据

速度越快，通常容量越小，价格越高

$\tt{bit (b)} \rightarrow^8 \tt{Byte (B)} \rightarrow^{1024} \tt{KB} \rightarrow^{1024} MB \rightarrow^{1024} \tt{GB}$ ^[1]

其中 $\tt{bit}$ 为最小单位， $\tt{Byte}$ 为基本单位。

数值在计算机中是以补码的方式存储。

以下是原码反码补码的例子：

	正数	负数
原码	00001001	10001001
反码	00001001	11110110
补码	00001001	11110111

其中数字的第一个字符为符号位， $0$ 为正数， $1$ 为负数。

原码是原本的数值的二进制，第一位是符号位，例如十进制的 $3$ 的原码是 $00000011$ ，十进制的 $-3$ 的原码是 $10000011$ 。
反码是原码除了符号位的数值都取反，例如十进制的 $3$ 的反码是 $01111100$ ，十进制的 $-3$ 的补码是 $11111100$ 。
补码是在反码的基础上加 $1$ ，包含进位。例如十进制的 $3$ 的补码是 $01111101$ ，十进制的 $-3$ 的补是 $11111101$ 。

各类大小

有符号 $n$ 位二进制整数范围为 $[-2^{n-1},\space 2^{n-1}-1]$ 。
无符号 $n$ 位二进制整数范围为 $[0,\space 2^n-1]$ 。

图片大小计算公式为：

$宽 \times 高 \times 每位像素位数 \space(\div 8 \space\tt{Byte})$

例如， $1920 \times 1080$ 的 $24$ 位真彩色图像：

$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space$ $1920 \times 1080 \times 24 \div 8 = 6220800$ $\tt{B} \approx$ $5.93 \space \tt{MB}$

音频大小计算公式为：

$采样率 \times 量化位数 \times 声道数 \space(单声道为 1，双声道为 2) \times 时同 \space(\div 8 \space\tt{Byte})$

视频大小计算公式为：

$每帧图像大小 \times 帧率 \times 秒\space (\div 8 \space\tt{Byte})$

数据类型

char : $8$ 位， $1$ 字节
short : $16$ 位， $2$ 字节
int : $32$ 位， $4$ 字节
long long : $64$ 位， $8$ 字节
float : $32$ 位， $4$ 字节
double : $64$ 位， $8$ 字节

进制转换

简单的英文进制表示符：

字母	进制
$\tt{B}$	二
$\tt{O}$	八
$\tt{D}$	十
$\tt{H}$	十六

当 $\tt{0x}$ 作为开头是十六进制。

整数部分十进制转为 $k$ 进制（短除法）：

不断除 $k$ ，商 $0$ 为止，逆序除余。

例子：十进制的 $10$ 要转为二进制。 $10 \div 2 = 5 \space\cdots\space\cdots 0，5 \div 2 = 2 \space\cdots\space\cdots 1,2 \div 2 = 1 \space\cdots\space\cdots 0, 1 \div 2 = 0 \space\cdots\space\cdots 1$ ，所以二进制为 $(1010)_2 = (10)_{10}$ 。

小数部分十进制转为 $k$ 进制：

不断乘 $k$ ，小数为 $0$ ，正序取整。

例子：十进制的 $0.625$ 要转为二进制。 $0.625 \times 2 = 1.25 \cdots \space \cdots1，0.25 \times 2 = 0.5 \cdots \space \cdots0，0.5 \times 2 = 1 \cdots \space \cdots1$ ，所以二进制为 $(101)_2 = (0.625)_{10}$

整数部分 $k$ 进制转为十进制：

例子：二进制 $1001$ 要转为十进制。

$1_{8 (2^3)}0_{4 (2^2)}0_{2 (2^1)}1_{1 (2^0)}$

将原本得值乘上权值。

$1 \times 1 + 1 \times 8 = 1 + 8 = 9$

所以 $(9)_{10} = (1001)_2$ 。

小数部分 $k$ 进制转为十进制：

例子：二进制 $0.101$ 要转为十进制。

$0.1_{0.5(k^{-1})}0_{0.25(k^{-2})}1_{0.125(k^{-3})}$

将原本得值乘上权值。

$1 \times 0.5 + 1 \times 0.125 = 0.625$

位运算

位运算一共有 $6$ 种，都是在补码的形态下计算的，包括：

按位与 &
按位或 |
按位异或 ^
按位取反 ~
左移 <<
右移 >>

按位与

$a$	$b$	$a\space \& \space b$
0	0	0
1	0	0
0	1	0
1	1	1

按位或

$a$	$b$	$a\space \|\space b$
0	0	0
1	0	1
0	1	1
1	1	1

按位异或

$a$	$b$	$a$ ^ $b$
0	0	0
1	0	1
0	1	1
1	1	0

右移

$n >> m = \lfloor \frac{n}{2^m}\rfloor$

左移

$n << m = n \times 2^m$

特殊性质

$a\space | \space b \geq \max(a, b)$
$a\space \& \space b \leq \min(a, b)$
$a$ ^ $b \leq a + b$
$\sim x = - (x+1)$

链表和指针

链表有分单向链表和双向链表。

单向链表中间插入：（在 $a$ 节点后插入 $b$ 节点）

$\color{red}{①}$ $b\rightarrow next = a\rightarrow next$
$\color{red}{②}$ $a \rightarrow next = b$

单向链表删除节点：（删除 $b$ 节点）

$\color{red}{①}$ $a\rightarrow next = b\rightarrow next$

双向链表中间插入：（在 $a$ 节点后插入 $b$ 节点）

$\color{red}{①}$ $b\rightarrow next = a \rightarrow next$
$\color{red}{②}$ $a\rightarrow next = b$
$\color{red}{③}$ $b \rightarrow pre = a$
$\color{red}{④}$ $b \rightarrow next \rightarrow pre = b$

双向链表删除节点：（删除 $b$ 节点）

$\color{red}{①}$ $b \rightarrow pre \rightarrow next = b \rightarrow next$
$\color{red}{②}$ $b \rightarrow next \rightarrow pre = b \rightarrow pre$

栈和队列

栈

先进后出 $\tt{FILO}$

队列

先进先出 $\tt{FIFO}$

树

二叉树的性质

二叉树第 $i$ 层上最多有 $2^{i-1}$ 个节点。（根在 $1$ 层）
深度为 $k$ 的二叉树只多有 $2^k - 1$ 个节点。（根在 $1$ 层）
任意一根二叉树，若其叶子结点的数量为 $n0$ ，度为 $1$ 的数量为 $n1$ ，度为 $2$ 的数量为 $n2$ ，则 $n0$ 与 $n2$ 一定满足 $n0 = n2+1$ 和 $n = n0 + n1 + n2$ 。
具有 $n \space (n \geq 0)$ 个节点的完全二叉树的深度为 $\lfloor \log_2(n)\rfloor + 1$ 。
若将一颗有 $n$ $n$ 个节点的完全二叉树自顶而下，同一层自左向右连续给节点编号 $1, 2, \cdots, n$ $1, 2, \dots, n$ ，则：
- 针对编号为 $i$ $i$ 的节点：
  - 其左孩子的编号为 $2\times i\space (2 \times i \leq n)$
  - 其右孩子的编号为 $2\times i + 1\space (2 \times i+1 \leq n)$

树的遍历

先序遍历（根左右）
中序遍历（左根右）
后序遍历（左右根）

哈夫曼树

构造

先排序然后两两一组，得出了和之后将和插入，继续循环直至没有值。

带权路径长度

带权路径长度计算公式如下：

$带全路径长度 \space(WPL)=\sum(叶子权值 \times 叶子到根的边数)$

图

简单图为没有自环和重边。
多重图为有自环或重边。

完全无向图含有 $\frac{n \times (n-1)}{2}$ 条边。
有向完全图含有 $n \times (n - 1)$ 条边。

排序

冒泡排序
- 一趟确定一个最大值的最终位置
选择排序
- 一趟确定一个最小值的最终位置
插入排序
- 左边始终有序，当前值找到位置插进去，第 $k$ 趟后，前 $k + 1$ 个元素一定是有序的。

定义稳定性为：如果两个元素关键字相同，排序后他们的相对先后顺序不变。

排序算法	稳定性
冒泡排序	$\color{green}{✔}$
选择排序	$\color{red}{✖}$
插入排序	$\color{green}{✔}$
计数排序	半稳定

前中后缀表达式

中缀 → 后缀

例子为：

$a + b \times c - (d + e)$

对所有的运算按优先级增加括号：

$((a + (b \times c)) - (d + e))$

从内到外江运算符移动至操作数后：

$((a \space(b\space c\space\times)+) \space (d\space e\space +)\space -)$

去括号：

$a\space b\space c\times+ \space d\space e+-$

中缀 → 前缀

例子为：

$a + b \times c - (d + e)$

对所有的运算按优先级增加括号：

$((a + (b \times c)) - (d + e))$

从内到外江运算符移动至操作数前：

$(-\space(+\space a \space(\times \space b \space c)) (+\space d \space e))$

去括号：

$-\space+\space a \space\times \space b \space c+\space d \space e$

后缀 → 中缀

例子为：

$a\space b\space c\times+ \space d\space e+-$

从左到右遍历，如果遇见符号就将符号插入前面两个值得中间并加上括号：

$a\space (b \times c)\space + d\space e\space + -$

$(a + (b\times c))\space d\space e\space + -$

$(a + (b\times c))\space (d+ e)\space -$

$((a + (b\times c))- (d+ e))$

去掉可以去的括号：

$a + b\times c- (d+ e)$

前缀 → 中缀

例子为：

$-\space+\space a \space\times \space b \space c+\space d \space e$

从右到左遍历，如果遇见符号就将符号插入前面两个值得中间并加上括号：

$-\space+\space a \space\times \space b \space c\space (d + e)$

$-\space+\space a \space (b \times c)\space (d + e)$

$-\space (a +(b \times c))\space (d + e)$

$((a +(b \times c))- (d + e))$

去掉可以去的括号：

$a +b \times c- (d + e)$

后缀 → 前缀

现把后缀转为中缀，再将中缀转为前缀。

前缀 → 后缀

现把前缀转为中缀，再将中缀转为后缀。

排列组合

从 $n$ 个数中取 $m$ 个数的排列被记为 $A^m_n$ 或 $P^m_n$ 的排列。

全排列是当 $n=m$ 的特殊情况。

$A^m_n = n \times (n-1) \times (n-2) \times \cdots \times (n - (m - 1))$

$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space=\frac{n!}{(n-m)!}\space (0!=1)$