<!-- 注意上面三行 --> # CPE 衝刺班 ### by AlanHacker ---  ### [前測](https://forms.gle/XFaZV4ZyR3naBRs36) ---  [儲幹報名(必填)](https://forms.gle/B2nkhx7DfJAmSP8e8) ---  [機房參訪](https://forms.office.com/r/JANueyiH7Q) --- ## Outline * 心態準備 * 一星題講解 --- ## 心態準備 ---- ### 學習資源 * [考古題 & 題庫](https://yuihuang.com/cpe/) * [SA 流 C++ 競程修練心法](https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FBkTJ0imPB) ---- ### C++ or C？ * 以解題而言當然 C++ * 演算法相關函式庫支援差很多 * 但以 CPE 畢業門檻而言 C 夠用 * 但提交程式一律建議丟 C++(反正兼容 ---- ### 解題能力階段 * 語法熟悉：能解無演算法的模擬題(約 1~2 個月) * 演算法初學：各種遞迴、暴力(約 1~2 個月) * 演算法中堅：圖論、貪心、分治、DP (約半年) * 演算法大師：競程大佬(依天賦而定) ---- ### 畢業門檻語法熟悉就穩了！ ---- ### 語法？ * 基本輸入輸出 * 條件判斷 * 迴圈 * 陣列模擬(一維、二維) * 字串處理 * 浮點數精度 * 基本遞迴套路 ---- ### 常見輸入輸出 -- C 語言 ```cpp= scanf("%lld%d%lf", &longlongNum, &intNum, &realNumber); printf("%lld%d%lf", longlongNum, intNum, realNumber); char c; c = getchar(); putchar(c); char s[10]; gets(s); puts(s); ``` ---- ### 多筆測資 ```cpp= int n; // 遇到多筆測資把解題過程與輸入拆開往往比較好理解 void solve() { // 解題過程 } int main() { while (scanf("%d", &n) != EOF) { solve(); } } ``` ---- ### CPE 小技巧 1  * 提交前先測人工公開測試資料 * 基本上過了就是對的 ---- ### CPE 小技巧 2 * 永遠不用擔心 overflow 啦！ ```cpp= #define int long long signed main() { /* 解題流程 */ return 0; } ``` ---- ### CPE 小技巧 3 * 陣列開大沒關係！！只要在 $10^8$ 以下都很穩 * 除非有特殊需求，不然陣列都從 1 開始 index * 通常新手遇到 Runtime Error 無非就是： * overflow：整數超出範圍 * 陣列超出範圍：負號索引或超出範圍 * 除 0 錯誤 ---- ```cpp= int arr[100000000]; int arr2[10000][10000]; int main() { for (int i = 1; i <= n; ++i) { scanf("%d", &arr[i]); } return 0; } ``` ---- ### CPE 小技巧 4 * 暴力是很優雅的 * 看到感覺很數學的問題不要急著算數學 * 先試著暴力就對了！！ ---- ### 範例 * 給你 $y(-10^{18}\le y\le10^{18})$ * 求 $2x^3+8x^2+x+212=y$ 中 x 的任一整數解 ---- ```cpp= #include <stdio.h> #define int long long signed main() { int y; scanf("%lld", &y); // 以暴力枚舉而言， 10^8 以下都是小 case 啦！ for (int x = -1000000; x <= 1000000; ++x) { if (2 * x*x*x + 8 * x*x + x + 212 == y) { printf("%lld", x); return 0; } } puts("No Answer!"); } ``` ---- # 免責聲明 ## 以下技巧不是常規技巧 ### 真的走投無路再使用 ---- ## 如果只差幾筆測資就對了 ---- ### 外鄉人打法 1-1 ```cpp= int main() { int input; scanf("%d", &input); /* 解題過程 */ printf("%d", ans); } ``` * 輸出： ``` 3 1 3 2 // 錯了！答案是 4 1 ``` ---- ```cpp= int main() { int input; scanf("%d", &input); /* 解題過程 */ if (ans == 2) { puts("4"); return 0; } printf("%d", ans); } ``` ---- ### 外鄉人打法 1-2 ```cpp= int main() { int input; scanf("%d", &input); /* 解題過程 */ printf("%d", ans); } ``` * 輸入： ``` 3 1 3 // 這筆輸入錯了，假設正解是 8 ，程式卻輸出 11 2 1 ``` ---- ```cpp= int main() { int input; scanf("%d", &input); if (input == 3) { puts("8\n"); return 0; } /* 解題過程 */ printf("%d", ans); } ``` --- ## 一星題講解 --- ### [Uva 10189 Minesweeper](https://vjudge.net/problem/UVA-10189) ---- ### 劃重點  ---- ### 思路(1) * 地雷不變(無論輸入輸出都是 `'*'`) * 其它變數字(周圍地雷數量) ---- ### 思路(2) * 用二維陣列模擬盤面 * 地雷用 -1 表示(因為不可能出現 -1) * 其他地方初始設為 0 * 剩下按照題目要求處理輸入輸出 ---- ### ~~這題根本難在輸入輸出~~ ```cpp= [4-5|8-19|21-28] #include <stdio.h> #include <string.h> int n, m; int board[105][105]; // 因為 (0 < n, m ≤ 100) 所以保險起見多抓一點 void solve() { memset(board, 0, sizeof(board)); // 記得初始化 getchar(); // 記得拿掉換行 // 從 1 開始存取？因為這樣就不用特別判斷邊界，等一下比較明顯 for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { char c; c = getchar(); if (c == '*') board[i][j] = -1; else board[i][j] = 0; } getchar(); // 記得拿掉換行 } // 輸出結果 for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (board[i][j] == -1) putchar('*'); else printf("%d", board[i][j]); } putchar('\n'); } } int main() { int firstTime = 1; // 紀錄是否為第一個測資 int x = 0; // 紀錄當前是第幾個測資 while (scanf("%d%d", &n, &m), n > 0 && m > 0) { // Uva 很愛叼換行，很 G8 if (firstTime == 0) { putchar('\n'); } firstTime = 0; printf("Field #%d:\n", ++x); solve(); } return 0; } ``` ---- ### 思路(3) * 每個非地雷格子都要變成周圍地雷的數量 * 暴力計算周圍所有格子地雷的數量！ * 只要記得排除自己就好 * 地雷呢？跳過啦！ ---- ### 計算周圍地雷 ```cpp= for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (board[i][j] == -1) continue; int count = 0; for (int dx = -1; dx <= 1; ++dx) { for (int dy = -1; dy <= 1; ++dy) { if (dx == 0 && dy == 0) continue; // 從 1 開始存取的好處 // 若從 0 開始，i + dx == -1 還要特別判斷 if (board[i + dx][j + dy] == -1) ++count; } } board[i][j] = count; } } ``` ---- ## [C 解法](https://gist.github.com/AW-AlanWu/cebb30921cdd37ff47ab71a36172d3a6) ## [Python 解法](https://gist.github.com/KevinYu0515/b96a1201425244995a87754b0cf0f81a) --- ### [Uva 10924 Prime Words](https://vjudge.net/problem/UVA-10924) ---- ### 劃重點  ---- ### 思路(1) * 其實沒什麼好講，只是把字串按照題意轉數字 * 再做質數判斷就好 ---- ### 思路(2) * 大小寫轉數字的部份可以善用內建函數 * `isupper` 、 `islower` 、 `tolower` 等 * 雖然這題沒影響，但記得 strlen 呼叫一次就好 ---- ```cpp= #include <stdio.h> #include <string.h> #include <ctype.h> char word[25]; int main() { while (scanf("%s", word) != EOF) { // strlen 拉出來，不要放在 for 迴圈 int n = strlen(word); int sum = 0; for (int i = 0; i < n; ++i) { // 小巧思，先一律轉小寫來處理 int value = tolower(word[i]) - 'a' + 1; // 再判斷大寫 if (isupper(word[i])) value += 26; sum += value; } if (isPrime(sum)) { puts("It is a prime word."); } else { puts("It is not a prime word."); } } return 0; } ``` ---- ### 思路(3) * 質數判斷的部份，只要找 $[2, \sqrt{n}]$ 範圍內是否有因數即可 * 因為對於 $\ge\sqrt{n}$ 的因數，必定存在另一個 $\le\sqrt{n}$ 的因數相乘等於 $n$ * 記得是**從 2 開始** ---- ```cpp= int isPrime(int num) { for (int i = 2; i * i <= num; ++i) { if (num % i == 0) return 0; } return 1; } ``` ---- ## [C 解法](https://gist.github.com/AW-AlanWu/f0ece6f1a2aabed67a1c8eac74d96d27) ## [Python 解法](https://gist.github.com/AW-AlanWu/d625bdeeae41f8d94edaff2306634459) --- ### [Uva 477 Points in Figures: Rectangles and Circles](https://vjudge.net/problem/UVA-477) ---- ### 劃重點(1)  ---- ### 劃重點(2)  ---- ### 思路(1) * 這題概念很簡單 * 給你一堆長方形和圓形、一堆點座標 * 求每個點分別在幾個圖形裡面？ * 難是難在是實作細節有點多 ---- ### 思路(2) * 遇到複雜的問題，先別寫 code * 先把問題拆分成不同子問題 * 怎麼存圖形、點座標？ * 怎麼判斷點是否在圖形內？ ---- ### 思路(3) -- 怎麼存圖形、點座標？ * 用陣列？很難做！因為很難區分圓形和矩形 * 用 struct ！自定義型別可以按需求客製化 * 所以我們需要圓形和矩形的 struct * 因為點座標很單純，所以用兩個變數存即可 ---- ```cpp= [5-17|19-41|43-50] #include <stdio.h> #include <stdlib.h> #include <math.h> struct Rect { int ord; double upper_left[2]; double lower_right[2]; } rect[15]; struct Circle { int ord; double center[2]; double rad; } circle[15]; int len_r = 0, len_c = 0; void input_figure() { int cnt = 0; char fig; while (scanf("%c", &fig), fig != '*') { if (fig == 'r') { scanf("%lf%lf%lf%lf", &rect[len_r].upper_left[0], &rect[len_r].upper_left[1], &rect[len_r].lower_right[0], &rect[len_r].lower_right[1]); rect[len_r].ord = ++cnt; ++len_r; } else { scanf("%lf%lf%lf", &circle[len_c].center[0], &circle[len_c].center[1], &circle[len_c].rad); circle[len_c].ord = ++cnt; ++len_c; } getchar(); } } int main() { input_figure(); double x, y; while (scanf("%lf%lf", &x, &y), x != 9999.9 || y != 9999.9) { /* 判斷點是否在圖形 */ } return 0; } ``` ---- ### 思路(3) -- 怎麼判斷點是否在圖形內？ * 圓形：使用國中教的距離公式 $\sqrt{(x_1-x_0)^2+(y_1-y_0)^2}$ ，小於半徑就代表在圓內 * 矩形：如下圖判斷  ---- ```cpp= int inCircle(double x, double y, struct Circle c) { double x_bias = fabs(x - c.center[0]); double y_bias = fabs(y - c.center[1]); double dis = sqrtl(x_bias * x_bias + y_bias * y_bias); if (dis <= c.rad) return 1; else return 0; } int inRect(double x, double y, struct Rect r) { if (x < r.upper_left[0] || x > r.lower_right[0]) return 0; if (y < r.lower_right[1] || y > r.upper_left[1]) return 0; return 1; } ``` ---- ### 思路(4) * 題目要求對於每個點所在的圖形 * 要按照輸入順序輸出 * 要排序呀！ ---- ```cpp= int cmp(const void *a, const void *b) { return *(int*)a - *(int*)b; } int main() { input_figure(); double x, y; int ans[15], point_num = 1; while (scanf("%lf%lf", &x, &y), x != 9999.9 || y != 9999.9) { int len_ans = 0; for (int i = 0; i < len_c; ++i) { if (inCircle(x, y, circle[i])) { ans[len_ans++] = circle[i].ord; } } for (int i = 0; i < len_r; ++i) { if (inRect(x, y, rect[i])) { ans[len_ans++] = rect[i].ord; } } qsort(ans, len_ans, sizeof(int), cmp); if (len_ans == 0) { printf("Point %d is not contained in any figure\n", point_num); } else { for (int i = 0; i < len_ans; ++i) { printf("Point %d is contained in figure %d\n", point_num, ans[i]); } } point_num++; } return 0; } ``` ---- ## [C 解法](https://gist.github.com/AW-AlanWu/ea63a42ebd9c406fe45c36a553f48600) ## [Python 解法](https://gist.github.com/KevinYu0515/51b0a3d0ff66e7d8fc5a76ba1d8a976e) --- ## Extra : C++ intro ---- * 萬用標頭檔 * 有了這個再也不用背一堆 `#include <XXX>` ```cpp= #include <bits/stdc++.h> ``` ---- * 排序比一比 * ~~qsort 什麼垃圾~~ ```cpp= int arr[100]; sort(arr, arr + 100); qsort(arr, 100, sizeof(int), cmp); ``` --- # 大家明天加油！ ---  ### [後測](https://forms.gle/Wi95hsgChfFZhiCL7) ---  [儲幹報名(必填)](https://forms.gle/B2nkhx7DfJAmSP8e8) ---  [機房參訪](https://forms.office.com/r/JANueyiH7Q)