114學年度第十屆榕資盃程式設計競賽 題解

我寫了六個多小時的題解，認真看看ㄅ

感謝 YummyBerry 學長 熱情贊助第四題速解法

感謝 wow肯德基爺爺欸 熱情贊助第六題題解

前言

這次比賽剛好跟中山大學資工特殊選材面試撞期沒參加到，但晚上我自己做了一次，先放成績（下面那次是正常的時限，後來又做出上面的多一個30分）

Score Board｜第二題後來又找到陷阱

結論上還是沒能破台，但Berry學長好像做出500分的成績…

看來我還需要多加練習

這篇文章每題的構成會以

1. 題目簡述
2. 思路
3. 完整題解

來做說明，我有用一些比喻讓他看起來比較像是人話，如果有更好的想法或是遇到問題可以在下面留言板詢問。

題目在這裡，要登入後按下「參加虛擬競賽」才能看到題目。

希望在看我的思路之前可以自己思考看看，再透過文章引導，做出AC或是比我更好的程式碼。

先說說stdio優化

這裡應該有剛踏入競程的人，所以我想介紹一下這個：你可能會在看我的程式時注意到我會這樣寫

#include <bits/stdc++.h>
#define raymondwengcode ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

int main() {
    raymondwengcode;
    // ...
    return 0;
}

上面的幾行我分別解釋

• 第一行#include <bits/stdc++.h>：這行是C++的萬用標頭檔，包含了幾乎所有C++標準函式庫，能讓你不用一個一個include需要的函式庫，節省時間。
• 第二行#define raymondwengcode ...：這行是定義一個指令，當你在程式中打raymondwengcode時，會被替換成後面的程式碼，這樣能節省打字時間，你也可以使用自己的指令名稱。
• 第七行raymondwengcode;：這行是呼叫上面定義的指令，作用是優化C++的輸入輸出速度，讓C++的cin/cout能接近C語言的scanf/printf速度，適合競賽使用。

值得注意的是優化的部分包含三個東西，他們分別也有功能

• ios::sync_with_stdio(false);：關閉C++的cin/cout與C語言的stdio同步，提升cin/cout速度。
• cin.tie(0);：解除cin與cout的綁定，讓cin不會在每次輸入前自動flush cout，提升輸入速度。
• cout.tie(0);：解除cout與cin的綁定，讓cout不會在每次輸出前自動flush cin，提升輸出速度。

看不懂的話，用白話文說就是解除限制，加速，指數級的加速。也歡迎你使用這個，但請注意

使用這個後不得混用cin/cout與scanf/printf，否則可能會導致輸入輸出錯亂。

然後說說一些常用資料結構

這部分蠻重要的，關乎於你撰寫程式的效率與便利性以及看不看懂我的程式碼

vector

vector就是一個陣列，可以動態調整大小，使用起來很方便，並且效率跟int[]那種陣列差不多

我一直以為vector比較慢

最近都用vector，所以下面會常常出現以下寫法請特別注意

• vector<A> v;：宣告一個A型別vector
• vector<A> v(n);：宣告一個長度為n的A型別vector
• vector<int> v(n, x);：宣告一個長度為n的int型別vector，並且每個元素初始值為x
• v.emplace_back(x);：在vector尾巴加入一個元素x，如果對於pair的vector，可以直接用v.emplace_back(a, b);來加入一個pair(a, b)
• v.size()：取得vector長度
• v.begin(), v.end()：取得vector的開始及結束位置，常用於sort等函式
• sort(v.begin(), v.end());：將vector中的元素進行排序（由小到大）
• for (auto i : v) { ... }：使用範圍for迴圈來遍歷vector中的每個元素（i會依序取得v中的每個元素）

pair

pair可以用一個變數存兩個值，可以避免需要創造多個陣列來存東西的麻煩，使用方式如下

• pair<A, B> p;：宣告一個pair，其中first是A型別，second是B型別
• p.first：取得pair的第一個值（也可以拿來賦值）
• p.second：取得pair的第二個值（也可以拿來賦值）
• make_pair(a, b)：建立一個pair，其中第一個值是a，第二個值是b

pair比大小時會先比較first，若相等則比較second。

priority_queue

priority_queue是一個優先佇列，可以用來存放需要排列的項目，並且能夠快速取得優先級最高的項目，使用方式如下

• priority_queue<A> pq;：宣告一個由大到小的priority_queue，其中A是存放的型別
• priority_queue<A, vector<A>, greater<A>> pq;：宣告一個由小到大的priority_queue，其中A是存放的型別
• pq.push(x);：將元素x加入priority_queue，加進去的時候他會自動排好
• pq.top();：取得priority_queue中優先級最高的元素
• pq.pop();：移除priority_queue中優先級最高的元素
• pq.empty();：檢查priority_queue是否為空

這東西在最短路徑的題目中很常用。

1. 有缺陷的計算機

題目類型：模擬

題目簡述

共有奇數行，其中

1. 奇數行輸入數字（整數）
2. 偶數行輸入運算子（0/1/2分別代表加減乘）

注意：須遵守先乘除後加減規則

輸出一行，包含運算結果。

思路

先講小東西：他沒有給輸入數量，所以要透過while(cin >> ...)來讀取直到EOF。

解題部分，一開始看到題目想說應該就是堆疊(stack)的題目，但發現好像不用那麼複雜，我分別展開說說。

思考堆疊的時候請在腦袋中準備壽司店的盤子，一個物件就是一個盤子

堆疊的部分

1. 先把東西全部塞成一堆（運算子記得轉換）
2. 先處理乘法，抽出前後數字跟運算子再算完塞回去
3. 再處理加減法（一樣抽出來算完塞回去）
4. 最後堆疊剩下一個數字就是答案

但這題沒有括號，且只有三種運算子，所以我想到可以直接用兩個變數來記錄：先設定res為0，n為第一個數字，然後每次讀到運算子就判斷：

1. 如果是乘法，直接把n乘上下一個數字
2. 如果是加法或減法，先把n加到res裡面，然後把n設為下一個數字（加法為正，減法為負）

原理：就是遇到乘法都先做，這樣就沒有先乘除後加減的問題，變成簡單的加減法輸入輸出。

有點像是接過盤子，然後遇到乘法就直接把盤子上的東西乘起來，遇到加減法就把盤子上的東西放到桌上，然後換一個新盤子接新的東西。

完整題解(AC 0.15s 1.5mb)

直接複製以下程式上傳會使你學不到任何東西，並有可能導致帳號被封禁，請僅將此程式作為寫法上的參考。

#include <bits/stdc++.h>
#define raymondwengcode ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

int main() {
    raymondwengcode;

    int res = 0; // sum
    int n; // now caculating number
    cin >> n;
    int op; // operator
    while (cin >> op) {
        int k;
        cin >> k;
        if (op == 2) { // multiply
            n *= k;
        }else {
            res += n;
            if (op == 0) { // add
                n = k;
            }else { // subtract
                n = -k;
            }
        }
    }
    res += n;
    cout << res;

    return 0;
}

2. 阿嬤的舊手機

題目類型：模擬

題目簡述

手機按鍵圖

像上面的舊手機，給定一串小寫英文及空白字串，請輸出一串數字代表按鍵序列。例如ae輸出233，但注意到如果連續兩個字母在同一個按鍵上，則中間要插入_，例如ab輸出2_22。對於連續空白字元不需輸出_。

思路

第一想法已經撇除運算了（麻煩，我懶），於是用Python做了一個每個字元列舉

for i in range(2, 10): # 數字鍵2到9
    for j in range(1, 4): # 每個鍵最多3個字母
        print(f"        \"{str(i)*j}\",") # 反斜線印出字串的雙引號

然後再手動加入pqrs和wxyz兩組，最後變成一個長度是26的list。

接著就是讀入字串，然後一個字元一個字元處理，但結論上我跟Berry學長都WA，暫時不想試，之後有解開再更新。如果你有發現我的錯誤也歡迎下面留言處指正！

更新（2025/11/27）：Batch2 #5 子題似乎有修正，重送之後就通過了

附註：他有大寫字母（啥）這部分我後來才看到，多了30分

不完整題解(AC 0.05s 1.6mb)

直接複製以下程式上傳會使你學不到任何東西，並有可能導致帳號被封禁，請僅將此程式作為寫法上的參考。

#include <bits/stdc++.h>
#define raymondwengcode ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

int main() {
    raymondwengcode;

    string list[] = {
        "2",
        "22",
        "222",
        //...
        "999",
        "9999"
    };

    string s;
    getline(cin,s);
    if(s == ""){
        return 0;
    }
    transform(s.begin(), s.end(), s.begin(), ::tolower); // 轉小寫
    string res = "";
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == ' ') {
            res += "0";
        }else {
            if (res.length() > 0 && res[res.length()-1] == list[s[i]-'a'][0]) { // 判斷底線
                res += "_";
            }
            res += list[s[i]-'a'];
        }
    }
    cout << res;

    return 0;
}

3. 搬運寶藏的海盜

題目類型：1-0一維背包問題

題目簡述

一個非常標準的01背包問題，第一行輸入兩個整數w, n代表背包容量及寶藏數量，後面有n行，每行有兩個整數w, v代表寶藏重量及價值，請輸出在不超過背包容量的情況下，能取得的最大價值。

本題範例輸出應為21，應該是題目打錯了

思路

我發現我沒有學過背包問題，但在各種意外下寫出了類似的做法如下

直接複製以下程式上傳會使你學不到任何東西，並有可能導致帳號被封禁，請僅將此程式作為寫法上的參考。

int dp(int i, int w, vector<pair<int, int>> &v) {
    // 回傳值代表在前i個物品中，當背包容量為w時，能取得的最大價值
    // i: 第i個物品 w: 背包容量 v: 物品重量價值pair陣列
    // pair<A, B> 代表first是A型別，second是B型別，一個變數有兩個值
    if (i <= 0 || w <= 0) return 0; 
    int res = dp(i-1, w, v); // 不拿第i個物品
    if (v[i-1].first <= w) { // 拿第i個物品，容量-w重量去找最大值
        res = max(res, v[i-1].second + dp(i-1, w-v[i-1].first, v));
    }
    return res;
}

被TLE(20分)了。我也想過用i來搭配w做一個二維dp陣列來存結果，但會MLE。

請注意本題記憶體限制為4M，不夠存int[10000][1000]

解釋01背包問題

對於一維空間，每樣物品只能拿取一次的題目，可以採取以下策略

定義

\[w_i\text{為第}i\text{項的重量}\] \[v_i\text{為第}i\text{項的價值}\newline\] \[dp[i][w]\text{為使用前}i\text{項物品，在背包容量為}w\text{時，能取得的最大價值}\]

則

\[dp[i][w]= \begin{cases} dp[i-1][w] & \text{if } w < w_i \\ max(dp[i-1][w], dp[i-1][w-w_i]+v_i) & \text{if } w >= w_i \end{cases}\]

主要是透過為背包騰出$w_i$的空間來計算，利用前i項最好的結果節省時間，也就是DP。

腦袋裡畫一排方格子也需可以幫助你思考，透過留下$w_i$個格子來放進第i項物品

如何優化

原本的做法中，直接使用遞迴會有重複計算的可能，但若使用二維陣列紀錄卻又會造成超出空間，所以可以嘗試使用一維陣列。透過將i遞增依序找出答案並記錄，每次更新時原本就留在陣列中的資料就是i-1的結果，所以可以直接使用。

請特別注意：製作時需要倒序處理w，避免重複使用同一物品，例如有物品重量為3，價值為3，原本陣列為

0 0 2 2 2 2

當處理到重量3時，若正序更新陣列會變成

0 0 2 3 3 5

因為當處理到重量5時，會使用到重量2的結果，導致同一物品被使用兩次。由後往前計算可以避免dp[w-wi]的結果被更新過。

完整題解(AC 0.19s 3.5mb)

直接複製以下程式上傳會使你學不到任何東西，並有可能導致帳號被封禁，請僅將此程式作為寫法上的參考。

#include <bits/stdc++.h>
#define raymondwengcode ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

int main() {
    raymondwengcode;
    int w, n;
    cin >> w >> n;
    vector<pair<int, int>> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].first >> v[i].second;
    }
    vector<int> dp(w+1, 0);
    for (int i = 0; i < n; i++) {
        for (int r = w; r >= 0; r--) {
            if (r >= v[i].first) {
                dp[r] = max(dp[r], dp[r - v[i].first] + v[i].second);
            }
        }
    }
    cout << dp[w] << endl;

    return 0;
}

4. 下一個排列

題目類型：排列組合/std應用

題目簡述

1, 2, 3排列，字典序由小到大依序為123, 132, 213…給定一個n代表長度，下一行有n個數字代表排列，請輸出下一個排列，若無（最大組合）則輸出最小排列。例如輸入215，輸出251。

思路

先排列找到字典序後一個的排列組合，若無則輸出最小排列。

然後我寫到一半看到Berry學長的訊息，用C++的next_permutation函式就能直接解決這題，於是我就用這個函式來做。

next_permutation會直接修改傳入的陣列，使其變成下一個排列組合，若無則回傳false。所以

1. 輸入數字進vector
2. if(next_permutation(...))，則輸出結果
3. else輸出最小排列（排序過的陣列）

值得注意的是這題在Leetcode有完全相同的題目，後面有空的時候會藉由這題撰寫不用next_permutation的解法。

完整題解(AC 0.12s 1.6mb)

直接複製以下程式上傳會使你學不到任何東西，並有可能導致帳號被封禁，請僅將此程式作為寫法上的參考。

#include <bits/stdc++.h>
#define raymondwengcode ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

int main() {
    raymondwengcode;

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    if (next_permutation(a.begin(), a.end())) {
        for (auto i : a) {
            cout << i << " ";
        }
    }else {
        sort(a.begin(), a.end());
        for (auto i : a) {
            cout << i << " ";
        }
    }

    return 0;
}

5. 好吃的熱食部自助餐

題目類型：隊列Queue

題目簡述

輸入一整數n代表有n筆操作，接下來有n行可能為以下格式

• 1 x：代表x加入隊伍
• 2：代表隊伍前面的人離開（若無則忽略）
• 3 x：代表隊伍中第一個是x的人離開（若無則忽略）

x為一大寫字母

最後輸出隊伍中剩下的人，若無則輸出0。

思路

這題常數不大，利用Queue來模擬即可。注意盡量避免使用刪除動作（erase），因為會導致時間複雜度過高，可以將刪除的元素標記起來，最後輸出時再跳過即可，以下例子將刪除的元素改成字元0。

Queue使用

1. vector(陣列)
2. 兩個整數代表頭尾位置

我自己腦袋中用一排撲克牌（像接龍那樣），頭尾分別放上一個綠色旗子跟紅色旗子，長度為0的時候（包含一開始）兩個旗子重疊在一起。

操作上

1. 加入：將x放到陣列尾巴，尾巴指標+1
2. 離開前面的人：將頭指標+1
3. 離開第一個x：從頭到尾掃描陣列，找到第一個x後將其改成0

那疊撲克牌可以透過「翻過來」這個動作完成刪除。循序搜尋有辦法完成這題

需注意做完第2, 3項操作後需檢查頭是否被指向已經被刪除的物件。

完整題解(AC 0.36s 3.3mb)

直接複製以下程式上傳會使你學不到任何東西，並有可能導致帳號被封禁，請僅將此程式作為寫法上的參考。

#include <bits/stdc++.h>
#define raymondwengcode ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

int main() {
    raymondwengcode;

    int n;
    cin >> n;
    vector<char> v(n);
    int head = 0;
    int tail = 0;
    for (int i = 0; i < n; i++) {
        int op;
        cin >> op;
        if (op == 1) { // 加入
            cin >> v[tail];
            tail++;
        }else if (op == 2) { // 離開前面的人
            if (tail > head) {
                head++;
            }
        }else if (op == 3) { // 離開第一個x
            char p;
            cin >> p;
            for (int r = head; r < tail; r++) {
                if (v[r] == p) {
                    v[r] = '0';
                    break; // 只刪除第一個，我一開始忘記了
                }
            }
        }
        for (; head < tail; head++) { // 檢查head是否已經被刪除
            if (v[head] != '0') {
                break;
            }
        }
    }
    bool printed = false; // 這個的作用是避免開頭多一個空格，以及判斷是否需要輸出0
    for (int i = head; i < tail; i++) {
        if (v[i] != '0') { // 跳過被刪除的項目
            if (printed) {
                cout << " " << v[i];
            }else {
                printed = true;
                cout << v[i];
            }
        }
    }
    if (!printed) {
        cout << 0;
    }

    return 0;
}

6. 上課要遲到了

本題題解由wow肯德基爺爺欸撰寫，萬分感謝

題目類型：二維圖最短路徑

題目簡述

輸入N,M代表節點數與通道數，有M行輸入起點u、終點v、要走多久w，最後一行分別輸入起始點S與終點T。 輸出最少需要多少時間。

思路

顯而易見這題就是標準的最短路徑dijkstra，首先先輸入成圖，用dist陣列存當下最短距離、priority_queue存(距離, 節點)，每次取出當前距離最小的點u，如果這個距離已經大於dist[u]就丟掉；不然就嘗試鬆弛u的所有鄰居v。

複雜度約為$O((N + M) log N)$

完整題解(AC)

直接複製以下程式上傳會使你學不到任何東西，並有可能導致帳號被封禁，請僅將此程式作為寫法上的參考。

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
struct Edge {
    // 做圖
    // 畫邊, to= 終點 w = 走這條路花的時間
    int to;
    int w;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin>>N>>M;

    vector<vector<Edge>> g(N + 1);

    for(int i = 0; i < M; i++) {
        int u, v, w;
        cin>>u>>v>>w;
        g[u].push_back({v, w});
    }
    int S, T;
    cin >> S >> T;
    // dist[i]= 從S走到i 的最短距離
    vector<long long> dist(N + 1, INF);
    // 每次取距離最小的點
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq; // 很醜但應該沒寫錯
    // 很重要 把起點設為距離0
    dist[S] = 0;
    pq.push({0, S});

    while(!pq.empty()) {
        auto[d, u] = pq.top();
        pq.pop();
        // 如果距離不是最小就跳過
        if(d >dist[u]) {continue;}
        // 因為pq.top會是當下最優解 所以當u 等於終點時即確保是最優解
        if (u == T) {break;}
        // 嘗試鬆弛所有從點u到點v
        // 鬆弛 : 大概是指試試看能不能用目前走到 u 的距離 + 邊 (u→v) 的長度, 去更新dist變得更小
        for(auto &e : g[u]) {
            int v = e.to;
            int w = e.w;
            if(dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    if(dist[T] == INF) {cout<<-1;}
    else {cout<<dist[T];}
}

後記

超好笑我為了這東西花了超多時間，然後開了超多次虛擬競賽，希望這個能幫到你們啊…

最後附上我的一大堆虛擬競賽