{%hackmd @hipp0\Hippotumuxthem %} <style> .text-center{ text-align: center; //文字置中 } .text-left{ text-align: left; //文字靠左 } .text-right{ text-align: right; //文字靠右 } </style> <style> .reveal .slides { text-align: left; font-size:30px; } </style> ## CPE 題目檢討 前三題我只會講個大概，題目沒有很困難，可以自行練習 --- ### 第一題 (給大家五分鐘看題目) https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10041.pdf ---- ### 題目 沒有仔細看題目的話可能會被騙 (這我) 題目大概: 選定任何一個當初始點，到每一個點的距離和要最小 ---- ### 思路 - 排序 - 暴力每一點 or 懂的話直接找中位數 - 然後得到距離和最小的點 --- ### 第二題 (給大家五分鐘看題目) https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/573.pdf ---- ### 題目 蝸牛白天可以爬 3，晚上睡覺時滑下來 1 。每一天爬的長度，都會比第一天爬的還要少 10%，也就是 3\*0.10 = 0.3。現在問你在第幾天這個蝸牛可以爬離這個井 (高度 $>H$ 才算爬出井口，$<0$ 才算掉入井底，這個訊息題目沒寫，對，當下要從側資判斷 = =) ---- ### 思路 - 利用模擬算出天數。注意每次上升長度的衰減是減個定值，並非每次去乘上一個比例 - 但需要注意每天上升的高度最低為 0。 (小關鍵) --- ### 第三題 (給大家五分鐘看題目) https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/11233.pdf ---- ### 題目 以下為複數形式的輸出說明： 若單字的複數形態屬於沒有規則的類型，請從表格輸出對應的複數型(表格會事先給定)。 否則，若單字以子音字母接"y"結尾，請以"ies"取代"y"。 否則，若單字以"o", "s", "ch", "sh", "x"結尾，請在字尾多加上"es"。 否則，請直接在字尾加上"s"。 ---- ### 思路 - 第一種用 map 一對一 - 再來一堆 if else 判斷剩下的幾種 - 若單字以子音字母接"y"結尾，請以"ies"取代"y"。 請注意是"子"音 --- ### 第四題 (給大家五分鐘看題目) https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/1118.pdf ---- 題目: S(n, m) = mS(n − 1, m) + S(n − 1, m − 1) 把 n 個數，分成 m 個聯集的總和 ---- ### 思路 (超簡單 DP) - 初始化: n 個數分成 1 個就是只有一種 n 個數 分成 n 個也是一種 - 看測資大小，可以直接簡單 top-down 的方式，然後用 map 紀錄算過的 (避免重複運算) - 或者你可以逆推回 button-up (記得用預處理，不要每次都重新處理) 下面使用 top-down 方法演示 ---- ### top-down 複雜度 $O(n^2)$ ```cpp= int dp[1005][1005]; int n, m; int S(int n, int m) { if (n == m || m == 1) return 1; if (dp[n][m] != 0) return dp[n][m]; int sum = (m * S(n - 1, m) + S(n - 1, m - 1)) % 2; dp[n][m] = sum; return sum; } void solve() { cin >> n >> m; cout << S(n, m) % 2 << endl; } // main 多筆測資處理 ``` --- ### 第五題 (給大家五分鐘看題目) https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/340.pdf ---- ### 題目 題目敘述: 1A2B 遊戲，給定一個正確答案，然後根據每個猜測輸出 XAYB ，A代表相同位置相同數字，B代表不同位置相同數字 ---- ### 思路 - 此題重點在於你可能會用到重複的數字，例如 答案 2222，猜測 1234，正確應該是 1A0B - 所以先簡單判斷 A 有幾個，並且記錄該位置已經被算過了 (不要重複計算) - 再來暴力計算 B 有幾個，同時要記得紀錄該位置被算過了 - 根據題目要求格式輸出(前面四個空格) ---- ### 簡單的實作而已 ```cpp= void solve(int n) { vector<int> ans(n); // 答案 for (int i = 0 ; i < n ; i++) cin >> ans[i]; while (true) { int A = 0, B = 0; vector<int> guess(n), ch(n); // 猜測 和 紀錄判斷位置 for (int i = 0 ; i < n ; i++) cin >> guess[i]; if (guess[0] == 0) return ; // 自己做剩下的主要判斷 cout << " (" << A << "," << B << ")" << endl; } } int main(void) { int test = 1, t; while (cin >> t) { if (t == 0) return 0; cout << "Game " << test << ":" << endl; solve(t); test++; } } ``` --- ### 第六題 (給大家十分鐘看題目) https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/580.pdf ---- ### 題目 題目: 有單一元素U和L，要求把n個元素排成一行同時要求至少有3個U在一起，問有幾種方法？ ---- ### DP 思路，需要仔細思考一下 - 全部排列數 - 不符合的組合數 - 定義 dp(i, j) 為 i 個元素 j = 0 代表以 L 結尾 j = 1 代表以 U 結尾 j = 2 代表以 UU 結尾 - 初始化 dp(1, 0) = dp(1, 1) = 1, dp(1, 2) = 0 ---- ### 實作 ```cpp= int dp[35][5]; void build() { dp[1][0] = 1, dp[1][1] = 1; dp[1][2] = 0; for (int i = 2 ; i <= 30 ; i++) { dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]; dp[i][1] = dp[i-1][0]; dp[i][2] = dp[i-1][1]; } return ; } int main(void) { build(); int t; while (cin >> t) { if (t == 0) return 0; cout << (1 << t) - dp[t][0] - dp[t][1] - dp[t][2] << endl; } } ``` ---- ### 暴力搜 這題有人說可以暴力搜 DFS 大家可以試試看? 但不是初衷所以不講 ---- ### 作弊小兔仔子 眼尖的大家可以發現，這題目只有 30 筆測資 而 CPE 是可以人工手輸測資，並且按下 人工test，會幫你產生答案 於是你可以先搞出答案後 ```cpp= vector<int> ans = {1, 12, 1234, 12345}; //這邊是亂打的，然後30個 void solve(int n) { cout << ans[n-1] << endl; } ``` --- ### 第七題 (1分鐘快速看一看) https://cpe.cse.nsysu.edu.tw/cpe/file/attendance/problemPdf/10229.pdf ---- ### 題目 題目: 要求輸出費式數列第 n 項 mod $2^m$ 注意: $0 ≤ n ≤ 2147483647$，所以不能用 $O(N)$ 的 DP 解 ---- ### $O(logN)$ 解 - 矩陣快速冪 上課講過囉! --- ### 結尾 祝大家考試順利!