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

一篇十題讓你看到爽！

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 取最小的頻率，為啥？以下是個例子：

1 2	(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 發展出來的一種排版語言。它將原始文字與一些排版指令結合，並產生出一份（希望是）漂亮的文件。漂亮的文件用 left_quotes 和 right_quotes 去表示引號，而非大多數鍵盤所提供的 ""，鍵盤通常沒有方向性的雙引號，但它們有左單引號「 left_quotes_keyboard 」（鍵盤那顆波浪鍵）與右單引號「’」。

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

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

如果原始檔包含：

Sentence1

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

Sentence2

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

Sentence3

註：最後一段我是真的不太會翻，我就把 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$ 。

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

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

實際算起來就像這樣：

$2 \cdot 3 + (- 6) = 0$
$0 \cdot 3 + 2 = 2$
$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

題目翻譯：

超級盃星期天要來了！為了打發等待中場廣告和衣服滑落的時間，當地的駭客們組織了一個比賽結果賭盤。成員們可以押注兩隊最終得分的總和，或是兩隊得分的絕對差值。

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

精選單字：

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