【個人筆記】C++ ZeroJudge 基礎題庫解題(純練習) - part 1

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

難度：☆☆☆☆☆

基本IO、條件判斷、四則運算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>

using namespace std;

int main(){
    int M, D, S;
    cin >> M >> D;
    S = (M*2+D)%3;
    if (S==0){
        cout << "普通";
    }
    else if (S==1){
        cout << "吉";
    }
    else{
        cout << "大吉";
    }
    return 0;
}

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

難度：★☆☆☆☆

遇到需要持續輸入的迴圈，在 CPP 中使用 while (cin >> a)。

若將 while 改成 while (true)，然後 cin 放裡面，會造成 TLE（Time Limit Exceed）時間超過限制。

使用 while (cin >> a) 可避免此情形發生，這行的意義為「迴圈會持續執行，直到 cin >> year 失敗為止」。

若輸入有效的整數時，條件為 true，迴圈繼續執行；若輸入了非整數，則 cin 錯誤，條件為 false，迴圈結束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>

using namespace std;

int main(){
    int year;
    while (cin >> year){
        if (year % 400 == 0 || (year % 100 != 0 && year % 4 == 0)){
            cout << "閏年" << endl;
        }
        else{
            cout << "平年" << endl;
        }
    }
    return 0;
}

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

難度：★★☆☆☆

雙層迴圈、條件判斷、邏輯應用。

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 <iostream>

using namespace std;

int main(){
    int t, a[5];
    cin >> t;
    for (int i=0;i<t;i++){
        for (int j=0;j<4;j++){
            cin >> a[j];
        }
        if ((a[1] - a[0]) == (a[2] - a[1])){
            a[4] = a[3] + (a[1] - a[0]);
        }
        else{
            a[4] = a[3] * (a[1] / a[0]);
        }
        for (int m=0;m<5;m++){
            cout << a[m] << " ";
        }
        cout << "\n";
    }
    return 0;
}

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

難度：★★☆☆☆

題目敘述在講的就是凱薩密碼（Caesar Cipher），要找 K（位移數），可能需要參照一下 ASCII code。

註：其實也不用參照，只要透過程式的 char() 轉整數去相減就好了。

image

Source：https://shihyu.github.io/books/apas01.html

然後題目是叫你自己去範例輸出輸入找 K，我們只要看第一個字元就好了：

1
2
範例輸入：
1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5
1
2
範例輸出：
*CDC is the trademark of the Control Data Corporation.

可發現字元 '1'、字元 '*' 兩個的 ASCII Code DEC（十進位） 相差 7（49-42），所以 K 是 7。

然後就可以打 code 了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <cstring>

using namespace std;

int main(){
    string a;

    getline(cin , a);

    for (int i = 0;i<a.size();i++){ // a.size() 方法是表示 a 字串的總長度。
        cout << char(a[i]-7);
    }

    return 0;
}

為何不用 cin.get(char)？

cin.get(char) 只能一個一個去讀字元，而 getline(cin, string) 可以讀完整行字串。

另外 cin.get(char) 會保留 new-line 跳脫字元（\n）在輸入流中，若下次再次讀取，可能會讀到 \n。

getline(cin, string) 可以讀完整行字串，直到遇到 \n 為止。他會把整行字串存在 string 物件裡面，不會自行將 \n 包含在內。

總之 cin.get(char) 有可能會遇到無限迴圈的情形，但另一個不會。

那是不是看起來 cin.get(char) 比較沒啥屁用？錯。

:::success
cin.get(char) 使用情形：

  1. 讀逐個字元
  2. 保留 \n
  3. 處理跳脫字元
  4. 限制輸入長度：cin.get(char array, size) 像是可控制陣列長度。
    :::

:::success
getline() 使用情形：

  1. 需忽略 \n
  2. 有空格的字串
    :::

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

難度：★★★★☆

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
#include <iostream>
#include <map>
using namespace std;

void pf(int n) {
    map<int, int> factor;
    
    while (n % 2 == 0) {  // 處理質因數 2（因為偶數的因數一定有 2）
        factor[2]++;
        n /= 2;
    }
    
    for (int i = 3; i * i <= n; i += 2) {  // 用 for 迴圈處理奇數的質因數
        // 若 i 平方超過 n 表示處理完畢
        while (n % i == 0) {
            factor[i]++;
            n /= i;
        }
    }
    
    if (n > 1) {  // 若 n 是質數且 > 1 
        factor[n]++;
    }
    
    // 輸出結果
    bool first = true; // 此 Variable 用來控制是否輸出 * 來分隔因數
    for (auto &[prime, exp] : factor) { // C++ 11 才有的 range-based for loop 用來遍歷 map
        // auto -> 自動偵測 map 的鍵值對型態
        if (!first) cout << " * ";
        first = false;
        cout << prime;
        if (exp > 1) cout << "^" << exp;
    }
    // prime -> 因數的英文, exp -> 指數的英文

}

int main() {
    int n;
    cin >> n;
    pf(n);
    return 0;
}

程式碼當中用到 C++ map 容器，可直接將其視為 Python 中的字典。

要宣告一個 map 容器，如下：

1
std::map<key_type, value_type> myMap;

key_type：鍵的型態。
value_type：值的型態。

插入元素：

1
myMap[key] = value;

存取元素：

1
value = myMap[key];

遍歷 Map：

1
2
3
for (std::map<key_type, value_type>::iterator it = myMap.begin(); it != myMap.end(); ++it) {
    std::cout << it->first << " => " << it->second << std::endl;
}

來源：https://www.runoob.com/cplusplus/cpp-libs-map.html

:::success
在此使用 Map 是為了方便計算跟儲存質因數（當Key）、次方數（當Value）。
:::

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

難度：★★★★★

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h> // 此為萬用標頭檔 因為這支程式碼太多函式褲要導入了

using namespace std;

// 羅馬數字與十進位映射
map<char, int> roman_to_int = {
    {'I', 1},
    {'V', 5},
    {'X', 10},
    {'L', 50},
    {'C', 100},
    {'D', 500},
    {'M', 1000},
};

// 羅馬數字轉為十進位
int R_T_I(const string &s) {
    int num = 0;
    int prev_value = 0;
    for (int i = s.size() - 1; i >= 0; --i) {
        int value = roman_to_int[s[i]];
        if (value >= prev_value) {
            num += value;
        } else {
            num -= value;
        }
        prev_value = value;
    }
    return num;
}

// 十進位轉羅馬數字
string I_T_R(int num) {
    if (num == 0) return "ZERO";

    pair<int, string> roman_values[] = {
        {1000, "M"},
        {900, "CM"},
        {500, "D"},
        {400, "CD"},
        {100, "C"},
        {90, "XC"},
        {50, "L"},
        {40, "XL"},
        {10, "X"},
        {9, "IX"},
        {5, "V"},
        {4, "IV"},
        {1, "I"},
    };

    string result;
    for (const auto &[value, symbol] : roman_values) {
        while (num >= value) {
            num -= value;
            result += symbol;
        }
    }
    return result;
}

int main() {
    string a, b;
    while (cin >> a && a != "#") {
        cin >> b;
        int num1 = R_T_I(a);
        int num2 = R_T_I(b);
        int diff = abs(num1 - num2);
        cout << I_T_R(diff) << endl;
    }
    return 0;
}

:::success
string s v.s. string &s v.s. const string &s：

三種不同函數傳遞方式各有不同：

string s：傳值呼叫，效能差，如果資料量小可這樣做。
string &s：傳參考呼叫，效能略勝上述。另外要注意不能傳遞字面常數（const char*），因為此時函數傳遞方式是可被修改的，不相通。
const string &s：不能修改，但三者當中效能最好，反正就是可讀不能改，符合上述競程題目需求。
:::

另外在函數 int R_T_I(const string &s) 當中，採用從右至左遍歷的解題思路。

因為在羅馬數字的規則下，「大數在前小數在後」代表加法 (如 VI = 6)；「小數在前大數在後」代表減法 (如 IV = 4)。

所以這樣的作法可以比較好去判斷加減法的部分，以求確切的十進位數字。

最後輸出時，根據題目輸出要求，所以還是要把數字變回去羅馬數字，那這支程式碼就定義了函數 string I_T_R(int num)。

此函數使用到了 pair 容器，需要使用此標頭檔 #include <utility> 引入。（不過我們用了萬用標頭檔所以不用手動引入）

以下是有關於 pair 的簡介：

建立一個 myPair 物件：

1
2
// 此行意義為 "將整數與字串關聯在一起"
pair<int, string> myPair(123, "abc");

看到物件就會想到類別，對，沒錯，pair 本身是類別。而 pair 內部有兩個 public 的 member：first、second，可用於存取 pair 的值。

如下：

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>

using namespace std;

int main(){
    pair <int, string> myPair(123, "abc");
    // 123 為 firsst, "abc" 為 second
    cout << myPair.first << endl;
    cout << myPair.second << endl;
    return 0;
}

輸出結果：

1
2
123
abc

回到正題，在函數 string I_T_R(int num) 中，為何使用 pair 容器而不是 map？

:::success
因為 map 內的鍵值對會自動做升序（由小到大遞增排序），並不符合羅馬數字的「減法規則」，而使用 pair 則不會更動順序，能自行調整，所以便使用 pair。
:::

最後

1
2
3
4
5
6
7
string result;
for (const auto &[value, symbol] : roman_values) {
    while (num >= value) {
        num -= value;
        result += symbol;
    }
}

這個部分，至於使用到 const auto &[value, symbol] 的目的，在於這東西是固定不動的（裡面是既定的羅馬數字對應十進位數字），不會被修改，所以給他加上 const。還有個好處就是帶來效能提升跟避免不必要的錯誤（如被修改到）。

另外加上 & 是因為 range-based for 內容物需要被修改到。