【Uva 題庫解題】C++ 個人解題筆記 - part4

本次題庫擷取自 CPE 2025/09/30 歷屆考題（本文撰筆日期 2025/10/03 時 CPE 官網尚未更新，但在瘋狂程設已有歷屆試題）。

練習題

第一題是 Hello World，第二題為 Rock, Scissor, Paper，第三題則為必考題 Fourth Point，第四題是 LCM Pair Sum。

Uva 10443 - Rock, Scissor, Paper

Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1384

No Zerojudge :(

PDF Source：https://onlinejudge.org/external/104/10443.pdf

題目翻譯：

Bart 的妹妹 Lisa 在一個二維網格上創造了一個新的文明。一開始，每個網格位置可能被三種生命體之一佔據：石頭（Rock）、剪刀（Scissor）或布（Paper）。

每天，佔據水平或垂直相鄰網格位置的不同生命體會發動戰爭。在每場戰爭中，石頭總是戰勝剪刀，剪刀總是戰勝布，而布總是戰勝石頭。在一天結束時，勝利者會擴張其領土，納入失敗者的網格位置。失敗者則會騰出該位置。

你的任務是確定在 n 天之後，每種生命體所佔據的領土。

Input

輸入的第一行包含 t，代表測資數量。每個測資以三個不大於 100 的整數開始：r 和 c（分別代表網格的行數和列數）以及 n。接下來的 r 行代表該網格，每行有 c 個字元。網格中的每個字元為 ‘R’、’S’ 或 ‘P’，分別表示該位置被石頭、剪刀或布所佔據。

Output

對於每個測資，請輸出第 n 天結束時的網格狀態。在連續測資的輸出之間請留一個空行。

Sample Input

1
2
3
4
5
6
7
8
9
2
3 3 1
RRR
RSR
RRR
3 4 2
RSPR
SPRS
PRSP

Sample Output

1
2
3
4
5
6
RRR
RRR
RRR
RRRS
RRSP
RSPR

解題思路：

很顯然這是一道模擬題。

觀察題目與其範例測資，可以發現一天的戰鬥下來，幾乎都是同時發生的，這表示說不能在 for 遍歷 grid 的時候去改它，因為一個格子的變化可能會影響到它旁邊尚未處理的格子的戰鬥結果。

實際作法是用兩個 grid（二維陣列或 vector<string>）：

  • 一個 current_grid 用來儲存當天開始時的狀態。
  • 另一個 next_day_grid 用來儲存根據 current_grid 計算出的當天結束時的狀態。

搞好了資料結構以後，接下來搞模擬步驟：

  1. 每天開始，都將 next_day_grid 初始化為 current_grid。
  2. 遍歷 current_grid 每個格子 (r, c)。
  3. 對於每個格子，檢查其上、下、左、右四個相鄰的格子。
  4. 如果任何一個相鄰的格子上的物種可以戰勝 (r, c) 上的物種（如 P 對上 R），那麼在 next_day_grid 中， (r, c) 的位置將被戰勝它的物種佔領。一旦找到一個勝利者，就可以停止檢查該格子的其他 neighbor了。
  5. 當遍歷完所有格子後，next_day_grid 就代表了新一天的狀態。
  6. 將 next_day_grid 的內容複製回 current_grid，準備進行下一天的模擬。
  7. 上述步驟做 n 次。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>

using namespace std;

char getWinner(char c) {
    if (c == 'R') return 'P';
    if (c == 'S') return 'R';
    return 'S';
}

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

    int t;
    cin >> t;
    while (t--) {
        int r, c, n;
        cin >> r >> c >> n;
    
        vector<string> grid(r);
        for (int i = 0; i < r; ++i) cin >> grid[i];
    
        for (int day = 0; day < n; ++day) {
            vector<string> next_grid = grid;
            
            for (int i = 0; i < r; ++i) {
                for (int j = 0; j < c; ++j) {
                    char current_lifeform = grid[i][j];
                    char winning_lifeform = getWinner(current_lifeform);
    
                    int dr[] = {-1, 1, 0, 0};
                    int dc[] = {0, 0, -1, 1};
    
                    for (int k = 0; k < 4; ++k) {
                        int ni = i + dr[k];
                        int nj = j + dc[k];
    
                        if (ni >= 0 && ni < r && nj >= 0 && nj < c) {
                            if (grid[ni][nj] == winning_lifeform) {
                                next_grid[i][j] = winning_lifeform;
                                break;
                            }
                        }
                    }
                }
            }
            grid = next_grid;
        }
    
        for (int i = 0; i < r; ++i) cout << grid[i] << '\n';
        
        if (t > 0) 
            cout << '\n';
    }

    return 0;
}

1. Uva 100 - The 3n + 1 Problem

此為一顆星選集之必考題，故不多做解釋。

Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=c039

PDF Source：https://onlinejudge.org/external/1/100.pdf

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>

using namespace std;

int getCycleLength(int n){
    int count = 1;
    while (n != 1){
        if (n % 2 == 1) n = 3 * n + 1;
        else n /= 2;
        count++;
    }
    return count;
}

int main(){
    int i, j;
    while (cin >> i >> j){
        int from = min(i, j);
        int to = max(i, j);
        int max_cycle = 0;
        for (int i = from; i <= to; ++i){
            int cycle_length = getCycleLength(i);
            if (cycle_length > max_cycle) max_cycle = cycle_length;
        }
        cout << i << " " << j << " " << max_cycle << '\n';
    }
    return 0;
}

2. Uva 483 - Word Scramble

Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=424

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=e625

PDF Source：https://onlinejudge.org/external/4/483.pdf

Tags : 字串處理

題目翻譯：

撰寫一個程式，在保留單字順序不變的情況下，將每個單字中的字母反轉。

Input

輸入檔案將包含數行文字，每行由數個單字組成。單字是由空白字元分隔開來的連續可列印字元。

Output

輸出內容將包含與輸入檔案相同的行與單字。但是，每個單字內的字母順序必須反轉。

Sample Input

1
2
3
I love you.
You love me.
We're a happy family.

Sample Output

1
2
3
I evol .uoy
uoY evol .em
er'eW a yppah .ylimaf

解題思路：

用 stringstream ss(line); 讀取用空格隔開的字串，然後 while(ss >> result) 就可一個一個把字串反轉輸出。

這邊可用 bool isFirst = true; 辨別是否為第一個字串，不是的話就用空格區隔。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    string line;
    while (getline(cin, line)){
        stringstream ss(line);
        string result;
        bool isFirst = true;
        while (ss >> result){
            if (!isFirst) cout << " ";
            
            reverse(result.begin(), result.end());
            
            cout << result;
            
            isFirst = false;
        }
        cout << "\n";
    }
    return 0;
}

3. Uva 673 - Parentheses Balance

Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=614

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=b304

PDF Source：https://onlinejudge.org/external/6/673.pdf

Tags : Stack

題目翻譯：

給定一個由括號 () 和 [] 組成的字串。如果此類型的字串滿足以下條件，則稱其為正確的：

(a) 如果它是空字串
(b) 如果 A 和 B 都是正確的，那麼 AB 也是正確的。
(c) 如果 A 是正確的，那麼 (A) 和 [A] 也是正確的。

請撰寫一個程式，讀取一系列這種類型的字串，並檢查其正確性。您的程式可以假設字串的最大長度為 128。

Input

輸入包含一個正整數 n，以及 n 個由括號 () 和 [] 組成的字串序列，每個字串佔一行。

Output

輸出一系列的 ‘Yes’ 或 ‘No’。

Sample Input

1
2
3
4
3
([])
(([()])))
([()[]()])()

Sample Output

1
2
3
Yes
No
Yes

解題思路：

本題是經典的括號配對題目，主要使用 Stack（堆疊）LIFO 資料結構的特性下去做。

C++ STL 中有提供 stack<data_type> 這樣的 container，不必再額外實作。

在這邊我用函數設計的方式實作內部細節，會比較容易讀，以下是 bool isCorrect(const string& s) 的演算法流程：

  1. 宣告 stack <char> 物件，用來存放所有遇到的左括號。
  2. range-based for loop 遍歷字串。
  3. （遇到左括號）若字元是 ( 或 [，則堆入 stack 裡面（方法：stack.push(c)）。
  4. （遇到右括號）流程有點複雜，不過請看：
    • 首要檢查 stack.empty()
      • 若為空：表示該右括號沒有對應的左括號 -> return false。
      • 若非空：檢查堆疊最頂端的元素（方法：stack.top()）是否為其對應的左括號。
    • 經過檢查、驗證過後，發現沒問題就直接 pop() 出來即可。
  5. 最後全遍歷完成後，若 stack 為空就表示所有括號配對完成。

最後提醒輸入要先輸入測資數量，再來要 getline(cin, line)，在此之前有使用到 cin 的部分，務必要打上 cin.ignore() 讀掉 \n。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>

using namespace std;

bool isCorrect(const string& s){
    stack <char> result;
    for (char c : s){
        if (c == '(' || c == '[') result.push(c);
        else if (c == ')'){
            if (result.empty() || result.top() != '(') return false;
            result.pop();
        }
        else if (c == ']'){
            if (result.empty() || result.top() != '[') return false;
            result.pop();
        }
    }
    return result.empty();
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    cin.ignore();
    string line;
    while (n--){
        getline(cin, line);
        cout << (isCorrect(line) ? "Yes" : "No") << '\n';
    }
    return 0;
}

4. Uva 417 - Word Index

Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=358

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=c077

PDF Source：https://onlinejudge.org/external/4/417.pdf

題目翻譯：

編碼系統常用於需要加密或節省資訊儲存 / 傳輸空間的情況。在這裡，我們開發一個簡單的編碼系統，將由五個或更少（小寫）字母組成的特定類型單字編碼為整數。

考慮英文字母表 ${a, b, c, …, z}$ 。使用此字母表，將形成一組依嚴格字典順序排列的有效單字。在這組有效單字中，一個單字的連續字母必須是嚴格遞增的順序；也就是說，一個有效單字中後面的字母在字母表 ${a, b, c, …, z}$ 中的位置必須總是在前面字母的後面。例如，

abc aep gwz

都是 有效 的三字母單字，而

aab are cat

則不是。

每個 有效 單字都關聯一個整數，該整數給出單字在所有單字的字母排序列表中的位置。也就是：

a -> 1
b -> 2
.
.
.
z -> 26
ab -> 27
ac -> 28
.
.
.
az -> 51
bc -> 52
.
.
.
vwxyz -> 83681

您的程式需要讀取一系列的輸入行。每行輸入將包含一個單字，長度為一到五個字母。對於讀取的每個單字，如果該單字 無效，則輸出數字 ‘0’。如果讀取的單字是 有效 的，則輸出其在上述字母排序列表中的位置索引。

Input

輸入包含一系列的單字，每行一個。單字長度至少一個字母，不超過五個字母。輸入只會使用小寫字母 {a,b,c,…,z}。單字的第一個字母將是輸入行的第一個字元。輸入將以檔案結尾（end-of-file）終止。

Output

輸出為一個大於或等於零 (0) 且小於或等於 83681 的單一整數。輸出值的第一個數字應為一行的第一個字元。每個輸入行對應一行輸出。

Sample Input

1
2
3
4
z
a
cat
vwxyz

Sample Output

1
2
3
4
26
1
0
83681

解題思路：

根據題目敘述，首先可以知道的是一個有效的單字，他的某個字母的後面不能小於那個字母，也就是說要嚴格遵循字典序的意思。

所以第一個流程就是檢查字母是否嚴格遞增（word[i] < word[i+1]）；若不合法，直接輸出 0。

同樣這邊我也是使用函數設計的方式，比較簡潔易懂，剛剛說明的流程就放在 long long getIndex(const string& word) 裡面。

然後會用到 long long 是因為這個題目會談到組合（Combination）的問題，保險起見才用到 long long。

接下來繼續設計 getIndex() 裡面的東西，然後要來設計計算索引的流程，這個流程就需要用到組合公式了。

英文字母總共有 26 個，則一個有效的合法單字就是 $C^{26}_k$ ，接著按照字典序去排序，然後求這個組合在所有組合中的排名第幾？

拿範例測資舉個例子：

  • “a” 只有一個字母，所以是 C1 取 k，但無論取多少它都還是 1，因此輸出 1。
  • “b” 比它小的只有 “a” 而已，所以為 2。
  • “ab” 所有長度 1 的組合都輪完一遍了（26 個字母跑完），然後在長度 2 的組合裡，”ab” 是第一個，因此輸出 27。

在此之前，先來設計組合公式的函數，因為 C++ STL 沒有提供函數（哭了）。

以下的函數就是公式

但是要直接在程式裡面算這個可能會直接變成非常糟糕的時間複雜度，所以可以對這個公式進一步化簡。

注意一下上面 n! 可以改成這樣： $n! = n \times (n - 1) \times \cdots \times (n - k + 1) \times (n - k)!$

而 $(n - k)! = (n - k) \times (n - k - 1) \times \cdots \times 1$

所以上下對消後公式就變成

然後這公式就是我們要寫的程式了。

1
2
3
4
5
6
7
8
long long C(int n, int k) {
    if (k > n) return 0;
    long long res = 1;
    for (int i = 1; i <= k; i++) {
        res = res * (n - i + 1) / i;
    }
    return res;
}

接著回到 getIndex() 函數裡面，設字串長度是 L，則加上所有比 L 短的組合數： $\sum^{L-1}_{i=1}C^{26}_i$ （這主要用在兩個以上的字母像是 'ab'）

然後比對他在相同長度組合裡面的排名是多少。這邊的演算流程設計是逐個比對字母，計算有多少組合在他前面，具體方法如下：

  • 設字串 = $w[0] w[1] … w[L-1]$ ，把字母換成數字 1~26。
  • 從左到右檢查：
    • 在第 $i$ 個字母前，假設選的字母比 $w[i]$ 更小，剩下的位置用組合數補齊。

這邊最後記得加上 1，因為還要包含字串本身。

範例程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

long long C(int n, int k) {
    if (k > n) return 0;
    long long res = 1;
    for (int i = 1; i <= k; i++) {
        res = res * (n - i + 1) / i;
    }
    return res;
}

long long getIndex(const string &word) {
    int L = word.size();
    for (int i = 1; i < L; i++) {
        if (word[i] <= word[i-1]) return 0;
    }

    long long rank = 0;

    for (int i = 1; i < L; i++) {
        rank += C(26, i);
    }

    int prev = 0;
    for (int i = 0; i < L; i++) {
        int cur = word[i] - 'a' + 1;
        for (int j = prev + 1; j < cur; j++) {
            rank += C(26 - j, L - i - 1);
        }
        prev = cur;
    }

    return rank + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string word;
    while (cin >> word) {
        cout << getIndex(word) << "\n";
    }
    return 0;
}