【Uva 題庫解題】C++ 個人解題筆記（一顆星選集） - part 2
===

[TOC]

一篇十題讓你看到爽！

CPE 49 道必考題，資料來源：https://cpe.mcu.edu.tw/environment.php

## 11. Common Permutation

PDF Source：https://onlinejudge.org/external/102/10252.pdf

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

題目翻譯：

給定由兩個小寫字母組成的字串，a 和 b，請輸出最長的小寫字母字串 x，使得 x 的某個排列是 a 的子序列，且 x 的某個排列也是 b 的子序列。

解題思路：

建立 A、B 字串的頻率表，接著 range-based for loop 判斷頻率++。

common 取最小的頻率，為啥？以下是個例子：

(a) the
(b) street

| 字母 | a | b |
| -------- | -------- | -------- |
| t | 1 次 | 2 次 |
| s | 0 次 | 1 次 |
| h | 1 次 | 0 次 |
| e | 1 次 | 2 次 |

而這個題目是要求兩個字串中字元的交集，所以要求共同出現的次數，像 t 就只取 1 次，e 也是。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    string a, b;
    while (getline(cin, a)){
        getline(cin, b);
        
        vector <int> freqA(26), freqB(26);
    
        for (char& ch : a) freqA[ch - 'a']++;
        for (char& ch : b) freqB[ch - 'a']++;
        
        string result;
        for (int i = 0; i < 26; ++i){
            int common = min(freqA[i], freqB[i]);
            for (int j = 0; j < common; ++j){
                result += 'a' + i;
            }
        }
        
        cout << result << '\n';
    }
    return 0;
}

## 12. Rotating Sentences

PDF Source：https://onlinejudge.org/external/4/490.pdf

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

題目翻譯：

在本題 "Rotating Sentences" 中，你被要求將一系列輸入句子順時針旋轉 90 度。所以你的程式不會從左到右、從上到下顯示輸入句子，而是從上到下、從右到左顯示。

精選單字：

- clockwise (adj., adv.) 順時針方向的

解題思路：

建立一個 `vector<string>` 存每一行的字串。

設 `max_len` 變數表示每一行字串中最長的那個字串大小，`resize(max_len, ' ')` vector 裡面的字串。（為長度不足的字串補空格）

`resize(max_len, ' ')` 如果遇到原本就有的元素不會刪除，是元素之外的才會加上去。

範例程式碼：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<string> lines;
    string line;
    
    while (getline(cin, line)) {
        lines.push_back(line);
    }

    int max_len = 0;
    for (auto &s : lines) {
        if ((int)s.size() > max_len) max_len = s.size();
    }

    for (auto &s : lines) {
        s.resize(max_len, ' ');
    }

    for (int i = 0; i < max_len; ++i) {
        for (int j = (int)lines.size() - 1; j >= 0; --j) {
            cout << lines[j][i];
        }
        cout << '\n';
    }

    return 0;
}

## 13. TeX Quotes

PDF Source：https://onlinejudge.org/external/2/272.pdf

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

TeX 是由 Donald Knuth 發展出來的一種排版語言。它將原始文字與一些排版指令結合，並產生出一份（希望是）漂亮的文件。漂亮的文件用  和  去表示引號，而非大多數鍵盤所提供的 `""`，鍵盤通常沒有方向性的雙引號，但它們有左單引號「」（鍵盤那顆波浪鍵）與右單引號「'」。

請檢查你的鍵盤，找出左單引號鍵「」（有時稱為「反引號鍵」）與右單引號鍵「'」（有時稱為「撇號」或「引號」）。

請注意不要把左單引號「」與「反斜線鍵（\\）」搞混了。TeX 讓使用者透過輸入兩個左單引號「」來產生一個左雙引號「」，以及輸入兩個右單引號「''」來產生一個右雙引號「''」。然而，大多數打字員習慣使用無方向性的雙引號 " 來標示引言。

如果原始檔包含：


那麼由 TeX 排版出來的文件將無法產生我們所期望的格式：


為了產生所期望的格式，原始檔必須包含下列內容：


註：最後一段我是真的不太會翻，我就把 Lucky 貓大大的翻譯句照抄了。

> 你現在必須要寫一個程式，將普通的雙引號（"），轉成有方向性的雙引號，而其它文字則不變。而在把普通的雙引號換掉的時候，要特別注意，當要開始引述一句話時要用  ，而結束引述時要用 '' 。不用擔心會有多層巢狀引號的情形，也就是第一個引號一定是用  來代替，再來用 ''，然後用  ，接著用 '' ，依此類推。

精選單字：

- typesetting (n.) 排版
- delimit (v.) 標出…的界限，給…劃界
- quotation (n.) 引語，引文，語錄；報價；公司股票在…上市
- mundane (adj.) 世俗的；單調的；平凡的
- oriented 在這當 p.p. 形容詞表示導向的、方向的
- typist (n.) 打字員
- accustomed (adj.) 習慣的；適應了的
- typeset (v.) 為...排字、排版
- identical (adj.) 完全相同的；極為相似的
- arise (v.) 發生；產生；出現；起床

解題思路：

設 `isLeftQuote` bool 變數，用於判斷是否為左右括號。

遇到 `"` 字元就先判斷是否為左右括號，是左括號就輸出波浪鍵那個半形符號兩個，右就是 ''。

不是的話就按原文輸出。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    string line;
    bool isLeftQuote = true;
    
    while (getline(cin, line)){
        
        for (char c : line){
            
            if (c == '"'){
                cout << (isLeftQuote ? "``" : "''");
                isLeftQuote = !isLeftQuote;
            }
            else{
                cout << c;
            }
            
        }
        
        cout << '\n';
    }
    return 0;
}

## 14. Doom's Day Algorithm

PDF Source：https://onlinejudge.org/external/120/12019.pdf

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

題目翻譯：

Doom's Day 演算法不是用來計算世界末日是哪一天的方法。它是一個由數學家 John Horton Conway 創建的演算法，用來計算一週中的哪一天（星期一、星期二等）對應於某個特定日期。

這個演算法的基礎是「doomsday」這個概念，也就是一周中的某一天總是會發生在同一個日期。如 4/4（4 月 4 日）、6/6（6 月 6 日）、8/8（8 月 8 日）、10/10（10 月 10 日）以及 12/12（12 月 12 日）這幾個日期，總會發生在 doomsday。每一年都有屬於自己的 doomsday。

在 2011 年，doomsday 是星期一。所以 4/4、6/6、8/8、10/10 和 12/12 都是星期一。利用這個資訊，你就可以輕鬆計算出其他任何日期是星期幾。如 2011 年 12 月 13 日是星期二，2011 年 12 月 14 日是星期三，以此類推。

其他落在 doomsday 的日期還有 5/9、9/5、7/11 和 11/7。此外，在閏年時，還有 1/11（1 月 11 日）和 2/22（2 月 22 日）這兩個 doomsday，而在平年則是 1/10 和 2/21。

給定 2011 年的某個日期，你需要計算出它是星期幾。

精選單字：

- mathematician (n.) 數學家

解題思路：

先找出一個基準日，也就是 1/1 號那天到底是星期幾，從範例測資推算過後發現 1/1 是星期六。

所以就要先從星期六開始去推算。

接下來建兩個陣列，一個是 monthDays 表示每個月有幾天，這邊我是用 1-based index，比較直覺一點。

再來另一個陣列是存星期一到星期日的，後面要做模運算 ( `%` )，所以索引 0 的地方要是 Sunday，接下來是 Monday 以此類推，如果你要從星期一開始、星期日結束的話就記得 `% 7 + 1`，不然會錯。

然後宣告一個變數 `startDay = 6`，表示在星期六開始。

之後跑 T 次迴圈，裡面設一個變數 `dayPassed = 0`，表示過了幾天，再來裡面有 M 次（月份）迴圈，而迭代值（那個 i）預設為 1，因為在這邊我寫的 monthDays 是以 1 為起始的索引。

那要這個迴圈幹嘛呢？算每個月的天數，加給 dayPassed。

跑完迴圈再寫 `dayPassed += (D - 1);`，把 D 加進去。減 1 是因為假設輸入是 `1 / 1`，等同跟基準日同一天，如果沒減掉會顯示過 1 天。

之後就是 `startDay + dayPassed` 做 `% 7` 運算了。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int T;
    cin >> T;
    
    int monthDays[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    
    string weekDays[7] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
    
    int startDay = 6;
    
    for (int i = 0; i < T; ++i){
        int M, D;
        cin >> M >> D;
        
        int dayPassed = 0;
        for (int m = 1; m < M; ++m){
            dayPassed += monthDays[m];
        }
        dayPassed += (D - 1);
        
        int weekDay = (startDay + dayPassed) % 7;
        
        cout << weekDays[weekDay] << '\n';
    }
    
    return 0;
}

## 15. Jolly Jumpers

PDF Source：https://onlinejudge.org/external/100/10038.pdf

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

題目翻譯：

一個長度為 $n > 0$ 的整數序列，若相鄰元素之間的差的絕對值涵蓋從 $1$ 到 $n − 1$ 的所有整數，則稱該序列為 jolly jumper。如序列 $1 4 2 3$ 是一個 jolly jumper，因為相鄰元素的絕對值的差分別為 $3$ 、 $2$ 和 $1$ 。此定義也表示，任何只有一個整數的序列皆為 jolly jumper。你需要撰寫一個程式，判斷多個序列是否為 jolly jumper。

精選單字：

- jolly (adj.) 興高采烈的，快活的；令人愉快的，愜意的；明亮好看的
- jolly (adv.) 很，非常
- jolly (v.) （說好話）哄，捧，鼓勵
- respectively (adv.) 分別地
- imply (v.) 暗示；暗指

解題思路：

首先釐清題目的意思，題目要求的 jolly jumper 意思是 1 到 n - 1 相鄰元素絕對值的差，每個數字只能出現一次。（如：3 2 2 1 是錯的，要 3 2 1 才可以）

計算差值：`abs(seq[i] - seq[i+1])`。

判斷差值條件：

- 差值必在 $1$ 到 $n - 1$ 之間。
- 差值不能重複出現。
- 用一個 bool 陣列（或 hash table（unordered_map））來記錄差值是否出現過。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int n;
    while (cin >> n){
        
        vector <int> seq(n);
        for (int i = 0; i < n; ++i){
            cin >> seq[i];
        }
        
        vector <bool> diffFound(n, false);
        
        bool isJolly = true;
        
        for (int i = 0; i < n - 1; ++i){
            
            int diff = abs(seq[i] - seq[i + 1]);
            
            if (diff < 1 || diff >= n || diffFound[diff]){
                isJolly = false;
                break;
            }
            
            diffFound[diff] = true;
        }
        
        cout << (isJolly ? "Jolly" : "Not jolly") << '\n';
    }
    return 0;
}

## 16. What is the Probability ?

PDF Source：https://onlinejudge.org/external/100/10056.pdf

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

題目翻譯：

機率一直是電腦演算法中不可或缺的一部分。當確定性演算法無法在短時間內解決問題時，機率性演算法便派上用場。在本題中，我們並不會處理任何機率性演算法。我們只試圖找出某一位玩家獲勝的機率。

遊戲的規則是輪流擲骰子（需注意這個骰子不一定是一般六面的骰子）。當某位玩家擲骰後發生特定事件（例如擲出 3、擲出綠面朝上，或其他條件）時，該玩家即為贏家。總共有 $N$ 名玩家。第一位玩家先擲骰，然後是第二位，一直到第 $N$ 位玩家，再回到第一位玩家，依此輪流進行。當某位玩家擲出期望事件時，即獲勝並結束遊戲。你必須計算其中某一位玩家（第 $I$ 位）的獲勝機率。

精選單字：

- integrate (v.) （使）融入（某社會或群體）；（使）成為一體
- deterministic (adj.) 決定論（者）的（認為一切事物具有不以人的意志為轉移的必然性）
- probabilistic (adj.) 基於概率的

解題思路：

這個牽扯到二項分布+無窮等比級數的概念，在這邊強力推薦楊翰數學（不是業配）：

二項分布：https://www.youtube.com/watch?v=PL2XxMdbqqU&list=PLZwcGSBTi1pPyIh9R3yFk4WjtvVrmI7kb&index=7&pp=iAQB

無窮等比級數：https://www.youtube.com/watch?v=0u2ZpjGbu6o&list=PLZwcGSBTi1pPvthca4so6wgzLaVuOOc6H&index=6

先來個數學推導，玩家數為 $N$ ，成功機率為 $p$ ，求第 $i$ 個玩家的獲勝機率。

第 $i$ 個玩家第一次擲骰子時，成功機率是 $p$ 。如果前面所有玩家都失敗（機率為 $(1-p)$ ），且前一輪所有玩家都失敗，遊戲則繼續。

玩家 $i$ 獲勝的事件可理解為：

:::success
在前一輪所有玩家都失敗的情況下，輪到玩家 $i$ 擲骰子，玩家 $i$ 成功。
:::

前一輪所有玩家擲骰子都失敗的機率是：

$$(1 - p)^N$$

根據這個題目敘述，遊戲可能不只一輪而已，因此玩家 $i$ 獲勝的機率為無窮等比級數：

$$P_i = p \times (1 - p)^{i - 1} \times \sum^{\infty}_{k = 0}((1 - p)^N)^k$$

$(1 - p)^{i - 1}$ 是在同一輪中， $i$ 之前的玩家都失敗的機率。

註： $p \times (1 - p)^{i - 1}$ 就是二項分布了，因為有成功跟失敗這兩種結果，而只要有 1 人成功就結束遊戲，其餘的 $i - 1$ 都會是失敗的結果。

等比級數公式（ $a$ 為首項， $r$ 為公比）：

$$\lim_{n \to \infty}S_n = \frac{a}{1 - r}$$

最後套公式得到：

$$P_i = \frac{p(1 - p)^{i - 1}}{1 - (1 - p)^N}$$

把這個公式代進去程式裡面就是答案了。

另外要注意 `p == 0.0` 機率可能為 $0$ 這件事情，我注意到，沒加就丟 Online Judge，然後就 WA 了。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int S;
    cin >> S;
    
    for (int s = 0; s < S; ++s){
        int N, i;
        double p;
        cin >> N >> p >> i;
        
        if (p == 0.0){
            cout << fixed << setprecision(4) << 0.0 << '\n';
            continue;
        }
        
        double a = p * pow(1 - p, i - 1);
        double b = 1 - pow(1 - p, N);
        cout << fixed << setprecision(4) << a / b << '\n';
    }
    
    return 0;
}

## 17. The Hotel with Infinite Rooms

PDF Source：https://onlinejudge.org/external/101/10170.pdf

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

題目翻譯：

HaluaRuti 市有一家有無限房間的奇怪飯店。而入住本飯店的團體需遵照以下規則：

a) 同時，只能有一個團體中的成員可租用飯店。
b) 每個團體會在入住當天的早上到達，並於退房當天的晚上離開飯店。
c) 當前團體離開後，下一個團體會在隔天早上到來。
d) 新來的團體有一個很重要的性質，就是其成員數會比前一個團體多一人（除非是第一個團體）。你將被給予第一個團體的人數。
e) 一個有 n 位成員的團體會在飯店住 n 天。如：若一個有四位成員的團體在八月一日早上到來，他們會在八月四日晚上離開飯店，接下來有五位成員的團體會在八月五日早上到來，並住五天，依此類推。

給定最初的團體人數，你需要找出在指定日期入住飯店的團體人數。

解題思路：

先 `D-=S`，扣掉第一組停留的天數 S 天。

之後用 `while(D > 0)` 跑，然後按照規則先 `S++`，再把 `D` 扣掉加過後的 `S`，最後輸出 S 就是答案了。

整體思路就是扣到 D 沒天數。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    long long S, D;
    while (cin >> S >> D){
        D -= S;
        while (D > 0){
            S++;
            D -= S;
        }
        cout << S << '\n';
    }
    return 0;
}

## 18. 498-bis

PDF Source：https://onlinejudge.org/external/102/10268.pdf

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

題目翻譯：

在瀏覽「Online Judge 的題目集錦」時，我發現了一個非常有趣的題目，編號為 498，標題是「Polly the Polynomial」。坦白說，我並沒有解出這題，但我從中衍生出這個題目。

這題的所有內容都是從 498 題衍生出來的。特別是，498 題是「…設計來幫助你記住……基礎代數技能，讓世界變得更美好，等等。」本題是為了幫助你記起基本微分代數的技巧，加快讓世界變得更美好的速度，諸如此類。

在 498 題中，你需要評估多項式的數值：

$$a_0x^n+a_1x^{n-1}+ \cdots + a_{n-1}x+a_n$$

而在這題中，你應該計算它的導數。記得導數的定義如下：

$$a_0nx^{n-1}+a_1(n-1)x^{n-2}+ \cdots +a_{n-1}$$

所有的輸入與輸出資料都將可以整數表示，也就是說其絕對值將小於 $2^{31}$ 。

輸入說明：

每組測資兩行，第一行為 $x$ 的值，第二行為一組多項式係數。

輸入應以 EOF 終止。

輸出說明：

計算出微分後的值。

解題思路：

主要用秦九韶算法（又稱霍納法則）去算多項式的值，用一般的指數冪運算時間複雜度是 $O(n^2)$ ，丟 zerojudge 是可以過，但 Online Judge 測資比較強，會直接 TLE。

那秦九韶算法是將多項式以巢狀的形式去計算，假定有個多項式：

$$P(x) = a_nx^n + a_{n-1}x^{n-1}+ \cdots + a_1x + a_0$$

用秦九韶算法就變成：

$$P(x) = (\cdots ((a_nx + a_{n - 1}) x + a_{n - 2}) x + \cdots + a_1)x + a_0$$

這樣可能有點難懂，所以來舉例！假設多項式 $P(x) = 2x^3 - 6x^2 + 2x - 1$ 代入 $x = 3$ ：

秦九韶算法： $P(3) = ((2 \cdot 3 - 6) \cdot 3 + 2) \cdot 3 - 1 = 5$ 。

以下是比較容易記的手算法，在程式上也會這樣寫：

1. 從領導係數開始，將所有係數列出來：`2, -6, 2, -1`
2. 也是從領導係數開始，把它乘上 x（這邊 x 用 3 代入），然後再加下一個係數。
3. 接下來再把上步的結果再乘上 x，然後再加下一個係數，以此類推。

實際算起來就像這樣：

1. $2 \cdot 3 + (- 6) = 0$
2. $0 \cdot 3 + 2 = 2$
3. $2 \cdot 3 + (-1) = 5$

最後就得到 $P(3) = 5$ 。

秦九韶算法的好處是同時只要做 $n$ 次乘法跟 $n$ 次加法，能把時間複雜度降到 $O(n)$ 。

範例程式碼：

在這用字串去讀取兩行，然後用 stringstream 字串流去擷取每個測資的資訊。

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

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

        getline(cin, line);
        stringstream ss2(line);
        vector<ll> coe;
        ll a;
        
        while (ss2 >> a) {
            coe.push_back(a);
        }

        int n = (int)coe.size() - 1;

        ll result = 0;
        for (int i = 0; i < n; ++i) {
            // (n - i) 做微分
            result = result * x + coe[i] * (n - i); // 秦九韶算法
        }

        cout << result << '\n';
    }
    return 0;
}

## 19. Odd Sum

PDF Source：https://onlinejudge.org/external/107/10783.pdf

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

題目翻譯：

給定一個區間 $[a, b]$ ，請你找到在這區間內所有奇數整數的和。如 $[3, 9]$ 內所有奇數整數的和為 $3 + 5 + 7 + 9 = 24$ 。

解題思路：

唯一要注意的就是它是閉區間，for 迴圈記得寫 `i <= b`。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int count = 0;
    int T;
    
    scanf("%d", &T);
    
    while (T--){
        
        count++;
        int sum = 0;
        int a, b;
        
        scanf("%d %d", &a, &b);
        for (int i = a; i <= b; ++i){
            if (i % 2 == 1){
                sum += i;
            }
        }
        
        printf("Case %d: %d\n", count, sum);
    }
    return 0;
}

## 20. Beat the Spread!

PDF Source：https://onlinejudge.org/external/108/10812.pdf

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

題目翻譯：

超級盃星期天要來了！為了打發等待中場廣告和[衣服滑落](https://zh.wikipedia.org/zh-tw/%E8%A1%A3%E6%9C%8D%E6%BB%91%E8%90%BD)的時間，當地的駭客們組織了一個比賽結果賭盤。成員們可以押注兩隊最終得分的總和，或是兩隊得分的絕對差值。

如果給你每種類型賭注的中獎號碼，你能推算出最終得分嗎？

精選單字：

- wardrobe (n.) 衣櫥，衣櫃；（某人的）全部衣服；（劇院等的）服裝保管部，戲服部
- deduce (v.) 推斷，推論

解題思路：

$s$ 為兩隊分數總和，以及分數差絕對值 $d$ ，求兩隊分數 $x$ 和 $y$ （ $x \geq y \geq 0$ ）。

然後來求二元一次聯立方程式囉～

\begin{cases}
x + y = s \\
x - y = d
\end{cases}

然後稍微移項跟上下對消就可得出：

$$x = \frac{s + d}{2}, y = \frac{s - d}{2}$$

以下條件若不符合，則為 "Impossible"。

- $x, y \geq 0$
- $x \geq y$
- $s \geq d$
- $s + d$ 和 $s - d$ 必為偶數，因為這樣才能整除 2 得到整數分數。

在程式設計上就遵照以上條件去撰寫即可。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    
    while (T--){
        int s, d;
        cin >> s >> d;
        
        if (d > s){
            cout << "impossible" << '\n';
            continue;
        }
        
        if ((s + d) % 2 != 0 || (s - d) % 2 != 0){
            cout << "impossible" << '\n';
            continue;
        }
        
        int x = (s + d) / 2, y = (s - d) / 2;
        
        if (x < 0 || y < 0){
            cout << "impossible" << '\n';
            continue;
        }
        
        cout << x << " " << y << '\n';
    }
    return 0;
}