CSP-J/S 初賽沖刺
對于咱們信奧選手來說，會做的題要堅(jiān)決不丟分，不會做的題要學(xué)會盡量多拿分，這樣你的競賽之路才能一路亨通！
Linux 基礎(chǔ)操作
文件（文件夾）操作
列出文件：ls
列出隱藏文件：ls -a
列出文件及大小：ls -l
重命名文件：mv old.cpp new.cpp
創(chuàng)建備份：cp file.cpp file.cpp.bak
查看目錄地址：pwd
切換上級目錄：cd ..
切換目錄：cd dirx
創(chuàng)建目錄：mkdir dirx
刪除目錄：rm -r dirx
點(diǎn)擊查看代碼
運(yùn)行程序：./test
計(jì)時運(yùn)行：time ./test
重定向輸入輸出：test<in.txt>out.txt
查看所有進(jìn)程：ps
殺掉后臺進(jìn)程：killall test
終止進(jìn)程：kill $pid
強(qiáng)制終止運(yùn)行：Ctrl-C
輸入結(jié)尾（EOF）：Ctrl-Z
G++/Gcc 基礎(chǔ)指令
生成調(diào)試信息：-g
生成目標(biāo)文件：-c
生成可執(zhí)行文件：-o
包含 cmath 庫：-lm
顯示警告：-Wall
缺氧、氧氣優(yōu)化：-O0，-O2
C++11/14：-std=c++11，-std=c++14
計(jì)算機(jī)設(shè)備結(jié)構(gòu)
存儲器
訪問速度：寄存器 \(>\) 高速緩存 \(>\) 內(nèi)存（ROM + RAM）\(>\) 外存，斷電僅保留 ROM 和外存中的數(shù)據(jù)。
ASCII 碼
\(\texttt{ASCII}\) 碼（\(\texttt{American Standard Code for Information Interchange}\)）是美國國家交換標(biāo)準(zhǔn)代嗎。
| 碼域 | 字符 | 可見性 |
|---|---|---|
| \(0 \sim 31\)，\(127\) | 控制字符或通信專用字符 | \(\texttt{False}\) |
| \(32\) | 空格 | \(\texttt{False}\) 或 \(\texttt{True}\) |
| \(48 \sim 57\) | 數(shù)字（\(\texttt{0} \sim \texttt{9}\)） | \(\texttt{True}\) |
| \(65 \sim 90\) | 大寫字母（\(\texttt{A} \sim \texttt{Z}\)） | \(\texttt{True}\) |
| \(97 \sim 122\) | 小寫字母（\(\texttt{a} \sim \texttt{z}\)） | \(\texttt{True}\) |
| 其他（\(33 \sim 47\)，\(58 \sim 64\)，\(94 \sim 96\)，\(126\)） | 特殊字符 | \(\texttt{True}\) |
| 拓展（\(128 \sim 255\)） | 拓展的 \(\texttt{ASCII}\) 碼 | \(\texttt{N/A}\) |
（ \(\texttt{PS: } 2^8 - 1 = 255，2^7 - 1 = 127\) ）
機(jī)器數(shù)與真值
正數(shù)：［原碼 \(=\) 反碼 \(=\) 補(bǔ)碼］
負(fù)數(shù)：［反碼 \(=\) 除符號位外，原碼的各位全部取反］［補(bǔ)碼 \(=\) 反碼 \(+1\)］
邏輯表達(dá)式的右結(jié)合性
邏輯表達(dá)式：由邏輯運(yùn)算組合而成，返回值只有 \(\texttt{True}\) 和 \(\texttt{False}\)，其中 \(0\) 表示假、非 \(0\) 表示真。
如果邏輯表達(dá)式由多個組合，需要［從右往左］依次判斷，最后得出答案。這種性質(zhì)被稱為［右結(jié)合性］。
例子：
<表達(dá)式1>?<表達(dá)式2>:<表達(dá)式3>?<表達(dá)式4>:<表達(dá)式5>
執(zhí)行的時候是從表達(dá)式 \(3\) 開始判斷是否為真，然后從右往左執(zhí)行每一個表達(dá)式，依次向上回溯，最后得出答案。
算法基礎(chǔ)
數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)
詳見：https://www.luogu.com.cn/blog/334586/csp-pre-knowledge
數(shù)學(xué)基礎(chǔ)
詳見：https://www.luogu.com.cn/blog/334586/csp-pre-knowledge
復(fù)雜度分析
符號：\(T(n)\) 表示時間復(fù)雜度，$T(n) = $ 后跟一個符號，例：\(T(n) = \mathcal{O}(n^2)\)。
| 符號 | 英文名稱 | 意義 |
|---|---|---|
| \(\Theta\) | theta |
等于 |
| \(\mathcal{O}\) | big-oh |
小于等于 |
| \(\Omega\) | big-omega |
大于等于（不常用） |
| \(o\) | small-oh |
小于（不常用） |
| \(\omega\) | small omega |
大于（不常用） |
詳見：https://oi-wiki.org/basic/complexity/
排序算法
基于比較：通過比較元素來排序數(shù)列，如冒泡排序，快速排序等；
不基于比較：不比較元素，通過其他方法來進(jìn)行排序，如基數(shù)排序等。
| 選擇排序 | 冒泡排序 | 插入排序 | 快速排序 | 歸并排序 | |
|---|---|---|---|---|---|
| 平均復(fù)雜度 | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n \log n)\) | \(\mathcal{O}(n \log n)\) |
| 最壞復(fù)雜度 | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n \log n)\) |
| 最好復(fù)雜度 | \(\mathcal{O}(n^2)\) | \(\mathcal{O}(n)\) | \(\mathcal{O}(n)\) | \(\mathcal{O}(n \log n)\) | \(\mathcal{O}(n \log n)\) |
| 穩(wěn)定性 | 不穩(wěn)定 | 穩(wěn)定 | 穩(wěn)定 | 不穩(wěn)定 | 穩(wěn)定 |
| 空間復(fù)雜度 | \(\mathcal{O}(1)\) | \(\mathcal{O}(1)\) | \(\mathcal{O}(1)\) | \(\mathcal{O}(n)\) | \(\mathcal{O}(n)\) |
| 希爾排序 | 堆排序 | 基數(shù)排序 | |
|---|---|---|---|
| 平均復(fù)雜度 | \(\mathcal{O}(n^{1.3})\) | \(\mathcal{O}(n \log n)\) | \(\mathcal{O}(d \times (n + w))\) |
| 最壞復(fù)雜度 | \(\mathcal{O}(n \log n)\) | \(\mathcal{O}(d \times (n + w))\) | |
| 最好復(fù)雜度 | \(\mathcal{O}(n \log n)\) | \(\mathcal{O}(d \times (n + w))\) | |
| 穩(wěn)定性 | 不穩(wěn)定 | 不穩(wěn)定 | 穩(wěn)定 |
| 空間復(fù)雜度 | \(\mathcal{O}(1)\) | \(\mathcal{O}(1)\) | \(\mathcal{O}(w)\) |
常用縮寫
網(wǎng)絡(luò)
- 局域網(wǎng)：\(\texttt{LAN}\)（\(\texttt{Local Area Network}\)），\(\le 1 \text{ } \texttt{km}\)，結(jié)構(gòu)簡單、范圍小，短距離傳輸效率極高
- 城域網(wǎng)：\(\texttt{MAN}\)（\(\texttt{Metropolitan Area Network}\)），\(1 \sim 10 \text{ } \texttt{km}\)
- 廣域網(wǎng)：\(\texttt{WAN}\)（\(\texttt{Wide Area Network}\)），\(10 \sim 1000 \text{ } \texttt{km}\)
- 萬維網(wǎng)：\(\texttt{WWW}\)（\(\texttt{World Wide Web}\)），全球范圍
協(xié)議
-
傳輸相關(guān)
- 傳輸控制協(xié)議：\(\texttt{TCP}\)（\(\texttt{Transmission Control Protocol}\)）
- 用戶數(shù)據(jù)報協(xié)議：\(\texttt{UDP}\)（\(\texttt{User Datagram Protocol}\)）
-
應(yīng)用相關(guān)
- 超文本傳輸協(xié)議：\(\texttt{HTTP}\)（\(\texttt{Hyper Text Transfer Prtcl}\)）
- 超文本傳輸協(xié)議：\(\texttt{HTTPS}\)（\(\texttt{ - over Securesocket ayer}\)），增加了傳輸加密和身份認(rèn)證
- 文件傳輸協(xié)議：\(\texttt{FTP}\)（\(\texttt{File Transfer Protocol}\)）
- 對等網(wǎng)絡(luò)：\(\texttt{P2P}\)（\(\texttt{peer-t(w)o-peer}\)）
-
郵件相關(guān)
- 簡單郵件傳輸協(xié)議：\(\texttt{SMTP}\)（\(\texttt{Simple Mail Transfer Protocol}\)）
- 郵局協(xié)議 ：\(\texttt{POP}\)（\(\texttt{Post Office Protocol}\)）
- 郵局協(xié)議第三版 ：\(\texttt{POP3}\)（\(\texttt{Post Office Protocol - Version 3}\)）
- 交互郵件訪問協(xié)議：\(\texttt{IMAP}\)（\(\texttt{Internet Message Access Protocol}\)）
計(jì)算機(jī)設(shè)備結(jié)構(gòu)
- 隨機(jī)存儲器：\(\texttt{RAM}\)（\(\texttt{Random Access Memory}\)）
- 只讀存儲器：\(\texttt{ROM}\)（\(\texttt{Read Only Memory}\)）
數(shù)學(xué)問題
排列組合
-
排列 \(A(n, m)\)，舊時寫作 \(P(n, m)\)：
\(\displaystyle A(n, m) = \frac{n!}{(n - m)!}\)
-
組合 \(C(n, m)\)，也寫作 \(\displaystyle \binom{n}{m}\)：
\(\displaystyle C(n, m) = \frac{A(n, m)}{A(m, m)} = \frac{n!}{m!(n - m)!}\)
-
錯排列問題：
\(D_1 = 0\)，\(D_2 = 1\)，\(D_n = (n - 1)(D_{n - 1} + D_{n - 2})\)
-
Lucas 定理：
\(\displaystyle \binom{n}{m} = \binom{n \bmod p}{m \bmod p}\binom{n / p}{m / p}\)，其中 \(p\) 為質(zhì)數(shù)
-
Catalan 數(shù)：
\(\displaystyle C(n) = \binom{2n}{n} - \binom{2n}{n - 1} = \frac{1}{n + 1} \binom{2n}{n}\)
-
二項(xiàng)式定理：
\(\displaystyle (x + y)^k = \sum_{i = 0}^{k} C(n, i) x^i y^{k - i}\)
概率與統(tǒng)計(jì)
-
獨(dú)立事件（即兩事件的結(jié)果不會相互影響）：
\(P(A \cap B) = P(A) \times P(B)\)
-
古典公式：
\(P(A) = \dfrac{|A|}{S}\)
-
貝葉斯公式：
\(P(A \mid B) = \dfrac{P(A \cap B)}{P(B)}\)
-
數(shù)學(xué)期望：
\(\displaystyle E(x) = \sum_{i = 1}^\infty x_i p_i\)
線性代數(shù)
-
矩陣：
-
矩陣乘法 \(O(nmr)\)：
設(shè) \(A = (a_{ij})_{n \times m}\)，\(B = (b_{ij})_{m \times r}\)，
設(shè) \(C = A \times B = (c_{ij})_{n \times r}\)，
則 \(\displaystyle c_{ij} = \sum_{k = 1}^{m} a_{ik}b_{kj}\)如圖
方格路徑
題目：有 \(n \times m\) 的方格，從 \((1, 1)\) 出發(fā)，只能向右、下走，求走到 \((n, m)\) 的方案數(shù)。
-
遞推法
每個格子可以從上面和右面轉(zhuǎn)移過來，這是一個非?；A(chǔ)的 DP 問題：\(f(i, j) = f(i - 1, j - 1) + f(i - 1, j)\).
-
組合數(shù)學(xué)法
\(C(n + m - 2, n - 1)\) 或 \(C(n + m - 2, m - 1)\).
證明：一共要走 \(n + m - 2\) 步，其中 \(n - 1\) 個下，\(m - 1\) 個右，隨時都能向右走，證畢。
-
擴(kuò)展
從 \((a, b)\) 走到 \((c, d)\)，路徑數(shù)為 \(C(c - a + d - b, c - a)\) 或 \(C(c - a + d - b, d - b)\).
其他
-
對數(shù)恒等式：
*\(\log_kn = \dfrac{\log_xn}{\log_xk}\)
-
整數(shù)溢出：
signed 溢出是 Undefined Behavior（UB），是否取會模取決于編譯器；
unsigned 溢出是 Define Behavior（DB），在溢出時自動取模。 -
模等式：
- 對于 \(m \bmod n = p\)：
- 若 \(m > n\)，則 \(0 \le p <n\)；
- 若 \(m = n\)，則 \(p = 0\)；
- 若 \(m < n\)，則 \(p = m\)；
- 所以 \(p \le \min(m, n)\)
- 對于 \(m \bmod n = p\)：
圖片與視頻大小問題
拿分技巧
普通單選題就是一個題面一道題四個選項(xiàng)，主要是從五個方面來考察，分別是：計(jì)算機(jī)基礎(chǔ)常識、C++ 語法、基本算法理論、數(shù)據(jù)結(jié)構(gòu)、數(shù)學(xué)基礎(chǔ)。本文主要詳述一下這些題適用的拿分技巧，包括：排除法、特殊值代入法、極值法等，除此之外在一些代碼題中也可以用模擬法，模擬法會在下文詳述。
長篇代碼題就是給一段代碼，然后需要回答若干道與之相關(guān)的客觀題，給出的代碼可以是完好的（閱讀程序題），也可以是殘缺的（完善程序題）。對于這些題，我們能用的技巧有：模擬法、模仿相似代碼法、相關(guān)變量法、經(jīng)典算法實(shí)現(xiàn)、參考文字提示、特殊數(shù)據(jù)帶入法、排除法、反例法等。
排除法
這道題當(dāng)年很多同學(xué)不敢肯定 A 是對的，但是呢，由于 BCD 錯得離譜，所以就算你再不確定 A 是不是對的，由于其他選項(xiàng)都被排除了，也就只好選 A 了。
極值法
本題是一個抽象的規(guī)律題，理論上對于任何符合條件的數(shù)，這個規(guī)律都能成立，故而我們可以代入一些極為特殊的數(shù)，從而能直接簡化整個題目的難度等級，比如代入 \(n = 1\)，則數(shù)組被簡化為 \(1 \times 1\) 的數(shù)組，只有 \(1\) 個元素：a[0][0]。
此時，這個元素的前面沒有任何元素，即，有 \(0\) 個元素。然后把 \(i = 0\) 和 \(j = 0\) 代入四個選項(xiàng)，能夠快速得到 A 為 \(-1\)、D 為 \(1\) 都是不符合題意的選項(xiàng)，均可以快速排除。至于 B 和 C 選項(xiàng)，我們只需要再代入一個稍復(fù)雜的矩陣（如 \(3 \times 4\)）的就能輕松解決問題~
在上述實(shí)操中，我們使用了一個特殊極值，將題目化簡為了一個極為簡單的情況（從二維變成了一維），從而快速排除掉一半的選項(xiàng)，將隨機(jī)選擇的正確率從 \(25\%\) 一下就提高到了 \(50\%\)，這道題的原意本來是想考察我們對二維數(shù)組存儲的理解深度，但是如果你對二維數(shù)組的了解不深，通過這種極值簡化和排除的辦法，也能極大提高得分概率。
代入法
我們可以代入一些特殊的數(shù)據(jù)，來猜測什么樣的數(shù)組合并時，比較次數(shù)最多，并算出最多的比較次數(shù)。
比如，如果是 a 數(shù)組 \([1, 2, 3]\) 和 b 數(shù)組 \([4, 5, 6]\) 兩個數(shù)組，我們發(fā)現(xiàn)首先 \(1\)、\(2\)、\(3\) 分別需要和 \(4\) 比較一次后放入結(jié)果數(shù)組，然后由于 a 數(shù)組已經(jīng)沒有了可比較元素了，b 數(shù)組就直接按順序放入結(jié)果數(shù)組即可，所以比較次數(shù)只需要 \(3\) 次，即 n 次即可。
這樣顯然太順利了，而題目問的是至多多少次，所以我們可以構(gòu)造一個運(yùn)氣不太好的數(shù)組，如 a 為 \([1, 3, 5]\)，b 為 \([2, 4, 6]\)，這樣 \(1\) 需要和 \(2\) 比較，然后放入結(jié)果數(shù)組，\(2\) 需要和 \(3\) 比較、\(3\) 需要和 \(4\) 比較等等。
以此類推，合并這兩個數(shù)組需要比較 \(5\) 次，咱們可以隨意增大數(shù)組長度找規(guī)律，可知需要比較 \(2n – 1\) 次。而且由于除了最后一個元素外，每個元素進(jìn)數(shù)組前都要比較一次，比較得很充分，沒有其他情況能比這種情況比的次數(shù)更多了，故而得到本題答案選 D。這樣代入具體例子肯定比同學(xué)們在理論層面推要快，要直觀，更不容易錯，對吧？
模擬法
若變量個數(shù)過多，或程序變化過于復(fù)雜，隨手寫的過程中容易稍不留神就出錯時，則可以考慮設(shè)計(jì)表格來展示所有數(shù)據(jù)。模擬時，遇到常見的變量名和算法結(jié)構(gòu)時，可以大膽地根據(jù)變量名、算法結(jié)構(gòu)猜測其作用，再根據(jù)模擬的結(jié)果小心驗(yàn)證，這樣能夠提高做對的概率，并且極大減少我們模擬時的工作量~
常見的變量名如下：
對于常見的算法結(jié)構(gòu)，大家可以重點(diǎn)關(guān)注一些算法的典型結(jié)構(gòu)：二分、計(jì)數(shù)排序、連續(xù)字符判斷（字符轉(zhuǎn)數(shù)字）、鏈表、分治、二叉樹等。此處限于篇幅就不詳細(xì)列出每種結(jié)構(gòu)了，請大家一定要對照代碼，仔細(xì)總結(jié)。
雖然模擬法非常有用，但是比較依賴各位同學(xué)扎實(shí)的代碼能力，對于非常復(fù)雜的題，代碼能力弱的同學(xué)可能會模擬得非常吃力，還容易出錯，所以下述技巧其實(shí)才是咱們“騙分”的主力！
模仿相似代碼法
在我們編寫程序的時候，常常會出現(xiàn)相似度很高的代碼，它們通常是對不同的對象做相同或者相似的處理。這種現(xiàn)象常常出現(xiàn)在枚舉、分治或者樹結(jié)構(gòu)相關(guān)的程序上。當(dāng)我們需要補(bǔ)全語句時，參考與它相似的段落往往會給我們帶來很多提示和啟發(fā)。
方法舉例：
通過題目可知，本題代碼考察的是二叉樹結(jié)構(gòu)。在代碼里，你能發(fā)現(xiàn)相似的地方不？16行和17行的代碼是比較相似的吧？從 \(17\) 行的 a[root].rch 來看，我們不難猜出，這里應(yīng)該是要遍歷它的右子樹，那么 \(16\) 行應(yīng)該是要遍歷什么呢？自然是左子樹，所以標(biāo)號為 ② 這個空的答案呼之欲出：自然是 a[root].lch。
通過 \(16\) 行可知，左子樹的范圍是 lower_bound 到 cur，那么 ③④ 空右子樹的范圍是啥呢？肯定從 cur 左右開始，到 upper_bound。為啥是 upper_bound 呢？因?yàn)橐徊樽值渚椭溃?code>lower_bound 是下界（下限/最小值），所以與之對應(yīng)的詞，習(xí)慣上一般稱為 upper_bound（上界）。經(jīng)過此番嚴(yán)謹(jǐn)而大膽的猜測后，下面的幾題你會選了么？
當(dāng)然，你要是覺得用技巧的猜測過于大膽了，不放心的話，在時間富裕的情況下，可以再用模擬法代入具體數(shù)值小心驗(yàn)證一下。
經(jīng)典算法實(shí)現(xiàn)
很多題目，特別是完善程序題的題目都會涉及到一個或多個具體的算法，而很多算法是有明顯的經(jīng)典代碼特色的。因此，咱們可以利用算法本身約定俗成的寫法就能快速解題！
方法舉例：
本題的 \(1\)、\(2\) 空一看就是在求所有的約數(shù)，結(jié)合題目要求復(fù)雜度為 \(O(\sqrt n)\)，我們根據(jù)過往求解因數(shù)個數(shù)等的模板可知，\(1\) 空為 i * i（因?yàn)榧s數(shù)是成雙成對的，找到 \(\sqrt n\) 就行了），\(2\) 空為 n / i，這是為了避免完全平方數(shù)有一個無法成對的約數(shù)情況（如，\(36\) 的約數(shù) \(6\) 沒有與之配對的不同的約數(shù)了）。
本題的 \(3\)、\(4\) 空根據(jù)函數(shù)名和題目描述可知，其作用是求最大公約數(shù)的函數(shù)，結(jié)合題目要求復(fù)雜度為 \(O(\log \max(a, b))\)，不難發(fā)現(xiàn)，這是考輾轉(zhuǎn)相除法的遞歸版本，所以 \(3\) 為 return a、\(4\) 為 a % b。
反例法
此方法通常用在判斷題里，根據(jù)題目給的條件，只要能舉出一個反例，那么題目所描述的內(nèi)容就會不成立。
方法舉例：文章來源：http://www.zghlxwxcb.cn/news/detail-703743.html
比如，題目說：數(shù)組 a[i] 必須全為正整數(shù)，否則程序?qū)⑦x入死循環(huán)。那我們就可以將 \(0\) 或者負(fù)整數(shù)代入 a 數(shù)組，看看會不會死循環(huán)，只要能找到一個反例，那么這道題的描述的情況就不成立。當(dāng)然，由于只需要找到一個反例，所以我們可以代入盡可能簡單的數(shù)，比如 \(0\) 或 \(-1\)，這樣就能快速算出答案。文章來源地址http://www.zghlxwxcb.cn/news/detail-703743.html
參考資料
- CSP初賽知識點(diǎn)梳理 - 159號程序員 的博客
- OI 賽事與賽制 - OI Wiki
- CSP-J初賽之鑰：初賽核心考點(diǎn)分析
- 決勝CSP-J/S初賽，晉級復(fù)賽，這份實(shí)用拿分技巧快收好！
- 組合數(shù)學(xué)之方格路徑 - 知乎
到了這里，關(guān)于CSP初賽知識點(diǎn) 學(xué)習(xí)筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
