{%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)$

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 有幾個，同時要記得紀錄該位置被算過了
- 根據題目要求格式輸出(前面四個空格)

----

### 簡單的實作而已

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

----

### 實作

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，會幫你產生答案
於是你可以先搞出答案後

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)$ 解

- 矩陣快速冪 上課講過囉!

---

### 結尾

祝大家考試順利!