【Uva 題庫解題】C++ 個人解題筆記 - part3
===
[TOC]
本次題庫擷取自 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$
```cpp=
#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 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。
範例輸入：
```
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
```
範例輸出：
```
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"。
範例程式碼：
```cpp=
#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$ 時，輸入結束。
**輸出格式**：
對於每組測資，列印所有可能的遊戲，每行一組。
- 每組遊戲的數字必須以升序排列，且數字間以一個空格分隔。
- 所有遊戲本身必須以字典序排序，即先比較最小數字，再比較第二小，以此類推，如範例輸出所示。
- 測資之間必須以一個空白行分隔。
- 最後一組測資之後不可多印空白行。
**範例輸入**：
```
7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0
```
**範例輸出**：
```
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()` 啦！
```cpp=
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();
}
}
```
完整範例程式碼：
```cpp=
#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."
範例輸入：
```
8
20
42
0
```
範例輸出：
```
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37
```
解題思路：
使用質數篩法，先建立到 1000000 的質數表，再來我們把奇數質數存起來（2 不用考慮，題目的輸出都要奇質數）。
再來找出對每個輸入的偶數 $n$ ，差值最大（ $b - a$ ）的一組奇質數 $a, b$ ，符合 $n = a + b$ 的輸出格式。
範例程式碼：
```cpp=
#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;
}
```
Sign in with Wallet
Connect another wallet