【Uva 題庫解題】C++ 個人解題筆記（一顆星選集） - part 3

一篇十題讓你看到爽！

CPE 49 道必考題，資料來源：https://cpe.mcu.edu.tw/environment.php

21. Symmetric Matrix

PDF Source：https://onlinejudge.org/external/113/11349.pdf

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

題目翻譯：

給定一個正方形矩陣 $M$ 。這矩陣的元素為 $M_{ij} = \{0 < i < n, 0 < j < n\}$ 。

於本題中你要找到給定的矩陣是否對稱。

定義：對稱矩陣指的是所有元素都是非負的，且相對於矩陣中心對稱的矩陣。其他任何矩陣都被認為是不對稱的。如：

你所要做的就是找出矩陣是否對稱。給定矩陣元素的範圍為 $-2^{32} \leq M_{ij} \leq 2^{32}$ 及 $0 \leq n \leq 100$ 。

精選單字：

symmetric (adj.) 對稱的；整齊的

解題思路：

這題乍看之下好像要先學線代，但其實不用！超級簡單～

首先輸入部分，先把 N = 用字串把它讀掉（一樣用 cin）。

之後就是設 isSymmetric bool 變數判斷是否對稱，然後一次雙層迴圈輸入 vector，再一次雙層迴圈，最內層判斷 M[i][j] != M[N - 1 - i][N - 1 - j] 即可。

另外記得用 long long 存，因為元素範圍超過 int 了。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t){
        string a, b; // 讀掉 N = 的部分
        int N;
        cin >> a >> b >> N;
        
        vector <vector<ll>> M(N, vector<ll>(N));
        
        bool isSymmetric = true;
        
        for (int i = 0; i < N; ++i){
            for (int j = 0; j < N; ++j){
                cin >> M[i][j];
                if (M[i][j] < 0) isSymmetric = false; 
            }
        }
        
        if (isSymmetric){
            for (int i = 0; i < N && isSymmetric; ++i){
                for (int j = 0; j < N && isSymmetric; ++j){
                    if (M[i][j] != M[N - 1 - i][N - 1 - j]){
                        isSymmetric = false;
                    }
                }
            }
        }
        
        cout << "Test #" << t << ": " << (isSymmetric ? "Symmetric." : "Non-symmetric.") << '\n';
    }
    return 0;
}

22. Square Number

PDF Source：https://onlinejudge.org/external/114/11461.pdf

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

題目翻譯：

平方數是一個其平方根也是整數的整數。如，1、4、81 都是平方數。給定兩個數字 a 和 b，你需要找出在 a 和 b 之間（包含 a 和 b）有多少個平方數。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF && (a && b)){
        int count = 0;
        for (int i = a; i <= b; ++i){
            int root = sqrt(i);
            if (root * root == i) count++;
        }
        printf("%d\n", count);
    }
    return 0;
}

23. B2-Sequence

PDF Source：https://onlinejudge.org/external/110/11063.pdf

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

題目翻譯：

B2 序列指的是一組正整數的序列， $1 \leq b_1 < b_2 < b_3 \cdots$ 使得所有成對的和 $b_i + b_j$ （ $i \leq j$ ）都不同。

你的任務是判別給定的序列是否為 B2 序列。

解題思路：

根據題目敘述的觀察下，可以知道一個序列是不是 B2 序列，主要看三個條件：

是否為嚴格遞增。
$b_i + b_j$ （ $i \leq j$ ）不相等。
$b_i >= 1$

第二條可以用 set 去存 $b_i + b_j$ ，每次迴圈判斷 sums.count(s) > 0，如果 true 就不是 B2 序列。

範例程式碼：

#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;
}

24. Back to High School Physics

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

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

題目翻譯：

一個粒子有初速度和加速度。設它在一定時間後的速率為 v，那在 2t 秒內它的位移是多少？

精選單字：

displacement (n.) 位移

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int v, t;
    while (cin >> v >> t){
        cout << v * 2 * t << '\n';
    }
    return 0;
}

25. An Easy Problem!

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

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

題目翻譯：

你有聽過「每個正常的數字系統都是以 10 為基數」的事實嗎？當然，我並不是在談及 Stern Brockot 這類的數字系統。這題與該事實無關，但也許有些地方是相似的。

給定一個 $N$ 進位的整數 $R$ ，並保證 $R$ 可以被 $(N - 1)$ 整除。你需要輸出 $N$ 的最小可能值。 $N$ 的範圍為 $2 \leq N \leq 62$ ，而 $62$ 進位數字的符號為（ $0..9$ 和 $A..Z$ 以及 $a..z$ ）。同理， $61$ 進位的數字符號為 $0..9$ 、 $A..Z$ 、 $a..y$ ，依此類推。

註：前一題才是 Easy Problem…這根本都不 Easy。

解題思路：

小心輸入的不一定是字元，而是字串。

整理一下題目要求的：

會輸入一個數字字串（基於 N 進位的整數，符號包括 ‘0’-‘9’、‘A’-‘Z’、‘a’-‘z’ 對應數字 0~61）。
已知該數字是基數 N 的數，且該數可以被 (N-1) 整除。
需要找出符合條件的「最小」可能進位基數 N，且 $2 \leq N \leq 62$ 。
若找不到，輸出 “such number is impossible!”。

解題步驟：

找最大字元的數值 maxVal（進位至少是 maxVal+1）。
計算該字串所有位數字的十進位和 sumDigits（以十進位形式視為一般加總，各位數字的值加總）。
基數 N 從 (maxVal+1) 到 62 依序去做嘗試（mod (N - 1)）。

2025/09/27 修改：輸入有可能是非有效字元，需額外判斷。

範例程式碼：

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

int charToValue(char c){
    if (c >= '0' && c <= '9') return c - '0';
    if (c >= 'A' && c <= 'Z') return c - 'A' + 10;
    if (c >= 'a' && c <= 'z') return c - 'a' + 36;
    return -1;
}

int main(){
    string R;
    while (getline(cin, R)){
        int maxVal = 1, sumDigits = 0;
        
        for (char c : R){
            int val = charToValue(c);
            if (val != -1){
                maxVal = max(maxVal, val);
                sumDigits += val;
            }
        }
        
        bool found = false;
        for (int N = maxVal + 1; N <= 62; ++N){
            if (sumDigits % (N - 1) == 0){
                cout << N << endl;
                found = true;
                break;
            }
        }
        if (!found) cout << "such number is impossible!" << endl;
    }
    return 0;
}

26. Fibonaccimal Base

PDF Source：https://onlinejudge.org/external/9/948.pdf

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

題目不翻譯，太長了。

精選單字：

be obtained by：透過…得到
Among other things：除此之外
repetition (n.) 重複
scheme (n.) 陰謀、詭計；方案、計劃

題目摘要：

首先它就是跟你講說費氏數列到底是啥：

1
2
3

（費氏數列的遞迴式）
Fib(0) = 0, Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)，n ≥ 2

0, 1, 1, 2, 3, 5, 8, 13, …

然後再來講什麼是費氏進位：

將正整數表示成不含連續項的費氏數列和。
將用到的費氏數標為 1，沒用到的標為 0，從右至左表示（Fib(1), Fib(2), Fib(3)...）。
最左邊的位元一定是 1。
不允許出現連續的 1。

這題要做的就是把一個正整數 N，輸出它的「費氏進位」表示法。

假設輸入 17：

$17 = 13 + 3 + 1$

對應的費氏項為 $Fib(7), Fib(4), Fib(1) → 13, 3, 1$

以右至左（ $Fib(1)$ 到 $Fib(7)$ ）表示：

1	0	0	1	0	1
13	8	5	3	2	1

解題思路：

預處理一個大約 $1$ 億的費氏數列（題目條件）
每個輸入數字都做以下的事情：
1. 從最大的費氏數項開始，判斷該費氏數項是否可被選用（ $\leq$ 該數字且不可與前一個選的費氏數相鄰）。
2. 以貪心法從大到小選取費氏數，將數字減去選取的數字並在對應位設 $1$ 。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> nums(N);

    for(int i=0; i<N; i++) {
        cin >> nums[i];
    }

    vector<int> fib = {1,1}; // fib(1) = 1, fib(2) = 1
    while (fib.back() <= 100000000) { // 預處理 fib()
        fib.push_back(fib[fib.size()-1] + fib[fib.size()-2]);
    }

    for(int x : nums) {
        int num = x;
        string res = ""; // res 儲存結果
        int n = fib.size();

        // used 表示 0 or 1 有沒有用過的費氏數項
        vector<int> used(n);

        // 貪心法
        // 因不能連續用，須跳過相鄰位
        // 從最大費氏數項開始找
        for(int i = n-1; i >= 1; i--) {
            if (fib[i] <= num) {
                used[i] = 1;
                num -= fib[i];
                i--;
            }
        }

        bool first_one_found = false;
        for(int i = n-1; i >= 1; i--) {
            if (used[i]) first_one_found = true;
            if (first_one_found)
                res += (used[i] ? '1' : '0');
        }

        cout << x << " = " << res << " (fib)" << "\n";
    }
    return 0;
}

27. Funny Encryption Method

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

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

題目翻譯：

墨西哥蒙特雷理工大學的一名學生正嘗試一種新的數位加密方法。此方法包含以下步驟：

讀取欲加密的數字 $N$ ： $M = 265$
解釋 $N$ 為一個十進位數字： $X_1 = 265$ （十進位）
將 $N$ 的十進位解釋轉換為二進位表示： $X_1 = 100001001$ （二進位）
令 $b_1$ 等於此二進位表示中的 1 的數量： $b_1 = 3$
解釋 $N$ 為十六進位數： $X_2 = 265$ （十六進位）
將 $N$ 的十六進位解釋轉換為二進位表示： $X_2 = 1001100101$
令 $b_2$ 等於最後一個二進位表示法中 $1$ 的數量： $b_2 = 5$
加密結果是 $M xor(b_1∗b_2)$ 的結果： $265 xor(3*5) = 262$

這位學生在計算機組織（Computational Organization）考試中被當了，因此他請墨西哥蒙特雷理工大學校內 ACM 程式設計競賽的評審，幫他詢問這兩種表示法中 $1$ 的位元數，這樣他就能繼續玩下去。

你必須撰寫一個程式，讀取一個數字，並輸出兩個數字 $b_1$ 和 $b_2$ 。

解題思路：

計算 $b_1$ ：

用位元運算判斷 $N$ 的二進位表示中有多少個 $1$ 。
方法：重複 $N \& 1$ 取出最低位元判斷， $N$ 除以 $2$ （右移）直到 $N=0$ 。

計算 $b_2$ ：

將 N 轉成字串。
用 stoi(str, nullptr, 16)。
對此十進位結果，再計算二進位中 $1$ 的個數（跟 $b_1$ 的計算方法相同）。

:::info
函數：
int stoi(const string& str, size_t* idx = 0, int base = 10);

idx 為指向 size_t 的 pointer，函數會將索引設為字串中數值結束後的下一個字元位置，方便判斷是否還有額外非數字字元；若不需要此資訊可設為 nullptr。

base 預設為 10，表示要將哪個進位制轉換成十進位整數，設成 0 會自動判斷。
:::

範例程式碼：

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

// 計算整數的二進位中 1 的個數
int count_ones(int x) {
    int count = 0;
    while (x > 0) {
        count += x & 1; // 位元運算, x & 1 取 x 二進位最低位元的值
        x >>= 1; // 右移 1 位, 最低位與其下一位換位, 最高位補 0
    }
    return count;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        // b1 : N 當十進位數直接算 1 的數目
        int b1 = count_ones(N);

        // 將 N 轉字串，當作十六進位轉成整數
        string hex_str = to_string(N);
        int x2 = stoi(hex_str, nullptr, 16);

        // b2 : x2 的二進位 1 的數目
        int b2 = count_ones(x2);

        cout << b1 << " " << b2 << "\n";
    }
    return 0;
}

28. Parity

PDF Source：https://onlinejudge.org/external/109/10931.pdf

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

題目翻譯：

我們定義一個整數 n 的同位元（parity）為其二進位表示中位元之和，並以 2 為模進行計算。如數字 $21 = 10101_2$ ，在其二進位表示中有 $3$ 個 $1$ ，所以其同位元為 $3 (mod 2)$ ，也就是 $1$ 。

在這個問題中，你必須計算滿足 $1 \leq I \leq 2147483647$ 的整數 $I$ 的同位元。

解題思路：

使用 bitset 將整數轉成二進位。

範圍是 $1 \leq I \leq 2147483647$ ，剛好是 int 整數的最大值，也是 32 位元，所以應寫成 bitset<32> binary(I)。

利用 binary.to_string() 轉成字串，但是會有前導 0 的情況，這邊可以用 find('1') 找出第一個字元 1，再用 substr(f1) 去移除前導 0。

計算有多少個 1 的函式可以參考上一題的函式，直接挪來用XD。

範例程式碼：

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

int count_ones(int x) {
    int count = 0;
    while (x > 0) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int I;
    while (cin >> I && I != 0){
        bitset<32> binary(I);
        string result = binary.to_string();
        auto f1 = result.find('1');
        result = result.substr(f1);
        cout << "The parity of " << result << " is " << count_ones(I) << " (mod 2)." << "\n";
    }
    return 0;
}

29. Cheapest Base

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

No Zerojudge 😦

題目翻譯（From Lucky貓）：

當我們想要把一些字印在紙上時，我們需要墨水。但不是每個字都需要相同的墨水，例如 'W'，'M'，'8' 要比 'i'，'c'，'1' 來的貴。這個問題主要是討論在不同進位制下需要的不同花費。

數字可以被表示成不同的進位制，當我們把數字表示成 n 進位時（ $2 \leq n \leq 36$ ），我們需要用到字串 '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ' 的前 n 項。

每個字元都有他獨特的價錢，以一個 1~128 的整數表示，對於每一個數字，他被印出的價錢是組成他的數字被印出的價錢和。現在給你一個數字，請計算他用哪些進位輸出最省錢。（註：輸出的數最左方不會有沒有意義的 0）

Input

最多有 25 組測資，第一列有一個正整數說明以下有幾個測資，每個測資的前四列每列有九個數，代表那三十六個字元的花費。接下來的數代表這組測資有幾個數，每個數介於 0 和 2000000000 間。

Output

第一列先輸入 “Case X:” ( X 表示是第幾組 )。

對於這組測資的每一個數，先輸出 "Cheapest base(s) for number Y: "，然後再輸出哪些進位制能讓它花最少的錢（遞增順序），如果超過一個進位制，中間請加空白鍵。

兩組測資間亦請空一列。輸出格式請參考 Sample Output。

Sample Input

2
10 8 12 13 15 13 13 16 9
11 18 24 21 23 23 23 13 15
17 33 21 23 27 26 27 19 4
22 18 30 30 24 16 26 21 21
5
98329921
12345
800348
14
873645
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
4
0
1
10
100

Sample Output

Case 1:
Cheapest base(s) for number 98329921: 24
Cheapest base(s) for number 12345: 13 31
Cheapest base(s) for number 800348: 31
Cheapest base(s) for number 14: 13
Cheapest base(s) for number 873645: 22

Case 2:
Cheapest base(s) for number 0: 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
Cheapest base(s) for number 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
Cheapest base(s) for number 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
Cheapest base(s) for number 100: 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

題目在說什麼？

需針對每組測資中的數字，找出在哪個進位制（從 2 到 36）下，印出該數字所需的墨水成本最低。

每組測資的內容含：

36 個字元成本值：
- 含 ‘0’~‘9’ 與 ‘A’~‘Z’。
- 4 列，每列 9 個數，共 36 個值（範圍：1~128）。
- 這些成本代表印出某個字元的「墨水成本」。
多個整數（0~2000000000）
- 每個整數要被轉換為不同進位表示，從 base = 2 到 base = 36。
- 對於每個進位表示，將其數字拆開（如轉成 base-n 的數字），並計算每個位數的「對應字元成本」，加總即為該進位表示法的總成本。

解題思路：

先將 '0' 到 'Z' 共 36 個字元的印字成本存起來，用一個長度為 36 的陣列 cost[36]。

'0' 的成本對應 cost[0]。
'A' 的成本對應 cost[10]。
'Z' 的成本對應 cost[35]。

然後對每個整數 N 做以下三件事情：

試轉成 base = 2 ~ 36 的進位表示。
對每個 base，計算它所需的總成本（把數字分解後看它的每個字元是什麼，再用對應成本加總）。
找出所有成本最小的 base。

如何將十進位數轉為 base-n？

while (N > 0){
    int remainder = N % base;
    // cost[remainder] 查成本
    N /= base;
}

最後就是找出所有最便宜的進位制：

每次更新 min_cost，同時清空 base 結果集合。
若發現與 min_cost 相等的 base，也加入集合中。

最後輸出這個集合即可。

範例程式碼：

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

const string DIGITS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int cost[36];  // 存每個字元的成本

// 將十進位的數字轉為指定進位制，並計算轉換後每個位數的成本總和
int compute_cost(int number, int base) {
    if (number == 0) return cost[0]; 

    int total = 0;
    while (number > 0) {
        int rem = number % base;
        total += cost[rem];
        number /= base;
    }
    return total;
}

int main() {
    int T;
    cin >> T;
    for (int case_num = 1; case_num <= T; ++case_num) {
        for (int i = 0; i < 36; ++i)
            cin >> cost[i];

        int Q;
        cin >> Q;
        vector<int> numbers(Q);
        for (int i = 0; i < Q; ++i)
            cin >> numbers[i];

        cout << "Case " << case_num << ":\n";
        for (int i = 0; i < Q; ++i) {
            int num = numbers[i];
            vector<int> bases;
            int min_cost = INT_MAX;

            for (int base = 2; base <= 36; ++base) {
                int c = compute_cost(num, base);
                
                if (c < min_cost) {
                    min_cost = c;
                    bases.clear();
                    bases.push_back(base);
                    
                } else if (c == min_cost) {
                    bases.push_back(base);
                }
            }

            cout << "Cheapest base(s) for number " << num << ":";
            for (int b : bases)
                cout << " " << b;
            cout << "\n";
        }

        if (case_num != T)
            cout << "\n";  // 測資之間空一列
    }

    return 0;
}

30. Hartals

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

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

題目翻譯：

一個社會研究組織已經確定了一組簡單的參數，用以模擬我國政黨的行為。其中一個參數是一個正整數 $h$ （稱為「罷工參數」hartal parameter），它表示某個特定政黨兩次連續罷工（hartals，罷工）之間的平均天數。雖然這個參數過於簡單而不夠完善，但仍可用來預測罷工造成的損害。以下的例子能讓你更清楚了解：

考慮三個政黨。假設 $h_1 = 3$ 、 $h_2 = 4$ 、 $h_3 = 8$ ，其中 $h_i$ 是第 $i$ 個政黨的罷工參數（ $i = 1, 2, 3$ ）。現在，我們將模擬這三個政黨在 $N = 14$ 天內的行為。我們必須從星期日開始模擬，並且假設每週的週五與週六是假日，因此這兩天不會發生罷工。

上述模擬顯示，在 $14$ 天中將會有 $5$ 次罷工（發生於第 $3$ 、 $4$ 、 $8$ 、 $9$ 和 $12$ 天）。由於第 $6$ 天是星期五，因此不會發生罷工。因此，我們在兩週內損失了 $5$ 個工作天。

在本題中，給定若干個政黨的罷工參數以及天數 $N$ 的值，你的任務是計算在這 $N$ 天中我們損失了多少個工作天。

精選單字：

denote (v.) 表示、代表
forecast (n.) （尤指對特定形勢或天氣的）預測，預報

範例程式碼：

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

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

    int T;
    cin >> T;
    while (T--){
        int N;
        cin >> N;
        int P;
        cin >> P;
        vector<int> h(P);
        for (int i = 0; i < P; ++i){
            cin >> h[i];
        }
        
        // 1-based index
        vector<bool> strike_days(N+1, false);

        for (int i = 0; i < P; ++i){
            int interval = h[i];
            // day 從 1 開始
            // day % 7 == 6 週五
            // day % 7 == 0 週六
            for (int day = interval; day <= N; day += interval){
                int weekday = day % 7;
                if (weekday == 6 || weekday == 0){
                    continue;
                }
                strike_days[day] = true;
            }
        }

        int result = 0;
        for (int day = 1; day <= N; ++day){
            if (strike_days[day]) result++;
        }

        cout << result << "\n";
    }
    return 0;
}