CSP-J 总结
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
内存数据
速度越快，通常容量越小，价格越高
bit(b)→8Byte(B)→1024KB→1024MB→1024GB\tt{bit (b)} \rightarrow^8 \tt{Byte (B)} \rightarrow^{1024} \tt{KB} \rightarrow^{1024} MB \rightarrow^{1024} \tt{GB}bit(b)→8Byte(B)→1024KB→1024MB→1024GB [1]
其中 bit\tt{bit}bit 为最小单位，Byte\tt{Byte}Byte 为基本单位。
数值在计算机中是以补码的方式存储。
以下是原码反码补码的例子：
正数 负数 原码 00001001 10001001 反码 00001001 11110110 补码 00001001 11110111
其中数字的第一个字符为符号位，000 为正数，111 为负数。
原码是原本的数值的二进制，第一位是符号位，例如十进制的 333 的原码是 000000110000001100000011，十进制的 −3-3−3 的原码是 100000111000001110000011。
反码是原码除了符号位的数值都取反，例如十进制的 333 的反码是 011111000111110001111100，十进制的 −3-3−3 的补码是 111111001111110011111100。
补码是在反码的基础上加 111，包含进位。例如十进制的 333 的补码是 011111010111110101111101，十进制的 −3-3−3 的补是 111111011111110111111101。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
各类大小
有符号 nnn 位二进制整数范围为 [−2n−1, 2n−1−1][-2^{n-1},\space 2^{n-1}-1][−2n−1, 2n−1−1]。
无符号 nnn 位二进制整数范围为 [0, 2n−1][0,\space 2^n-1][0, 2n−1]。
图片大小计算公式为：
宽×高×每位像素位数 (÷8 Byte)宽 \times 高 \times 每位像素位数 \space(\div 8 \space\tt{Byte}) 宽×高×每位像素位数 (÷8 Byte)
例如，1920×10801920 \times 10801920×1080 的 242424 位真彩色图像：
\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×1080×24÷8=62208001920 \times 1080 \times 24 \div 8 =
62208001920×1080×24÷8=6220800 B≈\tt{B} \approxB≈ 5.93 MB5.93 \space \tt{MB}5.93 MB
音频大小计算公式为：
采样率×量化位数×声道数 (单声道为1，双声道为2)×时同 (÷8 Byte)采样率 \times 量化位数 \times 声道数 \space(单声道为 1，双声道为 2) \times 时同 \space(\div 8 \space\tt{Byte}) 采样率×量化位数×声道数 (单声道为1，双声道为2)×时同 (÷8 Byte)
视频大小计算公式为：
每帧图像大小×帧率×秒 (÷8 Byte)每帧图像大小 \times 帧率 \times 秒\space (\div 8 \space\tt{Byte}) 每帧图像大小×帧率×秒 (÷8 Byte)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
数据类型
* char : 888 位，111 字节
* short : 161616 位，222 字节
* int : 323232 位，444 字节
* long long : 646464 位，888 字节
* float : 323232 位，444 字节
* double : 646464 位，888 字节
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
进制转换
简单的英文进制表示符：
字母 进制 B\tt{B}B 二 O\tt{O}O 八 D\tt{D}D 十 H\tt{H}H 十六
当 0x\tt{0x}0x 作为开头是十六进制。
整数部分十进制转为 KKK 进制（短除法）：
* 不断除 kkk，商 000 为止，逆序除余。
例子：十进制的 101010 要转为二进制。10÷2=5 ⋯ ⋯0，5÷2=2 ⋯ ⋯1,2÷2=1 ⋯ ⋯0,1÷2=0 ⋯ ⋯110 \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 110÷2=5 ⋯ ⋯0，5÷2=2 ⋯ ⋯1,2÷2=1 ⋯ ⋯0,1÷2=0 ⋯ ⋯1，所以二进制为
(1010)2=(10)10(1010)_2 = (10)_{10}(1010)2 =(10)10 。
小数部分十进制转为 KKK 进制：
* 不断乘 kkk，小数为 000，正序取整。
例子：十进制的 0.6250.6250.625 要转为二进制。0.625×2=1.25⋯ ⋯1，0.25×2=0.5⋯ ⋯0，0.5×2=1⋯ ⋯10.625 \times 2 = 1.25 \cdots \space \cdots1，0.25 \times 2 = 0.5 \cdots \space \cdots0，0.5 \times 2 = 1 \cdots \space \cdots10.625×2=1.25⋯ ⋯1，0.25×2=0.5⋯ ⋯0，0.5×2=1⋯ ⋯1，所以二进制为 (101)2=(0.625)10(101)_2 = (0.625)_{10}(101)2
=(0.625)10
整数部分 KKK 进制转为十进制：
例子：二进制 100110011001 要转为十进制。
18(23)04(22)02(21)11(20)1_{8 (2^3)}0_{4 (2^2)}0_{2 (2^1)}1_{1 (2^0)} 18(23) 04(22) 02(21) 11(20)
将原本得值乘上权值。
1×1+1×8=1+8=91 \times 1 + 1 \times 8 = 1 + 8 = 9 1×1+1×8=1+8=9
所以 (9)10=(1001)2(9)_{10} = (1001)_2(9)10 =(1001)2 。
小数部分 KKK 进制转为十进制：
例子：二进制 0.1010.1010.101 要转为十进制。
0.10.5(k−1)00.25(k−2)10.125(k−3)0.1_{0.5(k^{-1})}0_{0.25(k^{-2})}1_{0.125(k^{-3})} 0.10.5(k−1) 00.25(k−2) 10.125(k−3)
将原本得值乘上权值。
1×0.5+1×0.125=0.6251 \times 0.5 + 1 \times 0.125 = 0.625 1×0.5+1×0.125=0.625
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
位运算
位运算一共有 666 种，都是在补码的形态下计算的，包括：
* 按位与 &
* 按位或 |
* 按位异或 ^
* 按位取反 ~
* 左移 <<
* 右移 >>
按位与
aaa bbb a & ba\space \& \space ba & b 0 0 0 1 0 0 0 1 0 1 1 1
按位或
aaa bbb a ∣ ba\space |\space ba ∣ b 0 0 0 1 0 1 0 1 1 1 1 1
按位异或
aaa bbb aaa ^ bbb 0 0 0 1 0 1 0 1 1 1 1 0
右移
n>>m=⌊n2m⌋n >> m = \lfloor \frac{n}{2^m}\rfloorn>>m=⌊2mn ⌋
左移
n<<m=n×2mn << m = n \times 2^mn<<m=n×2m
特殊性质
* a ∣ b≥max(a,b)a\space | \space b \geq \max(a, b)a ∣ b≥max(a,b)
* a & b≤min(a,b)a\space \& \space b \leq \min(a, b)a & b≤min(a,b)
* aaa ^ b≤a+bb \leq a + bb≤a+b
* ∼x=−(x+1)\sim x = - (x+1)∼x=−(x+1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
链表和指针
链表有分单向链表和双向链表。
单向链表中间插入：（在 AAA 节点后插入 BBB 节点）
①\color{red}{①}① b→next=a→nextb\rightarrow next = a\rightarrow nextb→next=a→next
②\color{red}{②}② a→next=ba \rightarrow next = ba→next=b
单向链表删除节点：（删除 BBB 节点）
①\color{red}{①}① a→next=b→nexta\rightarrow next = b\rightarrow nexta→next=b→next
双向链表中间插入：（在 AAA 节点后插入 BBB 节点）
①\color{red}{①}① b→next=a→nextb\rightarrow next = a \rightarrow nextb→next=a→next
②\color{red}{②}② a→next=ba\rightarrow next = ba→next=b
③\color{red}{③}③ b→pre=ab \rightarrow pre = ab→pre=a
④\color{red}{④}④ b→next→pre=bb \rightarrow next \rightarrow pre = bb→next→pre=b
双向链表删除节点：（删除 BBB 节点）
①\color{red}{①}① b→pre→next=b→nextb \rightarrow pre \rightarrow next = b \rightarrow nextb→pre→next=b→next
②\color{red}{②}② b→next→pre=b→preb \rightarrow next \rightarrow pre = b \rightarrow preb→next→pre=b→pre
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
栈和队列
栈
* 先进后出 FILO\tt{FILO}FILO
队列
* 先进先出 FIFO\tt{FIFO}FIFO
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
树
二叉树的性质
* 二叉树第 iii 层上最多有 2i−12^{i-1}2i−1 个节点。（根在 111 层）
* 深度为 kkk 的二叉树只多有 2k−12^k - 12k−1 个节点。（根在 111 层）
* 任意一根二叉树，若其叶子结点的数量为 n0n0n0，度为 111 的数量为 n1n1n1，度为 222 的数量为 n2n2n2，则 n0n0n0 与 n2n2n2 一定满足 n0=n2+1n0 = n2+1n0=n2+1 和 n=n0+n1+n2n = n0 + n1 + n2n=n0+n1+n2。
* 具有 n (n≥0)n \space (n \geq 0)n (n≥0) 个节点的完全二叉树的深度为 ⌊log2(n)⌋+1\lfloor \log_2(n)\rfloor + 1⌊log2 (n)⌋+1。
* 若将一颗有 nnn 个节点的完全二叉树自顶而下，同一层自左向右连续给节点编号 1,2,⋯ ,n1, 2, \cdots, n1,2,⋯,n ，则：
* 针对编号为 iii 的节点：
* 其左孩子的编号为 2×i (2×i≤n)2\times i\space (2 \times i \leq n)2×i (2×i≤n)
* 其右孩子的编号为 2×i+1 (2×i+1≤n)2\times i + 1\space (2 \times i+1 \leq n)2×i+1 (2×i+1≤n)
树的遍历
* 先序遍历（根左右）
* 中序遍历（左根右）
* 后序遍历（左右根）
哈夫曼树
构造
先排序然后两两一组，得出了和之后将和插入，继续循环直至没有值。
带权路径长度
带权路径长度计算公式如下：
带全路径长度 (WPL)=∑(叶子权值×叶子到根的边数)带全路径长度 \space(WPL)=\sum(叶子权值 \times 叶子到根的边数) 带全路径长度 (WPL)=∑(叶子权值×叶子到根的边数)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
图
简单图为没有自环和重边。
多重图为有自环或重边。
完全无向图含有 n×(n−1)2\frac{n \times (n-1)}{2}2n×(n−1) 条边。
有向完全图含有 n×(n−1)n \times (n - 1)n×(n−1) 条边。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
排序
* 冒泡排序
* 一趟确定一个最大值的最终位置
* 选择排序
* 一趟确定一个最小值的最终位置
* 插入排序
* 左边始终有序，当前值找到位置插进去，第 kkk 趟后，前 k+1k + 1k+1 个元素一定是有序的。
定义稳定性为：如果两个元素关键字相同，排序后他们的相对先后顺序不变。
排序算法 稳定性 冒泡排序 ✔\color{green}{✔}✔ 选择排序 ✖\color{red}{✖}✖ 插入排序 ✔\color{green}{✔}✔ 计数排序 半稳定
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前中后缀表达式
中缀 → 后缀
例子为：
a+b×c−(d+e)a + b \times c - (d + e) a+b×c−(d+e)
1. 对所有的运算按优先级增加括号：
((a+(b×c))−(d+e))((a + (b \times c)) - (d + e)) ((a+(b×c))−(d+e))
2. 从内到外江运算符移动至操作数后：
((a (b c ×)+) (d e +) −)((a \space(b\space c\space\times)+) \space (d\space e\space +)\space -) ((a (b c ×)+) (d e +) −)
3. 去括号：
a b c×+ d e+−a\space b\space c\times+ \space d\space e+- a b c×+ d e+−
中缀 → 前缀
例子为：
a+b×c−(d+e)a + b \times c - (d + e) a+b×c−(d+e)
1. 对所有的运算按优先级增加括号：
((a+(b×c))−(d+e))((a + (b \times c)) - (d + e)) ((a+(b×c))−(d+e))
2. 从内到外江运算符移动至操作数前：
(− (+ a (× b c))(+ d e))(-\space(+\space a \space(\times \space b \space c)) (+\space d \space e)) (− (+ a (× b c))(+ d e))
3. 去括号：
− + a × b c+ d e-\space+\space a \space\times \space b \space c+\space d \space e − + a × b c+ d e
后缀 → 中缀
例子为：
a b c×+ d e+−a\space b\space c\times+ \space d\space e+- a b c×+ d e+−
1. 从左到右遍历，如果遇见符号就将符号插入前面两个值得中间并加上括号：
a (b×c) +d e +−a\space (b \times c)\space + d\space e\space + - a (b×c) +d e +−
(a+(b×c)) d e +−(a + (b\times c))\space d\space e\space + - (a+(b×c)) d e +−
(a+(b×c)) (d+e) −(a + (b\times c))\space (d+ e)\space - (a+(b×c)) (d+e) −
((a+(b×c))−(d+e))((a + (b\times c))- (d+ e)) ((a+(b×c))−(d+e))
2. 去掉可以去的括号：
a+b×c−(d+e)a + b\times c- (d+ e) a+b×c−(d+e)
前缀 → 中缀
例子为：
− + a × b c+ d e-\space+\space a \space\times \space b \space c+\space d \space e − + a × b c+ d e
1. 从右到左遍历，如果遇见符号就将符号插入前面两个值得中间并加上括号：
− + a × b c (d+e)-\space+\space a \space\times \space b \space c\space (d + e) − + a × b c (d+e)
− + a (b×c) (d+e)-\space+\space a \space (b \times c)\space (d + e) − + a (b×c) (d+e)
− (a+(b×c)) (d+e)-\space (a +(b \times c))\space (d + e) − (a+(b×c)) (d+e)
((a+(b×c))−(d+e))((a +(b \times c))- (d + e)) ((a+(b×c))−(d+e))
2. 去掉可以去的括号：
a+b×c−(d+e)a +b \times c- (d + e) a+b×c−(d+e)
后缀 → 前缀
现把后缀转为中缀，再将中缀转为前缀。
前缀 → 后缀
现把前缀转为中缀，再将中缀转为后缀。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
排列组合
从 nnn 个数中取 mmm 个数的排列被记为 AnmA^m_nAnm 或 PnmP^m_nPnm 的排列。
全排列是当 n=mn=mn=m 的特殊情况。
Anm=n×(n−1)×(n−2)×⋯×(n−(m−1))A^m_n = n \times (n-1) \times (n-2) \times \cdots \times (n - (m - 1)) Anm =n×(n−1)×(n−2)×⋯×(n−(m−1))
=n!(n−m)! (0!=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) =(n−m)!n! (0!=1)
\space
Anm=Cnm×AmmA^m_n = C^m_n \times A^m_m Anm =*** ×Amm
***=n!m!(n−m)!=Cnn−mC^m_n = \frac{n!}{m!(n-m)!}=C^{n-m}_{n} *** =m!(n−m)!n! =Cnn−m
排列组合的方法
* 特殊优先
* 捆绑法
* 排除法
* 隔板法
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
有任何问题可以纠正！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. A→xB\tt{A} \rightarrow^x \tt{B}A→xB 表示一 B\tt{B}B 等于 xxx 个 A\tt{A}A。例如 Byte→1024KB\tt{Byte} \rightarrow^{1024} \tt{KB}Byte→1024KB 就表示 1KB1 \tt{KB}1KB 等于 1024 Byte1024\space\tt{Byte}1024 Byte。 ↩︎
