---
# System prepended metadata

title: 【Uva 題庫解題】C++ 個人解題筆記 - part2
tags: [資料結構, 程式設計, C++, 競程, 排序, 演算法, 字串處理, CP]

---

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

1. 11461 SquareNumbers：https://cpe.mcu.edu.tw/cpe/problemPdf/11461.pdf

2025/03/25 CPE 第一題。

Zerojudge 翻譯版：https://zerojudge.tw/ShowProblem?problemid=d186

單字：

* inclusive (adj.)：（價格或數量）包括一切的、包括首尾兩天（或兩個數字）的、（團體或組織）可以包容各種人的。
* denote (v.)：表示，代表。

![image](https://hackmd.io/_uploads/ByKpVutGgx.png)

```cpp=
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b;
    while (cin >> a >> b){
        if (a == 0 && b == 0){
            break;
        }
        int sum = 0;
        for (int i = a; i <= b; i++){
            int root = sqrt(i);
            if (root * root == i){
                sum++;
            }
        }
        cout << sum << '\n';
    }
    return 0;
}
```

2. 10327 FlipSort：https://cpe.mcu.edu.tw/cpe/problemPdf/10327.pdf

2025/03/25 CPE 第二題。

Zerojudge 翻譯版：https://zerojudge.tw/ShowProblem?problemid=a539

![image](https://hackmd.io/_uploads/B1eG5quKMex.png)

單字：

* approach (n.)：原指逼近，這裡當作「方法」使用。
* adjacent (adj.)：鄰近的。
* ascending (adj.)：（規模、價值等）上升的，增長的
    * (biology specialized)（尤指神經通路）上行的，上升的
    * ascending order 就是升序的意思。

```cpp=
#include <bits/stdc++.h>

using namespace std;

int minSwaps(vector<int>& arr, int n) {
    int swaps = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swaps++;
            }
        }
    }
    return swaps;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        cout << "Minimum exchange operations : " << minSwaps(arr, n) << '\n';
    }
    return 0;
}
```

用泡沫排序法去判斷交換的次數，沒想到 AC 了。

複習泡沫排序法的雙層迴圈及判斷式：

```cpp=
for (int i = 0; i < n - 1; i ++){
    for (int j = 0; j < n - i - 1; j ++){
        if (arr[j] > arr[j + 1]){
            swap(arr[j], arr[j + 1]);
        }
    }
}
```

3. 10815 Andy’s First Dictionary：https://cpe.mcu.edu.tw/cpe/problemPdf/10815.pdf

2025/03/25 CPE 第三題。

（Lucky貓）中譯版題目：http://web.kshs.kh.edu.tw/academy/luckycat/homework/q10815.htm

單字及文法：

* 原文：This is not an easy task for him, as the number of words that he knows is, well, not quite enough.
    * as 在這裡當作「因為」使用，也是從屬連接詞。
    * well 在此沒啥特別意思，只是語助詞，類似中文表達「嗯...」。
* instead of (prep.)：並非、而不是。
* instead (adv.)：作為替代...。
* brilliant (adj.)：聰穎的；技藝高超的。
    * 明亮的；（顔色）鮮艶的。
    * 非常好的，出色的。
* copy something out (phr. v.)：抄寫，謄寫。
* alphabetical (adj.)：按字母排序的。
* time-consuming (n-adj.)：耗時的。
* consecutive (adj.)：連續的，連貫的，無間斷的。
* alphabet (n.)：字母表。

![image](https://hackmd.io/_uploads/By-ho9Kflx.png)

```cpp=
#include <bits/stdc++.h>

using namespace std;

string toLowerCase(const string &word) {
    string result = word;
    for (char &c : result) {
        c = tolower(c);
    }
    return result;
}

int main() {
    string word;
    set<string> words;

    char c;
    while (cin.get(c)) {
        if (isalpha(c)) {
            word += c;
        } else {
            if (!word.empty()) {
                words.insert(toLowerCase(word));
                word.clear();
            }
        }
    }

    if (!word.empty()) {
        words.insert(toLowerCase(word));
    }

    for (const string &w : words) {
        cout << w << "\n";
    }

    return 0;
}
```

我原本的想法是說要用 getline() 結合 sstream 下去實作，結果一直 WA 死的很慘，後來才去網路上找解法，才看到有人解這題是用 cin.get()。

因為 sstream 有可能會漏掉一些標點符號，導致處理上會少掉一些單字，所以在這題就可以把 sstream 給丟了 XD。

另外說說 cin.get() 與 getline() 之間的關係：

| 差異 | getline() | cin.get() |
| -------- | -------- | -------- |
| 標頭檔 | `<string>` | `<iostream>` |
| 讀入資料類型 | 讀入整行（含空白） | 一次讀入一個字元或一行 |
| 預設終止字元 | `'\n'` | 可自訂終止字元或讀到 `\n` |
| 是否吃掉換行字元 | 吃掉 `\n` | 預設不吃 `\n`（視用法而定） |
| 用途 | 讀入一整行字串 | 控制細節、讀單個字元、進階輸入 |

然後有個超級重要的細節，就是使用 C++ 內建的資料結構 set。可以省掉排序的動作，因為 set 會自動幫你排序，可保留字典序。

* `isalpha(c)`：`<cctype>` 標頭檔中的函數，主要拿來判斷一個字元 c 是否為英文字母。而此函數所接收的參數型態為 unsigned char 或 EOF。
    * 若輸入的字元非英文字母，如：`'3'`、`'!'` 等等，函數會回傳 0，否則為 1。
* `tolower(c)`：`<cctype>` 標頭檔中的函數，主要將英文字母轉為小寫，若原本就小寫就直接回傳，若大寫就轉小寫回傳，就醬。接受參數的型態如上。
