【個人筆記】C++ ZeroJudge 基礎題庫解題(純練習) - part 3
===

a020：https://zerojudge.tw/ShowProblem?problemid=a020

難度：★☆☆☆☆

流程控制。

#include <iostream>
#include <string>

using namespace std;

int main() {
    // 映射表，索引0對應A（10），1對應B（11），依此類推
    int mapping[26] = {
        10, 
        11, 
        12, 
        13, 
        14, 
        15, 
        16, 
        17, 
        34, 
        18, 
        19, 
        20, 
        21, 
        22, 
        35, 
        23, 
        24, 
        25, 
        26, 
        27, 
        28, 
        29, 
        32, 
        30, 
        31, 
        33
    };
    
    string id;
    cin >> id;
    
    char letter = id[0];
    
    // 轉字母為數字
    int num = mapping[letter - 'A'];
    int a = num / 10; // 十位數
    int b = num % 10; // 個位數
    int sum = a + b * 9;
    
    for (int i = 1; i <= 9; i++) {
        int digit = id[i] - '0';
        if (i <= 8) {
            sum += digit * (9 - i);
        } else {
            sum += digit;
        }
    }
    
    if (sum % 10 == 0) {
        cout << "real" << endl;
    } else {
        cout << "fake" << endl;
    }
    
    return 0;
}

---

c531.：https://zerojudge.tw/ShowProblem?problemid=c531

難度：★★★☆☆

字串流應用、基本排序法、基本資料結構

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

int main() {
    string line;
    // 逐行讀取輸入
    while (getline(cin, line)) {
        stringstream ss(line);
        string token;
        vector<int> numbers;
        // 將一行分割並轉換為整數
        while (getline(ss, token, ',')) {
            numbers.push_back(stoi(token));
        }
        // 提取偶數
        vector<int> evens;
        for (int num : numbers) {
            if (num % 2 == 0) {
                evens.push_back(num);
            }
        }
        // 對偶數進行升序排序
        sort(evens.begin(), evens.end());
        // 使用迭代器追蹤排序後的偶數
        auto it = evens.begin();
        for (size_t i = 0; i < numbers.size(); ++i) {
            if (numbers[i] % 2 == 0) {
                cout << *it;
                ++it;
            } else {
                cout << numbers[i];
            }
            // 在非最後一個數字後添加逗號
            if (i < numbers.size() - 1) {
                cout << ",";
            }
        }
        cout << endl;
    }
    return 0;
}

stoi()：字串轉整數，string to int。

---

e446.：https://zerojudge.tw/ShowProblem?problemid=e446

難度：★☆☆☆☆

排列組合、列舉

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    vector <int> nums;
    for (int i=1;i<=n;i++){
        nums.push_back(i);
    }
    do{
        for (int n : nums) cout << n << " ";
        cout << "\n";
    } while(next_permutation(nums.begin(), nums.end()));
    return 0;
}

最後一個測資點不知道是什麼鬼測資，測很久才發現 IO 要優化，記得別用 endl，用 '\n' 取代。

至於 `ios::sync_with_stdio(false), cin.tie(nullptr);` 要不要加其實沒差，但如果加了可以少 0.3 秒左右。

---

d212.：https://zerojudge.tw/ShowProblem?problemid=d212

難度：★★☆☆☆

費氏數列、dp 優化

最簡單的解法就是遞迴解，但遞迴所花費的時間過多，在遞歸的時候會產生額外的計算開銷，也不會記錄答案。

#include <iostream>

using namespace std;

int main() {
    int n;
    
    while(cin >> n) {
        
        if(n == 1) {
            cout << 1 << endl;
            continue;
        }

        long long a = 1, b = 2, c;
        
        for(int i = 3; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        
        cout << b << endl;
    }
    
    return 0;
}

此程式碼為 DP bottom-up（由下往上） 的方式：

主要先處理最小子問題：`dp[1] = 1, dp[2] = 2`（a = 1, b = 2），再用迴圈慢慢回推上去：`dp[i] = dp[i-1] + dp[i-2]`，所以 i 從 3 開始。

時間複雜度：$$O(n)$$空間複雜度：$$O(1)$$

以下是使用 top-down（由上往下） 的處理方式：

#include <iostream>
#include <vector>

using namespace std;

vector<long long> dp(100, -1);

long long ans(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;

    if (dp[n] != -1) return dp[n];

    return dp[n] = ans(n - 1) + ans(n - 2);
}

int main() {
    int n;
    while (cin >> n) {
        cout << ans(n) << endl;
    }
    return 0;
}

Top-Down 就跟 Bottom-Up 相反：

主要先拆解大問題，再用遞迴去求出小問題，最後透過 DP 儲存答案一步步求出最終解答。

另外 Top-Down 也強調記憶化（Memorization）的部分，因為遞迴會導致一些重複計算的部分而產生效能開銷，所以這時候 DP 的作用就發揮出來了。`return dp[n] = ans(n-1) + ans(n-2)` 的部分就是將答案記起來，就不用重複算了。

Top-Down 的時間複雜度：$$O(n)$$空間複雜度：$$O(n)$$