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

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.)：表示，代表。

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

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

2025/03/25 CPE 第二題。

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

單字：

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

#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 了。

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

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]);
        }
    }
}

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.)：字母表。

#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> 標頭檔中的函數，主要將英文字母轉為小寫，若原本就小寫就直接回傳，若大寫就轉小寫回傳，就醬。接受參數的型態如上。