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

1. https://zerojudge.tw/ShowProblem?problemid=a135

題目原文：https://cpe.mcu.edu.tw/cpe/problemPdf/12250.pdf

單字翻譯：

• prominent (adj.) 突出的；著名的；卓越的
• figure (vt.) 表示 (在此題當作表示之意)
• European (adj.) 歐洲的；歐洲人的 (n.) 歐洲人 (此題當作形容詞用)
• equivalent (adj.) 相同的；相等的 (n.) 等於；等同
• assume (v.) 假設；冒充、假裝；承擔、擔任 (此題為假設之意)
• uppercase (adj.) 大寫的
• terminate (v.) 使終止；限定；終止、結束
• quote (v.) 引用；放在引號內；估計 (n.) 引號 (此題當作引號之意)

2024/12/10 CPE 第一題。

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main(){
    string line;
    
    int n;
    
    map <string, string> language = {
        {"HELLO", "ENGLISH"},
        {"HOLA", "SPANISH"},
        {"HALLO", "GERMAN"},
        {"BONJOUR", "FRENCH"},
        {"CIAO", "ITALIAN"},
        {"ZDRAVSTVUJTE", "RUSSIAN"},
    };
    
    while (cin >> line && (line != "#")){
        n ++;
        language.find(line) != language.end() ? cout << "Case " << n << ": " << language[line] << "\n" : cout << "Case " << n << ": " << "UNKNOWN" << "\n";
    }
    
    return 0;
}

map 字典鍵值對映射的應用。

字串處理。

EOF、特定字元終止程式。

另解：

另一個思路就是做一個巢狀的 if-elseif-else 判斷式，判斷六個 hello 意義，然後輸出對應的語言，最後 else 就是非這些字串的，輸出 UNKNOWN 字串。沒學 map 可用這個，照樣可 AC。

1. https://zerojudge.tw/ShowProblem?problemid=c032

題目原文：https://cpe.mcu.edu.tw/cpe/problemPdf/382.pdf

單字翻譯：

• mutiple (n.) 倍數
• divisor (n.) 除數
• factor (n.) 因數
• proper divisor 真因數、真因子
• even (adj.) 偶數的；odd (adj.) 奇數的
• imperfect (adj.) 不完美的
• deficient (adj.) 缺乏的、缺少的
• abundant (adj.) 豐富的
• determine (v.) 確定、決定、影響；下決心；找出

2024/12/10 CPE 第二題。

#include <iostream>
#include <iomanip>

using namespace std;

int main() {
    cout << "PERFECTION OUTPUT" << endl;

    int n;
    while (cin >> n) {
        if (n == 0) break;

        long long sum = 0;
        for (int d = 1; d * d <= n; d++) {
            if (n % d == 0) {
                if (d < n) {
                    sum += d;
                }
                int nd = n / d;
                if (nd < n && nd != d) {
                    sum += nd;
                }
            }
        }

        string classification;
        if (sum == n) {
            classification = "PERFECT";
        } else if (sum < n) {
            classification = "DEFICIENT";
        } else {
            classification = "ABUNDANT";
        }

        cout << "   " << n << "  " << classification << endl;
    }

    cout << "END OF OUTPUT" << endl;

    return 0;
}

perfect number : 一個正整數中，他的所有因數的和等於他這個數本身。

deficient : 所有因數和小於數本身。

abundant : 所有因數和大於數本身。

題目要求要求真因數（不含自身的因數之其他因數）和，所以 for 的地方主要是求真因數和。

那這樣的寫法時間複雜度只要 O(根號n)，如果一個一個檢查數字，則要到 O(n)，這樣蠻慢的。

為啥要這樣寫？因為因數是成對出現的，如 6 / 2 = 3, 6 / 3 = 2，再一個例子就是 12 / 2 = 6, 12 / 6 = 2。

if (d < n)：如果是真因數，就加進去 sum 裡面。

而 nd 及其判斷式的部分：

int nd = n / d;
if (nd < n && nd != d) {
    sum += nd;
}

則是前面所述，因數會成對出現，而前面的因數有 2 已經出現了，而且 6 / 2 = 3，3 也是 6 的因數之一，所以 nd = n / d。

然後判斷句跟前面的差不多，首先就是判斷是不是真因數，再來 nd != d 是防止在 n 是完全平方數時重複計入相同的因數（如：n = 9，d = 3，nd = 9 / 3 = 3）。

這個判斷其實蠻合理的，因為前面就已經判斷過一次 3 < 9，然後把它加進去 sum 了，假設這邊只有判斷真因數的部分，那等於重複再加一次，所以必須要加上去這個判斷。

後面就簡單了，判斷三種數出來，然後根據題目輸出要求去輸出。

1. https://zerojudge.tw/ShowProblem?problemid=f444

題目原文：https://cpe.mcu.edu.tw/cpe/problemPdf/10268.pdf

單字翻譯：

• polynomial (n.) 多項式（專有名詞）
• frankly (adv.) 坦率地、坦誠地；坦白說
• derivative (n.) 導數（微分出來的值）
• in particular (phr.) 特別是、尤其是
• algebra (n.) 代數
• derivation (n.) 推導；起源、衍生物、出處
• coefficient (n.) 係數
• terminate (v.) 使終止；終止、結束

2024/12/10 CPE 第三題。

#include <iostream>
#include <vector>
#include <sstream>
#include <string>

using namespace std;

// 處理整數冪的函數
long long ipow(int base, int exp) {
    long long result = 1;
    for (int i = 0; i < exp; i++) {
        result *= base;
    }
    return result;
}

int main() {
    string line;
    while (getline(cin, line)) {
        stringstream ss(line);
        int x;
        ss >> x;

        getline(cin, line);
        stringstream ss2(line);
        vector<int> coef; // coefficient 係數
        int a;
        while (ss2 >> a) {
            coef.push_back(a);
        }

        int n = coef.size() - 1;
        long long sum = 0;
        for (int i = 0; i < n; i++) {
            int exponent = n - i - 1; // exponent 指數
            // n - i - 1 是因為 i 初始值是 0
            long long term = (long long)coef[i] * (n - i) * ipow(x, exponent);
            sum += term;
        }
        cout << sum << endl;
    }
    return 0;
}

先來看看輸入範例代表的意義：

7
1 -1 
2
1 1 1 

首先 x = 7，然後係數是 1, -1。

這代表 x - 1 的意思，可以設 f(x) = x - 1，要求 f(x) 在 x = 7 的導數，則要先把它微分。

微分之後的導函數為：f’(x) = 1，所以 f’(7) = 1。

第二個也一樣：

設 g(x) = x^2 + x + 1

導函數 g’(x) = 2x + 1，g’(2) = 5。

所以輸出為：

1
5

首先要了解微分 Power Formula：n*x^n-1。

就是次方項 - 1，將原本的次方 n 乘上 x 前面的係數。

有關以上程式部分，可能會想說為啥自訂函數 ipow() 呢？明明有 pow() 可用。

這因為題目要求整數輸出，而 pow() 回傳值的資料型態是 double。

之後程式碼的部分，for 迴圈內部就直接代入微分公式就好囉。