CSP 初賽 2

日期： 2024年9月19日，甲辰八月十七
標籤： csp math oi note

補碼

計算機處理負數太麻煩，所以在模 $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（唯一）。

二分

看清楚區間表示方法。近兩年似乎越來越喜歡用左閉右開來表示區間了。