第 7 次社課講義

--- type: slide --- <style> .reveal .slides { font-size: 35px; } </style> # 南大附中資訊研究社 NFIRC 1st ## 第 7 次社課講義 2024/03/13 主講：Yude --- # 前情提要 ---- # 1.本學期主要內容資料結構與演算法難度提升、教學以概念為主實作只會簡單帶一下 ---- # 2.取消題單機制上學期題單狀況較不佳這學期取消題單機制但還是會收集題目放在講義中給想進步的人練習建議大家可以去把上學期題單都補完至少把上學期基礎語法掌握這學期聽懂演算法概念就好 ---- # 3.取消回饋表單不用再讓各位每節課都填表單了我們會從頭到尾開放一個回饋表單讓大家上完課如果想提供建議或有想說的話再自行填表單即可不過最後一次社課結束需要每個人填一個社團學期回饋表單 ---- # 4.聯合社課在南九校聯合寒訓過後有計劃要和其他學校辦聯合社課可以和其他學校一起上與資訊領域有關的多元課程詳細的內容跟細節還沒確定到時候有辦成功再請大家踴躍參加 ---- # 5.社費這學期社費一樣 300$ 今天下課就可以交了最晚收到第 9 次社課一樣會給收據 ---- # 6.資研周邊商品這學期社團內也有個計畫是推出南附資研周邊商品有人可以幫忙設計或有一些點子的話歡迎找我到時候如果真的成功做到再請大家幫我們多多宣傳 ---- # 7.下一屆幹部甄選我們會在這學期所有社課結束前找到下一屆的幹部資研社的未來靠你們了 --- ### 本學期預定課表 <center> 基礎資料結構與入門演算法 </center> | 節次 | 日期 | 課程內容 | 講師 | | --- | --- | --- | --- | | $7$ | $3/13$ | 複雜度分析｜暴力法與枚舉｜建表 | $Yude$ | | $8$ | $3/20$ | STL 基礎資料結構 | $YuDong$ | | $9$ | $4/3$ | sort 排序演算法 | $ShiYu$ | | $10$ | $4/17$ | 前綴和與差分｜單調隊列｜二分搜尋法 | $正宗老師$ | | $11$ | $4/24$ | 函式｜遞迴｜DP 基礎動態規劃 | $ShiYu$ | | $12$ | $5/1$ | (程式競賽 or 講座) && 聚餐 | | ---- # 目錄 1. 演算法入門 2. 複雜度分析 3. 暴力法與枚舉 4. 建表 --- ## 什麼是演算法這是 ChatGPT 給的答案 ![image](https://hackmd.io/_uploads/BJtlQ64h6.png) ---- ## 演算法 == 解決問題的方法 ---- ## 來看看有哪些演算法 - 枚舉演算法 - 排序演算法 - 搜尋演算法 - 分治演算法 - 貪心演算法 - 動態規劃 - 數論演算法 - 圖論演算法 - 最短路徑演算法 - 賽局理論 - 加密演算法 - 隨機演算法 - ...數不盡的各種演算法 ---- # 方法很多種不同的問題有不同的解決方法同個問題也有許多種解決方法該如何選擇較好的方法？或者說效率較快的方法？ ---- ## 舉個簡單的例子算出 1 到 100 的加總請給我個方法 ---- ## 最直接的方法直接 $1+2+3+4+5+...+99+100$ ---- ## 經過思考的方法觀察出每次頭尾相加都是 101 總共有 50 項頭尾相加所以答案是 $101 \times 50 = 5050$ ---- ### 甚至可以直接用公式解高一下數學第一章教的等差級數公式 $$ S_{n} = 1+2+3+ \cdots +(n-1)+n \\ $$ $$ = \sum_{i=1}^{n}i = \frac{n(n-1)}{2} $$ ---- ## 哪個方法比較好？ 1. 暴力加法 2. 公式解 ---- ## 你怎麼分辨的？執行時間？ ---- ## 「時間」是不準的受太多因素影響 - 硬體優劣 - 加總數字個數 - 實作細節 - 使用語言 - 同時執行的其它程式 - …etc ---- ## 但「計算量」是不變的不管你在什麼硬體下跑該算 100 次加法的，一次都不能少所以我們追求的是計算量越少越好而不是執行速度越快越好 ---- ## 如何評估一個演算法的計算量呢？ --- ## 複雜度分析（Complexity）用來分析一個演算法所需的計算量或記憶體空間 1. 時間複雜度：執行一份程式所需的計算量 2. 空間複雜度：執行一份程式所需的記憶體空間 ---- # 時間複雜度 - $O$ (Big-O)：最壞複雜度，上限(Upper bound) - $Ω$ (Omega)：最佳複雜度，下限(Lower bound) - $θ$ (Theta)：平均複雜度通常是看 Big-O，因為我們比較關心最糟情況程式執行多少次 ---- ## 各種常見的時間複雜度由小到大 | 名稱 | 時間複雜度 | | --- | --- | | 常數時間 | $O(1)$ | | 對數時間 | $O(\log n)$ | | 線性時間 | $O(n)$ | | 線性乘對數時間 | $O(n \log n)$ | | 平方時間 | $O(n^2)$ | | 指數時間 | $O(2^n)$ | | 階乘時間 | $O(n!)$ | 在估算複雜度中 $\log$ 皆以 2 為底、n! 階乘為 1 乘到 n ---- ## 用圖來理解 ![image](https://hackmd.io/_uploads/rJpdsEDnT.png =60%x) 可以發現當輸入個數很少的時候步驟數基本上不會差異太大但當輸入個數逐漸增加每個複雜度量級的差距會越來越大所以我們只想知道在資料量非常大的時候最糟情況如何最重要的是成長速度 ---- ## 剛剛兩種方法的複雜度 1. 暴力加法：$O(n)$ 2. 公式解：$O(1)$ ---- ## 時間複雜度計算原則看計算量也就是基本操作數次數會受資料量以及演算法影響只會紀錄最高次方項並忽略所有的係數例如一個程式需要執行 $3n^2 + 4n + 5$ 個基本操作我們會稱它的時間複雜度為 $O(n^2)$ ---- ## 基本操作以下每行都算一次基本操作 ```cpp= int i = 1; int j = 2; ++i; j++; i = i + j; i = i - j; i = i * j; i = i / j; i = i % j; ``` 不過這些操作之間在實際執行效率上還是有細微的差異但是我們都稱作 $O(1)$ 常數時間 ---- ## 透過舉例來分析時間複雜度 ---- ## 1 ```cpp= n = n * (n-1) / 2 ``` ---- ## 1 ```cpp= int n; cin >> n; n = n * (n-1) / 2 ``` ## $O(1)$ 常數時間這是一個用公式解求 1 ~ n 加總的程式不受資料量影響，不管 n 輸入多少都會執行減法、乘法、除法、賦值這幾個常數次的基本操作 ---- ## 2 ```cpp= int n; cin >> n; for(int i = 1; i <= n; i++){ sum += i; } ``` ---- ## 2 ```cpp= int n; cin >> n; for(int i = 1; i <= n; i++){ sum += i; } ``` ## $O(n)$ 線性時間這是一個用迴圈求 1 ~ n 加總的程式碼會受輸入的資料量影響 n 是多少就做多少次基本操作 ---- ## 3 ```cpp= int n; cin >> n; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ t += a[i] * a[j]; } } ``` ---- ## 3 ```cpp= int n; cin >> n; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ t += a[i] * a[j]; } } ``` ## $O(n^2)$ 平方時間 ---- ## 4 ```cpp= int i = 1; while(i < n) { i = i * 2; } ``` ---- ## 4 ```cpp= int i = 1; while(i < n) { i = i * 2; } ``` ## $O(\log n)$ 對數時間在 while 迴圈中，每次都將 i 乘以 2 乘完之後 i 距離 n 就越來越近了假設執行 $x$ 次 $i = i * 2$ 之後 $i \ge n$ 退出迴圈也就是說 $2^x \ge n$，那麼運用對數律可知 $x = \log_2 n$，因此時間複雜度為：O($\log n$) ---- # 我會算這個要幹嘛 ---- ## 當一個程式題目給了限制 ### 時間限制 ![image](https://hackmd.io/_uploads/ByomGe06a.png) ### 輸入資料量 ![image](https://hackmd.io/_uploads/H1ZMzl0ap.png) ---- 一般情況下電腦每秒大約可以執行 $10^8$ 次基本操作如果將題目限制以你寫的程式碼方法分析時間複雜度如果比 $10^8$ 高可能會 超時 (TLE) ---- ## 估算如何避免超時當你寫出一個 $O(n^2)$ 的程式想解決這個題目但當 $n = 2 \times 10^5$ 時總計算量約為 $4 \times 10^{10}$ 明顯超出電腦每秒執行次數 $10^8$ 導致 TLE 所以你只好優化你的程式碼改用其他演算法降低複雜度例如常見的二分搜尋演算法 (第 10 次社課會教到) 就可以將原本 O(n) 的複雜度優化成 $O(\log n)$ （或是用各種奇特的技巧壓常） ---- ## 透過輸入範圍估算時間複雜度 | 輸入範圍 | 時間複雜度 | | --- | --- | | $n \leq 10^{18}$ | $O(1) or O(\log n)$ | | $n \leq 10^9$ | $O(\sqrt n)$ | | $n\leq 10^6$ | $O(n) \ or \ O(n \log n)$ | | $n \le 5000$ | $O(n^2)$ | | $n \le 500$ | $O(n^3)$ | | $n \le 20$ | $O(2^n)$ | | $n \le 10$ | $O(n!)$ | ---- # 空間複雜度演算法執行時需要耗費多少的記憶體資源當你宣告了變數或陣列，使用到了記憶體空間 ```cpp= int N = 100; // 4byte int arr[100]; // 400byte int matrix[100][100]; // 40000byte char c; // 1byte double x = 9.99; // 8byte ``` ---- 每一題通常可以用 $10^6$~$10^7$ 個int 大部分題目不會刻意要求空間要夠小 ---- 時間複雜度與空間複雜度之間可以相互 trade off 就是你可以用較多的時間換取較少的空間或是用較多的空間換取較少的時間我們較常使用空間來換取時間 ---- 了解複雜度之後我們就可以在寫程式之前先分析自己的方法的時間複雜度判斷是否能在限制內執行完畢就可以避免寫完才發現 TLE --- ## 暴力法 Brute Force 暴力法是一種基本而直接的解題方式通常可以找到正確答案但時間複雜度有機會爆掉 ---- ## 電腦有著計算快又不會犯錯的優點做重覆的事情也不會出錯所以很適合做大量且單純的計算 ---- ## 暴力法可概分為： - 模擬：按照題目敘述模擬出結果 - 窮舉：將可能是答案的範圍，毫無遺漏地逐一窮舉 --- ## 模擬 - 依照題目模擬過程 - 用數字儲存現況 ---- 通常這種模擬題實作量都很大建議先掌握基礎語法再開始挑戰模擬題所以以下兩題例題聽不懂也沒關係 ---- ## 模擬法例題 1：[Kattis - Checkerboard](https://open.kattis.com/problems/thisaintyourgrandpascheckerboard) 您將獲得一個 $n \times n$ 棋盤其中每個方塊的顏色為黑色或白色如果滿足以下所有條件，則棋盤是正確的： - 每行的黑色方塊數量與白色方塊數量相同。 - 每列的黑色方塊數量與白色方塊數量相同。 - 沒有行或列有 $3$ 或多個相同顏色的連續方塊。輸入的字串會以 $B$、$W$來表示顏色 ---- ### 這題就像是模擬一個黑白棋盤 ### 讓我們一一判斷是否符合題目的要求 ---- 我們先開一個字串陣列來存棋盤 ```cpp= string x[n]; ``` ---- 先設定每一行列的黑白數為0 ```cpp= int r_B=0, r_W=0, c_B=0, c_W=0; ``` 因為每一個字串長度一樣可以直接把一個字串當作一列 ---- 寫一個函式來判斷棋盤是否正確 ```cpp= bool correct_grid(string x[], int n){ } ``` ---- 檢查同列的黑白數 ```cpp= if (x[i][j] == 'B') r_B++; else r_W++; ``` 檢查同行的黑白數 ```cpp= if (x[j][i] == 'B') c_B++; else c_W++; ``` 檢查是否有連續三個或更多同色 ```cpp= if (j < n - 2){ if (x[i][j] == x[i][j + 1] && x[i][j] == x[i][j + 2]) return false; if (x[j][i] == x[j + 1][i] && x[j][i] == x[j + 2][i]) return false; } ``` ---- 檢查黑白數是否相同 ```cpp= if (r_B != r_W || c_B != c_W) return false; ``` 如果都沒有不符合最後回傳 true ---- ## 模擬法例題 2： [ZJ F313](https://zerojudge.tw/ShowProblem?problemid=f313) $R \times C$ 的平面上有一些城市每天每個城市會向每個它相鄰的城市遷移 $\frac{人數}{k}$個人（整數除法，無條件捨去）請模擬出$m$天之後的結果，輸出人數最少及最多的城市人數。城市人數若為$-1$則代表該位置並非城市，不能由任何城市遷移至此。下圖是第一筆範例測資模擬的結果 ![image](https://hackmd.io/_uploads/SJsWxYvhp.png) ---- 開兩個陣列一個存總人數一個存遷移增加的人數判斷邊界後來計算$\frac{人數}{k}$ 動態紀錄相鄰城市數與城市人數變化 ```cpp= t = 0; p = 0; if(i!=0 && A[i-1][j]!=-1){ p += A[i-1][j]/k; t++; } if(j!=0 && A[i][j-1]!=-1){ p += A[i][j-1]/k; t++; } if(i!=r-1 && A[i+1][j]!=-1){ p += A[i+1][j]/k; t++; } if(j!=c-1 && A[i][j+1]!=-1){ p += A[i][j+1]/k; t++; } ``` ---- 搬出去的人 $= \frac{現在這個城市的人}{k} \times$ 相鄰城市數 ```cpp= num = A[i][j] / k * t; ``` 更新這天這個城市人數的變化為搬進來的 - 搬出去的 ```cpp= T[i][j] = p - num; ``` ---- 總之雖然模擬題非常麻煩常常需要用到二維陣列雙重迴圈等語法知識且實作量通常很大不過寫模擬題能穩固自己的基礎進步速度會很快 --- ## 窮舉 - 找出解可能存在的範圍 - 對範圍內每個東西，檢查它是不是解 ---- ### 最簡單的窮舉一個密碼系統，只能輸入四位數，猜正確密碼 ```cpp= for (int i = 0; i < 10000; ++i) { cout << setw(4) << setfill('0') << i << "\n"; } ``` 直接從 0000 暴力試到 9999 一定能在某個數字猜中密碼 ---- ## 窮舉法例題：[ZJ f312](https://zerojudge.tw/ShowProblem?problemid=f312) 有一個公司有$n$個員工，還有兩個工廠如果工廠一與工廠二分別有$X_1$與$X_2$個員工兩個工廠的收益$Y_1$,$Y_2$分別會是 $Y_1=A1\times X_1^2$ $+B_1\times X_1+C_1$ $Y_2=A2\times X_2^2$ $+B_2\times X_2+C_2$ 請你考慮所有分配員工的方式找出收益最大的組合，輸出最大收益。 ---- 已知 $X_1$ 可能範圍為 $0$ 到 $n$ 窮舉 $X_1$ 所有可能，每種得到 $X_2=n-X_1$ 代入求收益 $Y_1+Y_2$，取最大者 ```cpp= int ans = INT_MIN; // INT_MIN=-2147483648 for(int x1 = 0;x1 <= n;x1++){ int x2 = n-x1; ans = max(ans, a1*x1*x1 + b1*x1 + c1 + a2*x2*x2 + b2*x2 + c2); } ``` ---- ## 更聰明的窮舉：枚舉不需將所有可能性試過一遍可以先透過觀察與分析思考哪些不可能成為答案只需枚舉可能的答案就好 ---- ## 枚舉的應用給一整數 $n (n ≤ 10^{15})$，求出 $n$ 的所有因數 ---- ## 最簡單的方法窮舉出 1 ~ n 看有哪些數字能夠被 n 整除複雜度：$O(n)$ 但因為題目給 $n ≤ 10^{15}$ 顯然會 TLE ---- ## 思考看看只需要枚舉 $2 ∼ \sqrt{n}$ 就可以了因為假設 n = 10 找出因數 2，就可以順便找出因數 5 若持續找到因數 5 就重複了所以只需求出 $\leq \sqrt n$ 的所有因數就能同時順便找到 $> \sqrt n$ 的因數不用再繼續找下去了複雜度：$O(\sqrt n) = 10^{7.5} < 10^8$AC ---- ## 降低時間複雜度的方法我們常常會利用以下幾種方法來降低時間複雜度 1. 節省不必要的窮舉枚舉有可能的答案就好 2. 避免重複計算善用空間儲存某些特定的計算 3. 找規律或循環 4. 推導出一些數學性質 5. 搭配一些技巧來優化之後的運算例如：前綴和（第 10 次社課會教到） 6. 各種奇特壓常技巧（我們不會教） 7. ~~通靈出答案~~ --- ## 建表建表是個非常好用的實作技巧可以用來對付不那麼有規則、難以整理成迴圈的場合，讓程式碼變得較簡潔而不易出錯。 ---- ## 核心概念切分「資料」與「邏輯」 ---- ## 主要用途 - 讓程式碼變得簡潔、易於修改 - 降低出 bug 的風險 ---- ## 簡單建表例題：[Kattis Trik](https://open.kattis.com/problems/trik) 有三個杯子杯底朝上排成一橫排（左、中、右）一開始左杯放一顆球給一連串交換指令後，求球位在哪個杯子？ - A：交換左、中兩杯 - B：交換中、右兩杯 - C：交換左、右兩杯 ---- ## 最簡單的做法 ```cpp= bool l = true, m = false, r = false; for (i = 0; i < s.size(); i++){ if(cmd[i] == 'A'){ swap(left, mid); } else if(cmd[i] == 'B'){ swap(mid, right); } else{ swap(left, right); } } ``` ---- ## 缺點 - 缺乏彈性擴充性差 - 邏輯跟資料混在一起容易搞混 ---- ### 如果資料變成 10 個甚至更多該怎麼辦? - 10 個變數名稱 - $10 \times 9 \div 2$ 種交換方式 - 最後判斷球要寫好幾個 if ---- 如果我們用建表把邏輯跟資料拆開 ```cpp= const int cup_n = 3; const int change[cup_n][2] = {{0,1},{1,2},{0,2}}; bool ball[cup_n] = {true}; int main(){ string s; cin >> s; for(int i = 0; i < s.size(); i++){ int t = s[i] - 'A'; swap(ball[change[t][0]] , ball[change[t][1]]); } for(int i = 0;i < 3; i++){ if(ball[i]) cout << i+1 << "\n"; } } ``` 提升可讀性的同時也增加了擴充性 ---- ## 建表例題 2 [$APCS$ 2024/1/7 p2 蜜蜂觀察](https://zerojudge.tw/ShowProblem?problemid=m932) ---- ## 題目敘述蜜蜂在一個大小是 $m \times n$ 的蜂巢，並且每個蜂巢格上會有一個代表字母（大小或小寫英文字母）。輸入每步移動的方向，請輸出經過的路徑每格的代表字母，以及經過字元的種類數（大小寫相異），若經過時碰到牆壁該行動會停在原地。 ---- ## 題目中敘述蜜蜂的移動方位 ![image](https://hackmd.io/_uploads/rkvxDIPnp.png =30%x) 行走方向定義如圖： 0：右上 1：右方 2：右下 3：左下 4：左方 5：左上 ---- ## 範例輸入 ![image](https://hackmd.io/_uploads/HJEH2IPh6.png) ---- ## 轉成正確的移動方式後 ![image](https://hackmd.io/_uploads/B1iDwUv2a.png =40%x) 如果直接判斷的話需要很多判斷式這時候我們就能使用建表這個技巧 ---- ## 將移動方位以向量的形式轉換 | 方位 | ▵$x$ | ▵$y$ | | -------- |:----:|:----:| | $0:右上$ | 0 | -1 | | $1:右$ | 1 | 0 | | $2:右下$ | 1 | 1 | | $3:左下$ | 0 | 1 | | $4:左$ | -1 | 0 | | $5:左上$ | -1 | -1 | ---- ## 將向量的 x y 都存進陣列中 ```cpp= int step_x[6] = {0,1,1,0,-1,-1}; int step_y[6] = {-1,0,1,1,0,-1}; ``` 這樣每次移動都去查陣列裡的變化量就好了 ---- ## AC Code by ShiYu ```cpp= #include<bits/stdc++.h> using namespace std; #define ShiYu ios_base::sync_with_stdio(0);cin.tie(0) const int mv[6][2] = {{-1,0},{0,1},{1,1},{1,0},{0,-1},{-1,-1}}; int n,m; bool in_range(int x, int y) { return (0 <= x && x < m && 0 <= y && y < n); } signed main() { ShiYu; int k; cin >> m >> n >> k; vector<string> tb(m); for(auto &i : tb) cin >> i; int d,x=m-1,y=0,nx,ny; string ans; set<char> st; while(k--) { cin >> d; nx = x + mv[d][0]; ny = y + mv[d][1]; if(in_range(nx,ny)) { x = nx; y = ny; } char c = tb[x][y]; ans += c; st.insert(c); } cout << ans << "\n" << st.size() << "\n"; } ``` ---- ## 再來一題： [Kattis Astrological Sign](https://open.kattis.com/problems/astrologicalsign) 給日期，輸出星座 ![image](https://hackmd.io/_uploads/HyqhzvD3p.png) `幹這是殺小` ~~如果你很有耐心可以試試看硬幹慢慢判斷日期~~ ---- ## 有什麼方法? - 轉換日期 - 轉換月份 - 轉換星座 ---- 建月份星座表 ```cpp= const string month[] = {"Jan","Feb","Mar","Apr", "May","Jun","Jul","Aug", "Sep","Oct","Nov","Dec"}; const string star[] = {"Capricorn", "Aquarius", "Pisces","Aries", "Taurus","Gemini", "Cancer", "Leo", "Virgo", "Libra", "Scorpio", "Sagittarius", "Capricorn"}; ``` ---- 轉換日期先把英文月份轉成數字 ```cpp= int str_to_m(const string &s){ for(int i = 0; i < 12; i++){ if(s == month[i]) return i+1; } return -1; } ``` 再把?月?日改成數字 ```cpp= int res = str_to_m(m)*100 + d; ``` ---- 把星座日期也換成數字 ```cpp= const int intm[] = {120,219,320,420, 520,621,722,822, 921,1022,1122,1221, 9999}; ``` 記得注意邊界要設個上限 ---- ## AC Code by ShiYu ```cpp= #include <bits/stdc++.h> using namespace std; const string MONTH[] = {"Jan","Feb","Mar","Apr", "May","Jun","Jul","Aug", "Sep","Oct","Nov","Dec"}, NAME[] = {"Capricorn","Aquarius","Pisces","Aries", "Taurus","Gemini","Cancer","Leo","Virgo", "libra","Scorpio","Sagittarius","Capricorn"}; const int NUM[] = {120,219,320,420, 520,621,722,822,921, 1022,1122,1221,9999}; int month_to_int(const string& s) { for(int i=0;i<12;++i) { if(s == MONTH[i]) return i+1; } return -1; } signed main() { int t; cin >> t; while(t--) { int d; string m; cin >> d >> m; int n = month_to_int(m) * 100 + d; int ans; for(ans=0; n > NUM[ans]; ++ans); cout << NAME[ans] << "\n"; } } ``` ---- 時間夠的話來看一個有趣的技巧 ## 寫 code 自動建表 ---- ## 例題：[Kattis printingcosts](https://open.kattis.com/problems/printingcosts) 依照下表計算列印墨水費 ![image](https://hackmd.io/_uploads/H1VDuPPh6.png) ~~幹這又是殺小這麼多要複製多久~~ ---- ## 寫一個程式幫我們自動建表 ```cpp= char c; int n; while(cin >> c >> n) { cout << "{'" << c << "'," << n << "}" << ","; } ``` ![image](https://hackmd.io/_uploads/BJxAOZATT.png =40%x) 建表真快樂不用自己一個一個慢慢複製 ---- ## AC Code by ShiYu ```cpp= #include <bits/stdc++.h> using namespace std; #define ShiYu ios_base::sync_with_stdio(0),cin.tie(0); // 建表利用程式幫忙建 map<char,int> tb = {{'!',9},{'"',6},{'#',24},{'$',29},{'%',22}, {'&',24},{'\'',3},{'(',12},{')',12},{'*',17}, {'+',13},{',',7},{'-',7},{'.',4},{'/',10}, {'0',22},{'1',19},{'2',22},{'3',23},{'4',21}, {'5',27},{'6',26},{'7',16},{'8',23},{'9',26}, {':',8},{';',11},{'<',10},{'=',14},{'>',10}, {'?',15},{'@',32},{'A',24},{'B',29},{'C',20}, {'D',26},{'E',26},{'F',20},{'G',25},{'H',25}, {'I',18},{'J',18},{'K',21},{'L',16},{'M',28}, {'N',25},{'O',26},{'P',23},{'Q',31},{'R',28}, {'S',25},{'T',16},{'U',23},{'V',19},{'W',26}, {'X',18},{'Y',14},{'Z',22},{'[',18},{'\\',10}, {']',18},{'^',7},{'_',8},{'`',3},{'a',23}, {'b',25},{'c',17},{'d',25},{'e',23},{'f',18}, {'g',30},{'h',21},{'i',15},{'j',20},{'k',21}, {'l',16},{'m',22},{'n',18},{'o',20},{'p',25}, {'q',25},{'r',13},{'s',21},{'t',17},{'u',17}, {'v',13},{'w',19},{'x',13},{'y',24},{'z',19}, {'{',18},{'|',12},{'}',18},{'~',9}}; signed main() { ShiYu; // 利用程式幫忙建 // char c; int n; // while(cin >> c >> n) // { // cout << "{'" << c << "'," << n << "}" << ","; // } string s; while(getline(cin,s)) { int ans = 0; for(int i=0;i<s.size();++i) { if(s[i] != ' ') ans += tb[s[i]]; } cout << ans << "\n"; } } ```

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.