CSP 初赛 2

补码

计算机处理负数太麻烦，所以在模 $2^n$ 意义下处理运算，这样加法减法乘法都容易实现。

数字 $x$ 转补码，先判正负，若负，则 $2^n + x$ 即是其补码。如数是 -0000 1101(-13)，则加上 1 0000 0000，是 1 0000 0000 - 0000 1101 = 1111 0011。补码转数字同理。

当 $x < 0$ 时，注意到其补码 $2^n - (-x) = (2^n - 1) - (-x) + 1$，这个 $(2^n - 1)$ 每一位都是 1，所以做减法就相当于异或，把 $(2^n - 1) - (-x)$ 叫做反码。反码加一即是补码。

所以原码存在意义是什么？

由于模数是 $2^n$，取模直接截取后面 n 位即可，省去了判断符号的困扰，提高了运算效率。

主定理

每年必忘。

对于 $T(n) = aT(\frac{n}{b}) + f(n)$。先计算 $c_{\text{crit}} = \log_{b}a$，是划分 $aT(\frac{n}{b})$ 和 $f(n)$ 谁占主导地位的标志。

1. 若 $f(n) = O(n^c)$，且 $c < c_{\text{crit}}$，则 $aT(\frac{n}{b})$ 占主导地位，复杂度为 $\Theta (n^{c_{\text{crit}}})$。
2. 若 $f(n) = \Theta(n^{c_{\text{crit}}}\log^{k}n)$。
   1. $k > -1$，常见情况，$T(n) = \Theta(n^{c_{\text{crit}}}\log^{k+1}n))$。
   2. $k = -1$，$T(n) = \Theta(c^{c_{\text{crit}}}\log\log n)$。
   3. $k < -1$，$T(n) = \Theta(c^{c_{\text{crit}}})$。
3. 若 $f(n) = \Omega(n^c)$ 且 $c > c_{\text{crit}}$，且满足 $af(\frac{n}{b}) \le kf(n)$（regularity condition），则 $f(n)$ 占主导地位，复杂度 $\Theta(n^c)$。

sizeof

union，其所有成员在同一时刻只有一个有用。所以其占用内存大小取决于占用内存最大的成员类型。类似功能还有 std::variant，但是是 C++17 的内容。

enum，将内部所有项自动编号。如果有等号则用等号的值，否则用前一项的值加一。如果标注了类型，则就是此类型之大小，否则不固定，根据其中存储值设置，如果 4 字节能存储，则不超过 4 字节，否则是 8 字节。

SCP-S 2023 的第 15 题目：

enum E {
    CardA = 0, CardB = 1,
    CardC = 2, CardD = 142857
} e;

这个 CardD 是 142857，2 字节存不下，4 字节能存下，则一定是四个字节，如果没有 CardD，则 1，2，4 字节都有可能，然而不会是 8 字节。

排序

1. 选择排序：每次在待排序串行中选取最小值。复杂度 $O(n^2)$。稳定。
2. 冒泡排序：有实现特判一轮排序没有交换就退出。复杂度最优 $O(n)$，平均和最坏 $O(n^2)$。稳定。
3. 插入排序：未排序串行中选取一项，插入到已排序串行的合适位置。复杂度最优 $O(n)$，最差 $O(n^2)$。
4. 希尔排序：存在合适的 d 选取方式使得复杂度为 $O(n\log^2 n)$，最优 $O(n)$。
   1. 按照间距 d，将串行划分为若干子串行
   2. 排序各个子串行（插入排序）
   3. 缩小 d。
5. 堆排序：类似选择排序，每次从堆中选取最小值，复杂度 $O(n\log n)$，不稳定。
6. 归并排序：$O(n\log n)$，稳定。
7. 原地归并排序：$O(n\log^2 n)$，稳定。然而我不会原理。
8. 快速排序：平均 $O(n\log n)$，不稳定。
9. 计数排序：基于值域，记每个元素出现次数，根据出现次数计算排名。容易和桶排序搞混。$O(n + V)$，稳定。
10. 基数排序：对于值划分为若干关键字，依次对关键字排序。复杂度稳定性与内部对关键字排序方法有关。
    1. 如果先对第一关键字排序，则是 MSD Radix Sort。排序后关键字相同的递归下去排序。
    2. 如果先对最低关键字排序，则是 LSD Radix Sort。要求内部排序稳定。大多数人应该常写的这个。
11. 桶排序：根据值域将数字划分为若干区间，对各个区间分别排序。

基于比较的排序最坏复杂度下界是 $O(n\log n)$ 的。不妨假设是排列，有 $n!$ 种可能性，每次比较结果有两种（大于或小于），若每次比较都能将状态数缩小一半，复杂度就是 $O(\log n!) = O(\log n^n) = O(\log_{n} n^n \log n) = O(n \log n)$。

VIM

考这玩意有用吗？

XOR

x ^= x << k 是个双射。末 k 位 x 和原来的 x 是相同的，容易从一个 x 反推回原来的 x（唯一）。

二分

看清楚区间表示方法。近两年似乎越来越喜欢用左闭右开来表示区间了。