<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 給的答案  ---- ## 演算法 == 解決問題的方法 ---- ## 來看看有哪些演算法 - 枚舉演算法 - 排序演算法 - 搜尋演算法 - 分治演算法 - 貪心演算法 - 動態規劃 - 數論演算法 - 圖論演算法 - 最短路徑演算法 - 賽局理論 - 加密演算法 - 隨機演算法 - ...數不盡的各種演算法 ---- # 方法很多種 不同的問題有不同的解決方法 同個問題也有許多種解決方法 該如何選擇較好的方法？ 或者說 效率較快的方法？ ---- ## 舉個簡單的例子 算出 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 ---- ## 用圖來理解  可以發現 當輸入個數很少的時候 步驟數基本上不會差異太大 但當輸入個數逐漸增加 每個複雜度量級的差距會越來越大 所以我們只想知道在資料量非常大的時候 最糟情況如何 最重要的是成長速度 ---- ## 剛剛兩種方法的複雜度 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$) ---- # 我會算這個要幹嘛 ---- ## 當一個程式題目給了限制 ### 時間限制  ### 輸入資料量  ---- 一般情況下 電腦每秒大約可以執行 $10^8$ 次基本操作 如果將題目限制以你寫的程式碼方法分析時間複雜度 如果比 $10^8$ 高 可能會 <span style="color:yellow">超時 (TLE)</span> ---- ## 估算如何避免超時 當你寫出一個 $O(n^2)$ 的程式想解決這個題目 但當 $n = 2 \times 10^5$ 時 總計算量約為 $4 \times 10^{10}$ 明顯超出電腦每秒執行次數 $10^8$ 導致 <span style="color:yellow">TLE</span> 所以你只好優化你的程式碼 改用其他演算法降低複雜度 例如常見的 二分搜尋演算法 (第 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 就是你可以用較多的時間換取較少的空間 或是 用較多的空間換取較少的時間 我們較常使用空間來換取時間 ---- 了解複雜度之後 我們就可以在寫程式之前 先分析自己的方法的時間複雜度 判斷是否能在限制內執行完畢 就可以避免寫完才發現 <span style="color:yellow">TLE</span> --- ## 暴力法 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$則代表該位置並非城市，不能由任何城市遷移至此。 下圖是第一筆範例測資模擬的結果  ---- 開兩個陣列一個存總人數 一個存遷移增加的人數 判斷邊界後來計算$\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}$ 顯然會 <span style="color:yellow">TLE</span> ---- ## 思考看看 只需要枚舉 $2 ∼ \sqrt{n}$ 就可以了 因為假設 n = 10 找出因數 2，就可以順便找出因數 5 若持續找到因數 5 就重複了 所以只需求出 $\leq \sqrt n$ 的所有因數 就能同時順便找到 $> \sqrt n$ 的因數 不用再繼續找下去了 複雜度：$O(\sqrt n) = 10^{7.5} < 10^8$<span style="color:green">AC</span> ---- ## 降低時間複雜度的方法 我們常常會利用以下幾種方法來降低時間複雜度 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$ 的蜂巢，並且每個蜂巢格上會有一個代表字母（大小或小寫英文字母）。 輸入每步移動的方向，請輸出經過的路徑每格的代表字母，以及經過字元的種類數（大小寫相異），若經過時碰到牆壁該行動會停在原地。 ---- ## 題目中敘述蜜蜂的移動方位  行走方向定義如圖： 0：右上 1：右方 2：右下 3：左下 4：左方 5：左上 ---- ## 範例輸入  ---- ## 轉成正確的移動方式後  如果直接判斷的話需要很多判斷式 這時候我們就能使用建表這個技巧 ---- ## 將移動方位以向量的形式轉換 | 方位 | ▵$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}; ``` 這樣每次移動都去查陣列裡的變化量就好了 ---- ## <span style="color:green">AC</span> 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) 給日期，輸出星座  `幹 這是殺小` ~~如果你很有耐心可以試試看硬幹 慢慢判斷日期~~ ---- ## 有什麼方法? - 轉換日期 - 轉換月份 - 轉換星座 ---- 建月份 星座表 ```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}; ``` 記得注意邊界 要設個上限 ---- ## <span style="color:green">AC</span> 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) 依照下表計算列印墨水費  ~~幹這又是殺小 這麼多要複製多久~~ ---- ## 寫一個程式幫我們自動建表 ```cpp= char c; int n; while(cin >> c >> n) { cout << "{'" << c << "'," << n << "}" << ","; } ```  建表真快樂 不用自己一個一個慢慢複製 ---- ## <span style="color:green">AC</span> 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"; } } ```