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

本次題庫擷取自 CPE 2025/05/20 歷屆考題：https://cpe.mcu.edu.tw/cpe/test_data/2025-05-20

1. B2-sequence

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

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

該題屬於一顆星選集的範圍，具體就不再說明了，直接給 Code：

上傳 Uva 的時候須注意條件：

  • B2-sequence 必須嚴格遞增
  • 且 $b_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
#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, test_case = 1;
    while (cin >> n){
        bool is_B2 = true;
        vector <int> num(n);
        for (int i = 0; i < n; ++i){
            cin >> num[i];
            if (num[i] < 1){
                is_B2 = false;
            }
        }
        bool is_strictly_increasing = is_B2;
        for (int i = 1; i < n; ++i){
            if (num[i] <= num[i - 1]){
                is_strictly_increasing = false;
                break;
            }
        }
        is_B2 = is_strictly_increasing;
        set <int> sums;
        if (is_B2){
            for (int i = 0; i < n; ++i){
                for (int j = i; j < n; ++j){
                    int sum = num[i] + num[j];
                    if (sums.count(sum) > 0){
                        is_B2 = false;
                        break;
                    }
                    sums.insert(sum);
                }
                if (!is_B2) break;
            }
        }
        cout << "Case #" << test_case++ << ": " << (is_B2 ? "It is a B2-Sequence." : "It is not a B2-Sequence.") << "\n" << "\n";
    }
    return 0;
}

2. Error Correction

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

題目翻譯：

有個布林矩陣具有偶數性質（parity property），當矩陣中每一列（row）與每一行（column）的總和皆為偶數，換言之，每列與每行中設定為 1 的位元數必須是偶數。以下是一個具有偶數性質的 4 × 4 矩陣：

1
2
3
4
1 0 1 0
0 0 0 0
1 1 1 1
0 1 0 1

此矩陣各列的總和分別為 2、0、4 與 2，各行的總和分別為 2、2、2 與 2。

你的任務是編寫一個程式，讀入一個矩陣並檢查它是否具有偶數性質（parity property）。

如果矩陣已經符合條件，則輸出 OK。

如果不符合，則檢查是否能僅透過修改一個位元（0 變 1 或 1 變 0）來使矩陣符合偶數性質。如果可以，輸出 Change bit (i,j)，其中 i 為列號，j 為行號。

如果無論如何都無法達成，則輸出 Corrupt。

輸入格式

  • 輸入檔包含一個或多個測資。
  • 每個測資的第一行包含一個整數 n（n < 100），表示矩陣的大小。
  • 接下來的 n 行，每行有 n 個整數。矩陣中僅會出現整數 0 與 1。
  • 當讀到 n = 0 時，輸入結束。

輸出格式

對輸入檔中的每個矩陣，輸出一行：

  • 若矩陣已符合偶數性質，輸出 OK。
  • 若修改一個位元即可符合，輸出 Change bit (i,j)。
  • 否則輸出 Corrupt。

範例輸入：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
4
1 0 1 0
0 0 0 0
1 1 1 1
0 1 0 1
4
1 0 1 0
0 0 1 0
1 1 1 1
0 1 0 1
4
1 0 1 0
0 1 1 0
1 1 1 1
0 1 0 1
0

範例輸出：

1
2
3
OK
Change bit (2,3)
Corrupt

解題思路：

除了矩陣外開兩個陣列 rowSum 跟 colSum，紀錄每列每行的總和，這樣可快速得知該列或行中有幾個 1，進而判斷奇偶性。

for 迴圈遍歷一次 rowSum 與 colSum 中的數字，找出總和為奇數的列和行，記錄其位置。

  • 若所有列和行的總和都是偶數（錯誤列和行數均為 0），表示矩陣本身已經符合偶數性質，輸出 “OK”。
  • 若只有一列與一行是奇數，只要將這交叉點的位元（該行該列的元素）做反轉（0 變 1，1 變 0）即可讓整個矩陣符合偶數性質（不用真的反轉，只要記住位置就好），輸出 “Change bit (i,j)”。此處 i 與 j 都是從 1 開始計數的列與行位置。
  • 剩餘其他任意狀況（錯誤列或錯誤行超過 1 個），表示無法一次修改一個位元使矩陣符合條件，輸出 “Corrupt”。

範例程式碼：

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;

int main(){
    int n;
    
    while (cin >> n, n != 0){
        vector <vector <int>> mat(n, vector<int>(n));
        
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                cin >> mat[i][j];
        
        vector<int> rowSum(n);
        vector<int> colSum(n);
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                rowSum[i] += mat[i][j];
                colSum[j] += mat[i][j];
            }
        }
        
        vector<int> rowErrs, colErrs;
        
        for (int i = 0; i < n; ++i) {
            if (rowSum[i] % 2 != 0) {
                rowErrs.push_back(i);
            }
            if (colSum[i] % 2 != 0) {
                colErrs.push_back(i);
            }
        }

        if (rowErrs.empty() && colErrs.empty()) {
            cout << "OK" << "\n";
        } else if (rowErrs.size() == 1 && colErrs.size() == 1) {
            cout << "Change bit (" << (rowErrs[0] + 1) << "," << (colErrs[0] + 1) << ")" << "\n";
        } else {
            cout << "Corrupt" << "\n";
        }
    }
    return 0;
}

3. Lotto

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

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

題目翻譯：

在德國樂透遊戲中，你需要從集合 ${1, 2, \cdots, 49}$ 中選擇 $6$ 個數字。一種常見但並不會提高中獎機率的玩法，是先從 $49$ 個數字中選出一個包含 $k$ 個元素的子集 $S(k > 6)$，然後只用 $S$ 內的數字來組成多組遊戲。例如，當 $k = 8$ 且 $S = {1, 2, 3, 5, 8, 13, 21, 34}$ 時，可以形成 28 種可能的遊戲組合： $[1, 2, 3, 5, 8, 13], [1, 2, 3, 5, 8, 21], [1, 2, 3, 5, 8, 34], [1, 2, 3, 5, 13, 21], \cdots, [3, 5, 8, 13, 21, 34]$ 。

你的任務是撰寫一支程式，讀取數字 $k$ 和集合 $S$ ，然後輸出所有只由 $S$ 內元素所組成的所有可能遊戲。

輸入格式：

輸入檔將包含一個或多組測資。每組測資為一行，由數個以空格分隔的整數組成：

  • 行首的第一個整數是 $k (6 < k < 13)$ 。
  • 接下來的 $k$ 個整數表示升序排列的集合 $S$ 。
  • 當 $k = 0$ 時，輸入結束。

輸出格式：

對於每組測資，列印所有可能的遊戲，每行一組。

  • 每組遊戲的數字必須以升序排列，且數字間以一個空格分隔。
  • 所有遊戲本身必須以字典序排序，即先比較最小數字，再比較第二小，以此類推，如範例輸出所示。
  • 測資之間必須以一個空白行分隔。
  • 最後一組測資之後不可多印空白行。

範例輸入：

1
2
3
7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

範例輸出：

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
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

解題思路：

本題使用 DFS + Backtracking 演算法解題。

然後從題目敘述稍微觀察一下，可以知道這是一個組合枚舉的題目，每個解都有 $C^k_6$ 種組合之可能性。

那 DFS 的部分如何實現呢？

在此之前我們先做個暫存陣列 comb，表示要輸出的組合。

然後我們從左到右，第一個元素開始做嘗試，嘗試丟入中（comb.push_back(S[i])），直到找出六個為止，如果發現不行就回到上一步，把它刪掉再來一次遞迴。

這邊不要直接寫 for (int i = 0; i < k; ++i) 我們多設一個變數叫 start，控制下一層遞迴的起點，以免重複或倒退選擇 → for (int i = start; i < k; ++i)。

迴圈內的遞迴函式中的 start 參數欄位，則是 i + 1，也確保不會出現重複的元素。

最後就可以設計出完整的一套 dfs() 啦！

1
2
3
4
5
6
7
8
9
10
11
void dfs(const vector<int>& S, int start, vector<int>& comb, vector<vector<int>>& result) {
    if (comb.size() == 6) {
        result.push_back(comb);
        return;
    }
    for (int i = start; i < S.size(); ++i) {
        comb.push_back(S[i]);
        dfs(S, i + 1, comb, result);
        comb.pop_back();
    }
}

完整範例程式碼：

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
#include <bits/stdc++.h>

using namespace std;

void dfs(const vector<int>& S, int start, vector<int>& comb, vector<vector<int>>& result) {
    if (comb.size() == 6) {
        result.push_back(comb);
        return;
    }
    for (int i = start; i < S.size(); ++i) {
        comb.push_back(S[i]);
        dfs(S, i + 1, comb, result);
        comb.pop_back();
    }
}

int main() {
    
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int k;
    bool first = true;
    
    while (cin >> k && k != 0) {
        
        vector<int> S(k);
        for (int i = 0; i < k; ++i) cin >> S[i];
        
        vector<vector<int>> result;
        
        vector<int> comb;
        
        dfs(S, 0, comb, result);

        if (!first) cout << '\n';
        first = false;
        
        for (const auto& v : result) {
            for (int i = 0; i < v.size(); ++i) {
                if (i) cout << " ";
                cout << v[i];
            }
            cout << '\n';
        }
    }
    return 0;
}

4. Goldbach’s Conjecture

Uva Judge：https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=484

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

題目翻譯：

1742 年，德國業餘數學家 Christian Goldbach（哥德巴赫）寫信給 Leonhard Euler（歐拉），提出了以下猜想：每個大於 2 的數都可以寫成三個質數的和。哥德巴赫當時把 1 也算作質數，這個慣例現在已經不再採用。後來，歐拉將這個猜想重新表述為：每個大於或等於 4 的偶數都可以寫成兩個質數的和。例如：

  • 8 = 3 + 5，3 和 5 都是奇質數。
  • 20 = 3 + 17 = 7 + 13。
  • 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23。

至今仍未證明這個猜想是否正確。（哦等等，當然我有證明，只是它太長了，不能寫在這一頁的邊緣。）
不過，現在你的任務是以歐拉表述的方式，驗證所有小於一百萬的偶數是否符合哥德巴赫猜想。

輸入說明：

輸入檔案包含一個或多組測資。每組測資包含一個偶整數 $n$ ，且 $6 ≤ n < 1000000$ 。當 $n$ 為 $0$ 時，輸入結束。

輸出說明：

對每組測資，輸出一行，格式為 $n = a + b$ ，其中 $a$ 和 $b$ 是奇質數。數字和運算子之間要用一個空格分隔，格式請參考以下範例輸出。如果有多組奇質數配對使其和為 $n$，請選擇差值 $b − a$ 最大的組合。如果沒有符合條件的組合，則輸出 “Goldbach’s conjecture is wrong.”

範例輸入：

1
2
3
4
8
20
42
0

範例輸出：

1
2
3
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

解題思路：

使用質數篩法，先建立到 1000000 的質數表，再來我們把奇數質數存起來（2 不用考慮，題目的輸出都要奇質數）。

再來找出對每個輸入的偶數 $n$ ，差值最大（ $b - a$ ）的一組奇質數 $a, b$ ，符合 $n = a + b$ 的輸出格式。

範例程式碼：

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
#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

const int MAX_N = 1000000;
bool is_prime[MAX_N];
vector <int> odd_primes;

void sieve(){
    fill(is_prime, is_prime + MAX_N + 1, true);
    is_prime[0] = false;
    is_prime[1] = false;
    for (int i = 2; i * i <= MAX_N; ++i){
        if (is_prime[i]){
            for (int j = i * i; j <= MAX_N; j += i)
                is_prime[j] = false;
        }
    }
    for (int i = 3; i <= MAX_N; i += 2){
        if (is_prime[i]) odd_primes.push_back(i);
    }
}

pii find_goldbach_pair(int n){
    for (int a : odd_primes){
        if (a > n / 2) break;
        int b = n - a;
        if (is_prime[b]){
            return {a, b};
        }
    }
    return {-1, -1};
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    sieve();
    int n;
    while (cin >> n && n != 0){
        pii ans = find_goldbach_pair(n);
        if (ans.first == -1)
            cout << "Goldbach's conjecture is wrong." << "\n";
        else
            cout << n << " = " << ans.first << " + " << ans.second << "\n";
    }
    return 0;
}