【個人筆記】C++ ZeroJudge 基礎題庫解題(純練習) - part 1
===
a003.：https://zerojudge.tw/ShowProblem?problemid=a003
難度：☆☆☆☆☆
基本IO、條件判斷、四則運算
```cpp=
#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，迴圈結束。
```cpp=
#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
難度：★★☆☆☆
雙層迴圈、條件判斷、邏輯應用。
```cpp=
#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() 轉整數去相減就好了。
Source：https://shihyu.github.io/books/apas01.html
然後題目是叫你自己去範例輸出輸入找 K，我們只要看第一個字元就好了：
```
範例輸入：
1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5
```
```
範例輸出：
*CDC is the trademark of the Control Data Corporation.
```
可發現字元 `'1'`、字元 `'*'` 兩個的 ASCII Code DEC（十進位） 相差 7（49-42），所以 K 是 7。
然後就可以打 code 了：
```cpp=
#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
難度：★★★★☆
```cpp=
#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 容器，如下：
```cpp=
std::map<key_type, value_type> myMap;
```
key_type：鍵的型態。
value_type：值的型態。
插入元素：
```cpp=
myMap[key] = value;
```
存取元素：
```cpp=
value = myMap[key];
```
遍歷 Map：
```cpp=
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
難度：★★★★★
```cpp=
#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 物件：
```cpp=
// 此行意義為 "將整數與字串關聯在一起"
pair<int, string> myPair(123, "abc");
```
看到物件就會想到類別，對，沒錯，pair 本身是類別。而 pair 內部有兩個 public 的 member：first、second，可用於存取 pair 的值。
如下：
```cpp=
#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;
}
```
輸出結果：
```
123
abc
```
---
回到正題，在函數 `string I_T_R(int num)` 中，為何使用 pair 容器而不是 map？
:::success
因為 map 內的鍵值對會自動做升序（由小到大遞增排序），並不符合羅馬數字的「減法規則」，而使用 pair 則不會更動順序，能自行調整，所以便使用 pair。
:::
最後
```cpp=
string result;
for (const auto &[value, symbol] : roman_values) {
while (num >= value) {
num -= value;
result += symbol;
}
}
```
這個部分，至於使用到 `const auto &[value, symbol]` 的目的，在於這東西是固定不動的（裡面是既定的羅馬數字對應十進位數字），不會被修改，所以給他加上 const。還有個好處就是帶來效能提升跟避免不必要的錯誤（如被修改到）。
另外加上 `&` 是因為 range-based for 內容物需要被修改到。
Sign in with Wallet
Connect another wallet