<style> #doc pre { tab-size: 4; overflow: auto; } </style> {%hackmd @debbylin/theme-matcha %} # 113 進階程式設計個人筆記 期待最「優雅」的方式解決，盡可能兼具可讀性、簡潔、效能。（可讀性 >> 簡潔 > 效能） 若有任何建議或想法歡迎留言賜教。 ::: spoiler TODO - [x] 讓明天的自己能看懂 - [x] 使變數命名皆盡可能有意義 - [x] 良好 Coding Style - [x] Morden C++（no C-style array、pefer `static_cast`...） - [x] 清理編譯器警告（最高等級，含隱式符號轉換） - [ ] 補全思路與計算過程 ::: <!-- | 目錄 | | ----- | | [TOC] | --> <table> <thead> <tr> <th>目錄</th> </tr> </thead> <tbody> <tr> <td><ul> <li><a href="#1-基礎CC程式設計複習" title="1. 基礎C/C++程式設計複習">1. 基礎C/C++程式設計複習</a><ul> <li><a href="#a064-成績指標" title="a064: 成績指標">a064: 成績指標</a></li> <li><a href="#a096-時間差計算" title="a096: 時間差計算">a096: 時間差計算</a></li> <li><a href="#a104-雪花片片" title="a104: 雪花片片">a104: 雪花片片</a></li> </ul> </li> <li><a href="#2-函式-公用函式、自定函式" title="2. [函式] 公用函式、自定函式">2. [函式] 公用函式、自定函式</a><ul> <li><a href="#a114-找出最小的完全平方數" title="a114: 找出最小的完全平方數">a114: 找出最小的完全平方數</a></li> <li><a href="#a116-一起回家的日子" title="a116: 一起回家的日子">a116: 一起回家的日子</a></li> <li><a href="#a115-賓果遊戲" title="a115: 賓果遊戲">a115: 賓果遊戲</a></li> </ul> </li> <li><a href="#3-函式-遞迴函式" title="3. [函式] 遞迴函式">3. [函式] 遞迴函式</a><ul> <li><a href="#a157-費波那契數列" title="a157: 費波那契數列">a157: 費波那契數列</a></li> <li><a href="#a158-F91" title="a158: F91">a158: F91</a></li> <li><a href="#a288-執行路徑數" title="a288: 執行路徑數">a288: 執行路徑數</a></li> <li><a href="#a117-三色河內塔" title="a117: 三色河內塔">a117: 三色河內塔</a></li> <li><a href="#a118-2k與四個自然數平方和" title="a118: 2^k與四個自然數平方和">a118: 2^k與四個自然數平方和</a></li> </ul> </li> <li><a href="#4-基本資料型態-指標、多維陣列、串列" title="4. [基本資料型態] 指標、多維陣列、串列">4. [基本資料型態] 指標、多維陣列、串列</a><ul> <li><a href="#a147-促銷活動" title="a147: 促銷活動">a147: 促銷活動</a></li> <li><a href="#a159-錯誤更正" title="a159: 錯誤更正">a159: 錯誤更正</a></li> <li><a href="#a105-爺爺種樹" title="a105: 爺爺種樹">a105: 爺爺種樹</a></li> <li><a href="#a106-賓果遊戲" title="a106: 賓果遊戲">a106: 賓果遊戲</a></li> <li><a href="#a107-加密解密" title="a107: 加密解密">a107: 加密解密</a></li> <li><a href="#a287-文件解壓縮" title="a287: 文件解壓縮">a287: 文件解壓縮</a></li> </ul> </li> <li><a href="#5-基本資料型態-字串" title="5. [基本資料型態] 字串">5. [基本資料型態] 字串</a><ul> <li><a href="#a065-秘密差" title="a065: 秘密差">a065: 秘密差</a></li> <li><a href="#a067-ROT13" title="a067: ROT13">a067: ROT13</a></li> <li><a href="#a109-跑長編碼與資料壓縮" title="a109: 跑長編碼與資料壓縮">a109: 跑長編碼與資料壓縮</a></li> <li><a href="#a108-計算字串間隔距離" title="a108: 計算字串間隔距離">a108: 計算字串間隔距離</a></li> <li><a href="#a110-棒球遊戲" title="a110: 棒球遊戲">a110: 棒球遊戲</a></li> </ul> </li> <li><a href="#6-基本資料型態-結構" title="6. [基本資料型態] 結構">6. [基本資料型態] 結構</a><ul> <li><a href="#a150-多邊形面積" title="a150: 多邊形面積">a150: 多邊形面積</a></li> <li><a href="#a113-99遊戲" title="a113: 99遊戲">a113: 99遊戲</a></li> <li><a href="#a111-排隊" title="a111: 排隊">a111: 排隊</a></li> <li><a href="#a112-動物數量統計" title="a112: 動物數量統計">a112: 動物數量統計</a></li> </ul> </li> <li><a href="#7-基礎資料結構-I--堆疊、佇列" title="7. [基礎資料結構 I ] 堆疊、佇列">7. [基礎資料結構 I ] 堆疊、佇列</a><ul> <li><a href="#a151-後序式求值" title="a151: 後序式求值">a151: 後序式求值</a></li> <li><a href="#a120-中置式轉後置式" title="a120: 中置式轉後置式">a120: 中置式轉後置式</a></li> <li><a href="#a119-括號問題" title="a119: 括號問題">a119: 括號問題</a></li> <li><a href="#a276-撲克牌遊戲：手風琴" title="a276: 撲克牌遊戲：手風琴">a276: 撲克牌遊戲：手風琴</a></li> <li><a href="#a074-單線鐵路" title="a074: 單線鐵路">a074: 單線鐵路</a></li> <li><a href="#a163-印表機佇列" title="a163: 印表機佇列">a163: 印表機佇列</a></li> <li><a href="#a164-團體佇列" title="a164: 團體佇列">a164: 團體佇列</a></li> </ul> </li> <li><a href="#8-基礎資料結構-I--樹狀結構" title="8. [基礎資料結構 I ] 樹狀結構">8. [基礎資料結構 I ] 樹狀結構</a><ul> <li><a href="#a077-小球落下" title="a077: 小球落下">a077: 小球落下</a></li> <li><a href="#a076-二元搜尋樹高度" title="a076: 二元搜尋樹高度">a076: 二元搜尋樹高度</a></li> <li><a href="#a122-血緣關係" title="a122: 血緣關係">a122: 血緣關係</a></li> <li><a href="#a123-樹狀圖分析" title="a123: 樹狀圖分析">a123: 樹狀圖分析</a></li> </ul> </li> <li><a href="#9-基礎資料結構-I--圖形結構" title="9. [基礎資料結構 I ] 圖形結構">9. [基礎資料結構 I ] 圖形結構</a><ul> <li><a href="#a051-城市旅遊" title="a051: 城市旅遊">a051: 城市旅遊</a></li> <li><a href="#a102-油田" title="a102: 油田">a102: 油田</a></li> <li><a href="#a103-小群體" title="a103: 小群體">a103: 小群體</a></li> <li><a href="#a124-二分圖" title="a124: 二分圖">a124: 二分圖</a></li> <li><a href="#a125-觀光景點" title="a125: 觀光景點">a125: 觀光景點</a></li> <li><a href="#a126-馬步問題" title="a126: 馬步問題">a126: 馬步問題</a></li> </ul> </li> <li><a href="#10-基礎演算法-I--複雜度分析、排序" title="10. [基礎演算法 I ] 複雜度分析、排序">10. [基礎演算法 I ] 複雜度分析、排序</a><ul> <li><a href="#a127-連號或不連號" title="a127: 連號或不連號">a127: 連號或不連號</a></li> <li><a href="#a148-字元頻率" title="a148: 字元頻率">a148: 字元頻率</a></li> <li><a href="#a128-Agar.io" title="a128: Agar.io">a128: Agar.io</a></li> <li><a href="#a129-飛天桑妮" title="a129: 飛天桑妮">a129: 飛天桑妮</a></li> </ul> </li> <li><a href="#11-基礎演算法-I--排序與搜尋" title="11. [基礎演算法 I ] 排序與搜尋">11. [基礎演算法 I ] 排序與搜尋</a><ul> <li><a href="#a152-二分搜尋" title="a152: 二分搜尋">a152: 二分搜尋</a></li> <li><a href="#a153-二分法求解" title="a153: 二分法求解">a153: 二分法求解</a></li> <li><a href="#a290-完美購書計畫" title="a290: 完美購書計畫">a290: 完美購書計畫</a></li> <li><a href="#a130-人員調動" title="a130: 人員調動">a130: 人員調動</a></li> <li><a href="#a131-大黑馬" title="a131: 大黑馬">a131: 大黑馬</a></li> <li><a href="#a132-主機排程" title="a132: 主機排程">a132: 主機排程</a></li> </ul> </li> <li><a href="#12-基礎演算法-I--窮舉法" title="12. [基礎演算法 I ] 窮舉法">12. [基礎演算法 I ] 窮舉法</a><ul> <li><a href="#a088-最大乘積" title="a088: 最大乘積">a088: 最大乘積</a></li> <li><a href="#a133-採蘑菇攻略問題" title="a133: 採蘑菇攻略問題">a133: 採蘑菇攻略問題</a></li> <li><a href="#a154-除法" title="a154: 除法">a154: 除法</a></li> <li><a href="#a134-回文日期問題" title="a134: 回文日期問題">a134: 回文日期問題</a></li> <li><a href="#a135-巧克力擺盒" title="a135: 巧克力擺盒">a135: 巧克力擺盒</a></li> </ul> </li> <li><a href="#13-基礎資料結構-II-及基礎演算法-II--貪婪法" title="13. [基礎資料結構 II 及基礎演算法 II ] 貪婪法">13. [基礎資料結構 II 及基礎演算法 II ] 貪婪法</a><ul> <li><a href="#a091-加總的代價" title="a091: 加總的代價">a091: 加總的代價</a></li> <li><a href="#a071-排隊買飲料" title="a071: 排隊買飲料">a071: 排隊買飲料</a></li> <li><a href="#a141-基地台" title="a141: 基地台">a141: 基地台</a></li> <li><a href="#a139-背包置物問題" title="a139: 背包置物問題">a139: 背包置物問題</a></li> <li><a href="#a075-醜數" title="a075: 醜數">a075: 醜數</a></li> </ul> </li> <li><a href="#14-基礎資料結構-II-及基礎演算法-II--分而治之與回溯法" title="14. [基礎資料結構 II 及基礎演算法 II ] 分而治之與回溯法">14. [基礎資料結構 II 及基礎演算法 II ] 分而治之與回溯法</a><ul> <li><a href="#a165-最近點對問題" title="a165: 最近點對問題">a165: 最近點對問題</a></li> <li><a href="#a089-蘇丹王位繼承者" title="a089: 蘇丹王位繼承者">a089: 蘇丹王位繼承者</a></li> <li><a href="#a090-質數環" title="a090: 質數環">a090: 質數環</a></li> <li><a href="#a286-23" title="a286: 23">a286: 23</a></li> <li><a href="#a142-無刻度容器倒水問題" title="a142: 無刻度容器倒水問題">a142: 無刻度容器倒水問題</a></li> </ul> </li> <li><a href="#15-基礎資料結構-II-及基礎演算法-II--動態規劃" title="15. [基礎資料結構 II 及基礎演算法 II ] 動態規劃">15. [基礎資料結構 II 及基礎演算法 II ] 動態規劃</a><ul> <li><a href="#a098-計算方法數" title="a098: 計算方法數">a098: 計算方法數</a></li> <li><a href="#a155-雙子星塔" title="a155: 雙子星塔">a155: 雙子星塔</a></li> <li><a href="#a144-農作物採收問題" title="a144: 農作物採收問題">a144: 農作物採收問題</a></li> <li><a href="#a101-分銅幣" title="a101: 分銅幣">a101: 分銅幣</a></li> <li><a href="#a143-關鍵字搜尋模擬" title="a143: 關鍵字搜尋模擬">a143: 關鍵字搜尋模擬</a></li> <li><a href="#a145-搬家規畫問題" title="a145: 搬家規畫問題">a145: 搬家規畫問題</a></li> </ul> </li> <li><a href="#16-基礎資料結構-II-及基礎演算法-II--樹狀圖形結構演算法" title="16. [基礎資料結構 II 及基礎演算法 II ] 樹狀/圖形結構演算法">16. [基礎資料結構 II 及基礎演算法 II ] 樹狀/圖形結構演算法</a><ul> <li><a href="#a136-元件測試排程問題" title="a136: 元件測試排程問題">a136: 元件測試排程問題</a></li> <li><a href="#a137-勇者冒險" title="a137: 勇者冒險">a137: 勇者冒險</a></li> <li><a href="#a138-最小花費的航空之旅" title="a138: 最小花費的航空之旅">a138: 最小花費的航空之旅</a></li> </ul> </li> <li><a href="#17-題目解析-APCS-程式開發環境、題目解析" title="17. [題目解析] APCS 程式開發環境、題目解析">17. [題目解析] APCS 程式開發環境、題目解析</a><ul> <li><a href="#a160-線段覆蓋長度" title="a160: 線段覆蓋長度">a160: 線段覆蓋長度</a></li> <li><a href="#a140-物品堆疊" title="a140: 物品堆疊">a140: 物品堆疊</a></li> </ul> </li> </ul> </td> </tr> </tbody> </table> ## 1. 基礎C/C++程式設計複習 ### a096: 時間差計算 這題仔細看範例，可以知道是要後減前，再以一天為除數[取模](https://zh.wikipedia.org/zh-tw/模除)。不過很遺憾，C++ 中 `%` 運算子是求餘，結果正負跟隨被除數，所以多加了一個 86400 避免負結果。 ```cpp= #include <iomanip> #include <iostream> #include <string> int main () { std::string str; int n = 86400; std::cin >> str; n -= std::stoi(str.substr(0, 2)) * 3600 + std::stoi(str.substr(3, 2)) * 60 + std::stoi(str.substr(6, 2)); std::cin >> str; n += std::stoi(str.substr(0, 2)) * 3600 + std::stoi(str.substr(3, 2)) * 60 + std::stoi(str.substr(6, 2)); n %= 86400; std::cout << std::setfill('0') << std::setw(2) << n / 3600 << ':' << std::setw(2) << n % 3600 / 60 << ':' << std::setw(2) << n % 60 << std::endl; return 0; } ``` ### a064: 成績指標 沒什麼好說的。 ```cpp= #include <algorithm> #include <iostream> #include <vector> int main () { int n {}; std::cin >> n; std::vector<int> scores(n); int wc {101}; int bc {-1}; for (auto& score : scores) { std::cin >> score; if (score >= 60) { if (score < wc) wc = score; } else if (score > bc) bc = score; } std::sort(scores.begin(), scores.end()); for (const auto& score : scores) std::cout << score << ' '; std::cout << "\n"; if (bc == -1) std::cout << "best case\n"; else std::cout << bc << "\n"; if (wc == 101) std::cout << "worst case\n"; else std::cout << wc << "\n"; return 0; } ``` ### a104: 雪花片片 首先使用瞪眼法，易發現三角形數是 4 的次方，解決。（大誤 設第 $n$ 個圖形有 $f(n)$ 個邊，$g(n)$ 個三角形。不難得出： $$ \begin{align} f(1)&=3\\ f(n)&=f(n-1)\times4\\ g(1)&=1\\ g(n)&=g(n-1)+f(n-1) \end{align} $$ 透過級數公式和數學歸納法可得： $$ \begin{align} f(n) &= 3 \times 4^{n-1}\\ g(n) &= 1 + 3(4^0+4^1+4^2+\dots+4^{n-3}+4^{n-2})\\ &= 1 + 3 \times \frac{4^{n-1}-1}{4-1}\\ &= 1 + 4^{n-1} - 1\\ &= 4^{n-1} \end{align} $$ 設累積三角形數（即題目要求的答案）為 $h(n)$。 $$ \begin{align} h(n) &= g(1) + g(2) + \dots + g(n-1) + g(n)\\ &= 1 + 4 + 16 + \dots + 4^{n-2} + 4^{n-1}\\ &= \frac{4^n-1}{4-1}\\ &= \frac{4^n-1}3 \end{align} $$ 好，雖然推導複雜了點，但蠻簡單的嘛？程式就一段 `(pow(4,n)+1)/3`，怎麼會說是最難的呢？ > 測試資料只有一行，只有一個數字 N，其值為 1 至 <u>120</u> 的整數。 $$ \begin{align} h(120) &= 1 + 4 + 16 + \dots + 4^{118} + 4^{119}\\ &> 4^{119} = 2^{238}\\ &\gg 2^{64} \end{align} $$ > `uint64_t` 的取值為 0 ~ 2^64^-1。 爆炸！由於 C/C++ 沒有內建大整數（是的 Python、Java都有），那就只能手搓大數運算了。也即儲存每一數位，自己做直式運算。 所以我們要做 N 次乘法（迭代$4^n$）、一個減法（$-1$）、再一個除法（$\frac{}3$）直式運算？不，這不優雅。仔細觀察： $$ \begin{align} h(n) &= 1 + 4 + 16 + \dots + 4^{n-3} + 4^{n-2} + 4^{n-1} \\ &= 1 + 4\left(1 + 4 + 16 + \dots + 4^{n-3} + 4^{n-2}\right) \\ &= 1 + 4h(n-1) \\ h(1) &= 1 \end{align} $$ $x \leftarrow 4x+1$ <ruby>遞迴<rp>(</rp><rt style="font-size:0.6em;">疊代</rt><rp>)</rp></ruby>，漂亮！ ```cpp= #include <iostream> #include <vector> int main () { // 倒序存（最高位在最後）比較好計算，故最後輸出時要反過來。 std::vector<int> bigNum {0}; int n {}; std::cin >> n; while (n--) { int c {1}; for (auto& x : bigNum) { const int temp {x * 4 + c}; c = temp / 10; x = temp % 10; } if (c) bigNum.push_back(c); } for (auto i {bigNum.rbegin()}; i != bigNum.rend(); i++) std::cout << *i; std::cout << '\n'; return 0; } ``` 另外其實裡面的 10 可以換成大一點的數字以大幅提升計算效率（只要是十的次方並確保不超過上限），但那樣還要用 `std::setprecision()` 確保 0 不會被吃掉，而我懶就沒弄了。 ## 2. [函式] 公用函式、自定函式 ### a114: 找出最小的完全平方數 一個一格數字確認是否是符合條件的數肯定會爆的，那該如何最佳化呢？ * 由底數找平方數而非反過來檢查 * 跳過奇數，因其平方必亦為奇數 * 若且唯若 $\sqrt{10^{n+1}} \le x < \sqrt{10^{n+2}}$，$x^2$ 的位數為 $n$ * 平方差 $(n+2)^2-n^2 = (2)(2n+2) = 4n+4$ * $\sqrt{10^{2k}} = 10^k$，$\sqrt{10^{2k+1}} = 10^k\sqrt{10}$ * ~~這題才 10 種可能，最好的解法應該是硬編碼才對 XD~~ - 但還是要先寫個程式算過就是（`constexpr`：叫我？） ```cpp= #include <iostream> bool all_even (int n, int length) { while (length--) { if (n % 2) break; n /= 10; } return !n; } int main () { constexpr double sqrt10 {3.1622776602}; int n {}; std::cin >> n; while (n--) { int length {}; std::cin >> length; int base {1}; for (int i = 0; i < (length - 1) / 2; i++) base *= 10; if (length % 2 == 0) base *= sqrt10; base += base % 2; long long square {base * base}; while (!all_even(square, length)) { square += 4 * base + 4; base += 2; } std::cout << square << '\n'; } return 0; } ``` ### a116: 一起回家的日子 > <ruby>不要重新發明輪子<rt>Don't reinvent the wheel</rt></ruby> 這一章叫做公用函式，而傳說有種東西叫[標準庫](https://en.cppreference.com)。 不得不吐槽一下，Python 時就知道要引庫，怎麼變成 C++ 就都不會了。 ```cpp= #include <ctime> #include <iomanip> #include <iostream> int gcd (int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main () { int timelong {1}; int n {}; std::cin >> n; while (n--) { int in {}; std::cin >> in; timelong *= in / gcd(in, timelong); } std::tm date {}; std::cin >> std::get_time(&date, "%Y/%m/%d"); date.tm_mday += timelong; std::mktime(&date); std::cout << std::put_time(&date, "%Y/%m/%d") << "\n"; return 0; } ``` 要不是 [`std::lcm`](https://en.cppreference.com/w/cpp/numeric/lcm) C\++17 才加入，而我們系統很爛的只支援 C\++14，還可以寫得更漂亮。 ### a115: 賓果遊戲 記錄每行列斜的狀態及每個數字所在的座標，最後比對每數字所在之處，有多少臨門一腳的行列斜。 然後我不加 `#pragma` 它不會幫我 `inline`。 ```cpp= #pragma GCC optimize("O3") #include <iostream> #include <vector> template <typename T> constexpr std::size_t u(T i) { return static_cast<std::size_t>(i); } int main () { std::vector<int> x_state(5), y_state(5); int slash_state {0}, bslash_state {0}; std::vector<int> x_pos(25), y_pos(25); bool state[25] = {}; for (int y = 0; y < 5; y++) { for (int x = 0; x < 5; x++) { int number {}; std::cin >> number; number--; x_pos[u(number)] = x; y_pos[u(number)] = y; } } int number {}; std::cin >> number; while (number != -1) { number--; x_state[u(x_pos[u(number)])]++; y_state[u(y_pos[u(number)])]++; if (x_pos[u(number)] == y_pos[u(number)]) bslash_state++; if (x_pos[u(number)] + y_pos[u(number)] == 4) slash_state++; state[number] = true; std::cin >> number; } int max_score {}; int answer {}; for (int i = 24; i >= 0; i--) { if (state[i]) continue; int score { (x_state[u(x_pos[u(i)])] == 4) + (y_state[u(y_pos[u(i)])] == 4) + (x_pos[u(i)] == y_pos[u(i)] && bslash_state == 4) + (x_pos[u(i)] + y_pos[u(i)] == 4 && slash_state == 4) }; if (score >= max_score) { max_score = score; answer = i; } } std::cout << answer + 1 << std::endl; return 0; } ``` ## 3. [函式] 遞迴函式 ### a157: 費波那契數列 題目叫你用遞迴就用遞迴。 遞迴爆炸？[尾遞迴](https://zh.wikipedia.org/zh-tw/尾调用)是種好東西。 ```cpp= #include <iostream> int f (int n, int f_nm1 = 1, int f_nm2 = 0) { return n == 0 ? f_nm2 : f(n - 1, f_nm1 + f_nm2, f_nm1); } int main () { int n {}; while (std::cin >> n) std::cout << f(n) << std::endl; return 0; } ``` ### a158: F91 瞪眼法：名字裡有 91 答案自然是 91。（誤&times;2） 設 $90 \le n \le 100$，歸納法得證： $$ \begin{align} F91(100) &= F91(F91(111))\\ &= F91(101)\\ &= 91\\ F91(n) &=F91(F91(n+11))\\ &=F91(n + 11 - 10)\\ &=F91(n+1)\\ &= 91\\ \end{align} $$ 設 $n \le 89$，假設 $F91(n) = 91$ 歸納法得證： $$ \begin{align} F91(89) &= F91(F91(100))\\ &= F91(91)\\ &= 91\\ F91(n) &=F91(F91(n+11))\\ &=F91(91)\\ &= 91\\ \end{align} $$ 可得： $$ F91(n) = \left\{ \begin{array}{cl} 91 & : \ n \le 100 \\ n-10 & : \ n \ge 101 \end{array} \right. $$ ```cpp= #include <iostream> int f91 (int n) { return n <= 100 ? 91 : n - 10; } int main () { int n; std::cin >> n; while (n != 0) { std::cout << "f91(" << n << ") = " << f91(n) << "\n"; std::cin >> n; } return 0; } ``` ### a288: 執行路徑數 將輸入的所有 `S` 刪去，`IF` 換成 `(1`，`ELSE` 換成 `+1`，`END_IF` 換成 `)`，就能得出答案的算式。例如： ``` IF ELSE IF ELSE END_IF END_IF IF IF ELSE END_IF IF ELSE END_IF ELSE IF ELSE END_IF END_IF ``` 以上輸入的答案即為 `(1+1(1+1))(1(1+1)(1+1)+1(1+1))`，原理學排列組合時已講過，此不再贅述。 再觀察以下計算過程： ``` (1+1(1+1))(1(1+1)(1+1)+1(1+1)) (1+1(2))(1(1+1)(1+1)+1(1+1)) (1+2)(1(1+1)(1+1)+1(1+1)) 3(1(1+1)(1+1)+1(1+1)) 3(1(2)(1+1)+1(1+1)) 3(2(1+1)+1(1+1)) 3(2(2)+1(1+1)) 3(4+1(1+1)) 3(4+1(2)) 3(4+2) 3(6) 18 ``` 轉換成程式碼就是： ```cpp= #include <iostream> #include <stack> #include <string> #include <utility> int main () { int n {}; std::cin >> n; while (n--) { std::stack<std::pair<long long, long long>> stack {}; stack.push({1, 0}); while (true) { std::string keyword {}; std::cin >> keyword; if (keyword == "S") { continue; } else if (keyword == "IF") { stack.push({1, 0}); } else if (keyword == "ELSE") { stack.top().second = stack.top().first; stack.top().first = 1; } else if (keyword == "END_IF") { const auto& temp {stack.top()}; stack.pop(); stack.top().first *= temp.first + temp.second; } else if (keyword == "ENDPROGRAM") { break; } } std::cout << stack.top().first << '\n'; } return 0; } ``` 雖然本題叫遞迴，但遞迴時語句歸屬可能有些燒腦，這邊採用較易理解的堆疊。 另外該寫法還有個好處：雖原題目必有且僅有一個 `ELSE`，只要為本程式碼加一個符號就能使其接受任意多的 `ELSE`……。 :::spoiler 任意多 `ELSE` 第 20 行`=`改為`+=`： ```cpp=20 stack.top().second += stack.top().first; ``` ::: ### a117: 三色河內塔 畫圖解，我懶得把圖放上來了。 由於自始移動都是拿最上面的 n 個環，可以直接數出環的編號。故實際上不需存儲塔的狀態，徑輸出即可。 ```cpp= #include <iostream> int moveTopOneRing (char from, char to, int id){ std::cout << "ring " << id << " : " << from << " => " << to << "\n"; return 1; } int moveTopNRings (int n, char from, char to, char through) { if (n == 1) return moveTopOneRing(from, to, n); int steps {0}; steps += moveTopNRings(n - 1, from, through, to); steps += moveTopOneRing(from, to, n); steps += moveTopNRings(n - 1, through, to, from); return steps; } int distributeTopNRings (int n, char from, char a, char b) { if (n == 0) return 0; if (n == 1) return moveTopOneRing(from, b, n); int steps {0}; steps += moveTopNRings(n - 1, from, a, b); steps += moveTopOneRing(from, b, n); steps += distributeTopNRings(n - 2, a, b, from); return steps; } int main () { int n {}; std::cin >> n; const int steps{ distributeTopNRings(n, 'A', 'B', 'C') }; std::cout << "共需" << steps << "個移動\n"; return 0; } ``` ### a118: 2^k與四個自然數平方和 > 想到「若」很簡單，但欲證明「唯若」就要費很大一番功夫了。 假設 $a_1,a_2,a_3,a_4$ 皆為奇數，設 $a_i=2b_i+1$，則： <!-- &=4b_1^2+4b_1+1+4b_2^2+4b_2+1+4b_3^2+4b_3+1+4b_4^2+4b_4+1\\--> $$ \begin{align} 2^k &=(2b_1+1)^2+(2b_2+1)^2+(2b_3+1)^2+(2b_4+1)^2\\ &=4(b_1^2+b_1+b_2^2+b_2+b_3^2+b_3+b_4^2+b_4 + 1)\\ 2^{k-2} &=b_1^2+b_1+b_2^2+b_2+b_3^2+b_3+b_4^2+b_4 + 1\\ \end{align} $$ 對於任何自然數 $x$，$x\equiv x^2 \pmod2$，可知 $x+x^2 \equiv 0\pmod2$。 $$ \displaylines{ 2^{k-2} \equiv 0 \pmod2 \\ \begin{align} 2^{k-2} &\equiv (b_1^2+b_1)+(b_2^2+b_2)+(b_3^2+b_3)+(b_4^2+b_4) + 1\\ &\equiv 0 + 0 + 0 + 0 +1\\ &\equiv 1\\ 0 &\equiv 1 \Rightarrow\!\Leftarrow\\ \end{align}\pmod2 } $$ 矛盾，故當 $k\ge3$ 時 $a_1,a_2,a_3,a_4$ 不可能皆為奇數。 再假設 $a_1,a_2,a_3,a_4$ 中共兩個奇數，不失一般性的令 $a_1=2b_1+1$、$a_2=2b_2+1$、$a_3=2b_3$、$a_4=2b_4$，則： $$ \begin{align} 2^k&=(2b_1+1)^2+(2b_2+1)^2+(2b_3)^2+(2b_4)^2\\ &=4(b_1^2+b_1+b_2^2+b_2+b_3^2+b_4^2)+2 \end{align} $$ 觀察到： $$ \displaylines{ 2^k \equiv 4\times2^{k-2} \equiv 0 \pmod4 \\ \begin{align} 2^k &\equiv 4(b_1^2+b_1+b_2^2+b_2+b_3^2+b_4^2)+2\\ &\equiv 0 + 2\\ &\equiv 2\\ 0 &\equiv 2 \Rightarrow\!\Leftarrow\\ \end{align}\pmod4 } $$ 矛盾，故當 $k\ge2$ 時 $a_1,a_2,a_3,a_4$ 不可能共兩個奇數。 一個奇數及三個奇數的情況不言自明：奇數平方亦為奇數，奇數個奇數相加結果必為奇數。然 $2^k$ 為偶數，產生矛盾，不可能。 故給定 $k\ge3$，$a_1,a_2,a_3,a_4$ 必皆為偶數，設 $a_i=2b_i$： $$ \begin{align} 2^k &=a_1^2 + a_2^2 + a_3^2 + a_4^2\\ &=(2b_1)^2+(2b_2)^2+(2b_3)^2+(2b_4)^2\\ &=4(b_1^2+b_2^2+b_3^2+2b_4^2)\\ 2^{k-2} &= b_1^2+b_2^2+b_3^2+b_4^2\\ \end{align} $$ 不難看出，對於任意 $k\ge3$，$2^k$ 的所有解 $a_1,a_2,a_3,a_4$ 必定與 $2^{k-2}$ 的所有解 $\frac{a_1}{2},\frac{a_2}{2},\frac{a_3}{2},\frac{a_4}{2}$ 一一對應（對射）。又若 $k-2 \geq 3$，依然可確定它們仍皆為偶數，並同理進一步往下對應，直至所有解都與 $2^2$ 的或 $2^1$ 的解以差了二的冪倍之方式對應。 簡單觀察試算可得知：$2^1$ 時無解，$2^2$ 僅有唯一解 $2^2=1^2+1^2+1^2+1^2$。以上述解的一一對應性推而廣之，綜上可以證明： $$ \displaylines{ 2^k = a_1^2 + a_2^2 + a_3^2 + a_4^2\\ \iff \\ (k = 2n) \land (a_1 = a_2 = a_3 = a_4 = 2^{n-1}) } $$ C++ 寫出來就是： ```cpp= #include <iostream> int main () { int k {}; std::cin >> k; if (k % 2) { std::cout << "0\n"; return 0; } const int ans{ 1 << (k / 2 - 1) }; std::cout << ans << ' ' << ans << ' ' << ans << ' ' << ans << '\n'; return 0; } ``` ## 4. [基本資料型態] 指標、多維陣列、串列 ### a147: 促銷活動 題目要求填空，風格突變請見諒。 ```cpp= #include <iostream> using namespace std; void discount(double& p1, double& p2){ if (p1 == p2) p2 /= 2; } int main(){ double p1, p2; cout << "Original price:" << endl; cin >> p1 >> p2; discount(p1, p2); cout << "Price after discount:" << endl; cout << p1 << " " << p2 << endl; return 0; } ``` ### a159: 錯誤更正 關鍵字「奇偶校驗」。另外奇偶結果等於互斥或（XOR）結果，不必真的去加。 ```cpp= #include <bitset> #include <iostream> int main () { int n {}; std::cin >> n; while (n != 0) { int flippedColumn {0}; int flippedRow {0}; std::bitset<100> columnSum {}; for (int i = 0; i < n; i++) { bool rowSum {false}; for (std::size_t j = 0; j < n; j++) { bool bit {}; std::cin >> bit; rowSum ^= bit; if (bit) columnSum.flip(j); } if (rowSum) flippedRow = flippedRow ? -1 : i + 1; } for (int j = 0; j < n; j++) if (columnSum[static_cast<std::size_t>(j)]) { flippedColumn = flippedColumn ? -1 : j + 1; } if (flippedRow > 0 && flippedColumn > 0) { std::cout << "Change bit (" << flippedRow << "," << flippedColumn << ")\n"; } else if (flippedRow == 0 && flippedColumn == 0) { std::cout << "OK\n"; } else { std::cout << "Corrupt\n"; } std::cin >> n; } return 0; } ``` ### a105: 爺爺種樹 ~~目前該寫法尚未整理，請勿模仿！~~ 重寫完成。 由於 `std::vector<bool>` 的缺陷，這裡以另一種方式儲存。 特別感謝孟學老師提供關於利用定義步進來合併不同情況的思路。 ```cpp= #include <iostream> #include <set> #include <utility> constexpr int sign (int x) { return (x > 0) - (x < 0); } int main () { int x_length {}, y_length {}; std::cin >> x_length >> y_length; std::set<std::pair<int, int>> map {}; int lines {}; std::cin >> lines; while (lines--) { int start_x {}, start_y {}, end_x {}, end_y {}; std::cin >> start_x >> start_y >> end_x >> end_y; const int dx {sign(end_x - start_x)}; const int dy {sign(end_y - start_y)}; for (int x {start_x}, y {start_y}; ; x += dx, y += dy) { map.emplace(x, y); if (x == end_x && y == end_y) break; } } std::cout << map.size() << '\n'; return 0; } ``` ### a106: 賓果遊戲 很多時候會發現硬寫的優雅之處。真去寫四個迴圈不比直接邏輯式還長還醜？ ~~另，可以用結構把 `names` 與 `disks` 結合，但我懶得改了。~~ 改好了。 ```cpp= #include <iostream> #include <utility> #include <vector> bool is_bingo (const std::vector<int>& disk) { return ( !(disk[0] || disk[1] || disk[2] || disk[3] ) || !(disk[4] || disk[5] || disk[6] || disk[7] ) || !(disk[8] || disk[9] || disk[10] || disk[11]) || !(disk[12] || disk[13] || disk[14] || disk[15]) || !(disk[0] || disk[4] || disk[8] || disk[12]) || !(disk[1] || disk[5] || disk[9] || disk[13]) || !(disk[2] || disk[6] || disk[10] || disk[14]) || !(disk[3] || disk[7] || disk[11] || disk[15]) || !(disk[0] || disk[5] || disk[10] || disk[15]) || !(disk[3] || disk[6] || disk[9] || disk[12]) ); } int main () { char symbol {}; std::size_t player_num {}; std::cin >> symbol >> player_num; // std::pair<name, disk> std::vector<std::pair<char, std::vector<int>>> players(player_num, {{}, std::vector<int>(16)}); for (auto& player : players) { std::cin >> player.first; for (auto& n : player.second) std::cin >> n; } std::cin >> symbol; std::vector<char> bingo {}; for (int i {0}; i < 16; i++) { int said_number {}; std::cin >> said_number; std::cout << said_number << ' '; for (auto& player : players) { for (auto& number : player.second) if (number == said_number) number = 0; if (is_bingo(player.second)) bingo.push_back(player.first); } if (!bingo.empty()) break; } for (const auto& name : bingo) std::cout << name << ' '; std::cout << '\n'; return 0; } ``` ### a107: 加密解密 二維陣列平坦化。 ~~目前這個解為了避免隱式符號轉換增加了些複雜。~~ 重寫完成。 ```cpp= #include <cctype> #include <string> #include <iostream> int main() { const std::string tableLower { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' }; const std::string tableUpper { 'E', 'X', 'A', 'M', 'P', 'L', 'B', 'C', 'D', 'F', 'G', 'H', 'I', 'J', 'K', 'N', 'O', 'R', 'S', 'T', 'U', 'V', 'W', 'Y', 'Z' }; std::size_t length {}; std::cin >> length; std::string input(length, '0'); for (auto i {input.rbegin()}; i != input.rend(); i++) std::cin >> *i; const bool is_upper {std::isupper(input[0]) != 0}; const auto decode {is_upper ? tableUpper : tableLower}; const auto encode {is_upper ? tableLower : tableUpper}; for (std::size_t i = 0; i < length; i += 2) { const auto a_pos {decode.find(input[i])}; const auto b_pos {decode.find(input[i + 1])}; std::cout << encode[a_pos / 5 * 5 + b_pos % 5] << encode[b_pos / 5 * 5 + a_pos % 5]; } return 0; } ``` ### a287: 文件解壓縮 題目怎麼說就怎麼做，不必多言。 ```cpp= #include <cctype> #include <iostream> #include <string> #include <vector> int main() { std::string reading {}; std::string input_line {}; std::vector<std::string> words {}; bool reading_word {false}; bool reading_number {false}; while (std::getline(std::cin, input_line)) { if (input_line == "0") return 0; input_line.push_back('\n'); for (const auto& c : input_line) { if (std::isalpha(c) || std::isdigit(c)) { reading.push_back(c); reading_word = std::isalpha(c); reading_number = std::isdigit(c); if (reading_number) continue; } else if (reading_word) { words.push_back(reading); reading.clear(); reading_word = false; } else if (reading_number) { const auto word {std::prev(words.end(), std::stoi(reading))}; std::cout << *word; words.push_back(*word); words.erase(word); reading.clear(); reading_number = false; } std::cout << c; } } return 0; } ``` ## 5. [基本資料型態] 字串 ### a065: 秘密差 透過不斷翻轉符號來達成一加一減，就無需另用一個變數做判斷。 冷知識：`c - '0'` 結果的正確有 C++ 標準保證。 ```cpp= #include <string> #include <iostream> int main () { std::string number {}; std::cin >> number; int secrect_nmber {}; for (const auto& c : number) secrect_nmber = -secrect_nmber + c - '0'; if (secrect_nmber < 0) secrect_nmber *= -1; std::cout << secrect_nmber << '\n'; return 0; } ``` ### a067: ROT13 `std::noskipws` 旗標能避免跳過空白。 都做 ASCII 加減了，ASCII 比大小就不用避諱了。 ```cpp= #include <iostream> int main() { std::cin >> std::noskipws; char c {}; while (std::cin >> c) { if ('a' <= c && c <= 'z') std::cout << static_cast<char>((c - 'a' + 13) % 26 + 'a'); else if ('A' <= c && c <= 'Z') std::cout << static_cast<char>((c - 'A' + 13) % 26 + 'A'); else std::cout << c; }; return 0; } ``` ### a109: 跑長編碼與資料壓縮 注意本題有個大坑：若沒有 `>> std::ws`，`>> n` 吃掉數字後不會吃掉第一行的換行符，將導致迴圈第一次讀入空行（失去了數字的第一行）。有另一種解法是開頭迴圈外多叫一次 `std::getline` 吃掉第一行，或是使用 `std::cin.ignore()` 單獨吃掉數字後的換行符。不過 `std::ws` 本身有讓 debug 比較方便的好處。 `std::bitset<n>(x)`是個輸出二進位字串的小技巧。 ```cpp= #include <bitset> #include <cmath> #include <iostream> #include <sstream> #include <string> enum State { reading_0 = '0', reading_1 = '1', not_reading, error }; int main() { int n {}; std::cin >> n; while (n--) { std::string line {}; std::getline(std::cin >> std::ws, line); std::stringstream sstream {}; unsigned int length {1}; double size {1}; State state {not_reading}; for (const auto& c : line) { if (state == c && length < 7) length++; else if (state != not_reading) { sstream << static_cast<char>(state) << std::bitset<3>(length) << ' '; length = 1; size++; } if (c == '0') state = reading_0; else if (c == '1') state = reading_1; else { std::cout << "-1\n"; state = error; break; } } if (state == error) continue; sstream << static_cast<char>(state) << std::bitset<3>(length) << ' ' << std::round(size * 400. / line.size()) << "%\n"; std::cout << sstream.rdbuf(); } return 0; } ``` ### a108: 計算字串間隔距離 * 統一大小寫 = 忽略大小寫 * 善用布林標誌 ```cpp= #include <cctype> #include <iostream> #include <string> int main() { std::string str {}; std::cin >> str; char find {}; std::cin >> find; for (auto& c : str) c = static_cast<char>(std::toupper(c)); find = static_cast<char>(std::toupper(find)); std::size_t start {0}; bool first {true}; while (true) { const auto pos {str.find(find, start)}; if (pos == str.npos) break; if (!first) std::cout << pos - start + 1 << " "; else first = false; start = pos + 1; } std::cout << "\n"; return 0; } ``` ### a110: 棒球遊戲 * 平坦化打擊至有序陣列 * 利用增長的陣列紀錄選手的跑壘紀錄 ```cpp= #include <bitset> #include <iostream> #include <string> #include <vector> enum class Hit { B1, B2, B3, B4, OUT, UNKNOWN }; Hit prase_hit_name (const std::string& name) { if (name == "1B") return Hit::B1; else if (name == "2B") return Hit::B2; else if (name == "3B") return Hit::B3; else if (name == "HR") return Hit::B4; else if (name == "FO" || name == "GO" || name == "SO") return Hit::OUT; else return Hit::UNKNOWN; } int main() { constexpr int player_number {9}; constexpr std::size_t max_step {27}; std::vector<Hit> hits(max_step, Hit::UNKNOWN); for (int i {0}; i < player_number; i++) { int hit_times {}; std::cin >> hit_times; for (int j {0}; j < hit_times; j++) { std::string hit_name {}; std::cin >> hit_name; const std::size_t index {static_cast<std::size_t>(player_number * j + i)}; if (index >= max_step) continue; hits[index] = prase_hit_name(hit_name); } } int target_num {}; std::cin >> target_num; std::bitset<max_step * 4> player {}; std::size_t move_times {0}; int out_times {0}; for (std::size_t i = 0; out_times < target_num; i++) { if (hits[i] == Hit::OUT) { out_times++; if (out_times % 3) continue; if (move_times <= 3) player.reset(); else { player.reset(move_times - 1); player.reset(move_times - 2); player.reset(move_times - 3); } continue; } player.set(move_times); switch (hits[i]) { case Hit::B1: move_times += 1; break; case Hit::B2: move_times += 2; break; case Hit::B3: move_times += 3; break; case Hit::B4: move_times += 4; break; default: break; } } if (move_times < 3) move_times = 0; else move_times -= 3; int score {0}; for (std::size_t i {0}; i < move_times; i++) score += player[i]; std::cout << score << "\n"; return 0; } ``` ## 6. [基本資料型態] 結構 ### a150: 多邊形面積 外積大法好。 ```cpp= #include <iomanip> #include <iostream> struct Pos { double x {}; double y {}; }; double cross (const Pos& a, const Pos& b) { return a.x * b.y - b.x * a.y; } int main () { int count {}; std::cin >> count; Pos first {}; std::cin >> first.x >> first.y; Pos last {first}; double area {0}; while (--count) { Pos now {}; std::cin >> now.x >> now.y; area += cross(last, now); last = now; } area += cross(last, first); area /= -2; std::cout << std::setprecision(2) << std::fixed << area; return 0; } ``` ### a113: 99遊戲 ```cpp= #include <iostream> #include <string> #include <utility> #include <vector> int main () { constexpr std::size_t players_num {4}; constexpr std::size_t cards {13}; // pair<名字, 手牌> std::vector<std::pair<std::string, std::vector<std::string>>> players( players_num, {{}, std::vector<std::string>(cards)} ); for (auto& player : players) { std::cin >> player.first; for (auto card {player.second.rbegin()}; card != player.second.rend(); card++) { std::cin >> *card; } } bool reversed {false}; int num {0}; std::size_t current_player_id {0}; while (true) { auto& player {players[current_player_id]}; const std::string card {player.second.back()}; player.second.pop_back(); if (card == "A") num = 0; else if (card == "4") reversed = !reversed; else if (card == "5" || card == "J") {} else if (card == "10") num += (num > 99 - 10) ? -10 : 10; else if (card == "Q") num += (num > 99 - 20) ? -20 : 20; else if (card == "K") num = 99; else num += std::stoi(card); if (num > 99) { std::cout << player.first << "\n" << player.second.size() << "\n"; return 0; } else if (player.second.empty()) { std::cout << player.first << "\n" << num << "\n"; return 0; } if (reversed) current_player_id += players_num - 1; else current_player_id += 1; current_player_id %= players_num; } return 0; } ``` ### a111: 排隊 ```cpp= #include <algorithm> #include <iostream> #include <utility> #include <vector> int main () { std::size_t numberOfCustomers {}; std::cin >> numberOfCustomers; std::vector<std::pair<int, int>> customers(numberOfCustomers); for (auto& customer : customers) { std::cin >> customer.first >> customer.second; } std::size_t max_line_long {0}; int clock {0}; std::size_t alreadyComing {0}; for (std::size_t i {0}; i < numberOfCustomers; i++) { if (clock < customers[i].first) clock = customers[i].first; clock += customers[i].second; if (alreadyComing < i) alreadyComing = i; for (std::size_t j {alreadyComing}; customers[j].first <= clock && j < numberOfCustomers; j++) alreadyComing = j; if (max_line_long < alreadyComing - i) max_line_long = alreadyComing - i; } std::cout << max_line_long << "\n"; return 0; } ``` ### a112: 動物數量統計 自己寫一個有序映射結構。 ```cpp= #include <iostream> #include <map> #include <vector> template <typename Key, typename T> struct OrderMap { std::map<Key, T> content {}; std::vector<Key> order {}; T& operator[] (const Key& key) { const auto& p {content.find(key)}; if (p == content.end()) { order.push_back(key); return content[key]; } return p->second; } const T& at (const Key& key) const { return content.at(key); } }; int main () { int lines {}; std::cin >> lines; OrderMap<std::string, OrderMap<std::string, int>> locations {}; while (lines--) { std::string animal {}; int numbers {}; std::string location {}; std::cin >> animal >> numbers >> location; locations[location][animal] += numbers; } for (const auto& location : locations.order) { std::cout << location << ":"; const auto& animals {locations.at(location)}; bool first {true}; for (const auto& animal : animals.order) { if (first) first = false; else std::cout << ","; std::cout << animal << " " << animals.at(animal); } std::cout << "\n"; } return 0; } ``` ## 7. [基礎資料結構 I ] 堆疊、佇列 ### a151: 後序式求值 ```cpp= #include <cctype> #include <iostream> #include <stack> #include <string> int main () { std::string line {}; while (std::getline(std::cin, line)) { std::stack<int> stack {}; for (const auto& c : line) { if (std::isdigit(c)) { stack.push(c - '0'); continue; } int b {stack.top()}; stack.pop(); int a {stack.top()}; stack.pop(); switch (c) { case '+': stack.push(a + b); break; case '-': stack.push(a - b); break; case '*': stack.push(a * b); break; case '/': stack.push(a / b); break; case '%': stack.push(a % b); break; } } std::cout << stack.top() << "\n"; } return 0; } ``` ### a120: 中置式轉後置式 有些語意問題，不想改了。 ```cpp= #include <iostream> #include <stack> enum class Operator { Add, Minus, Multipy, Divide, LeftBrace, RightBrace, Err }; bool get_op_priority (Operator left, Operator right) { if ( (right == Operator::Divide || right == Operator::Multipy) && (left == Operator::Add || left == Operator::Minus) ) return false; if ( left == Operator::LeftBrace || right == Operator::LeftBrace ) return false; return true; } Operator prase_op (char c) { return c == '+' ? Operator::Add : c == '-' ? Operator::Minus : c == '*' ? Operator::Multipy : c == '/' ? Operator::Divide : c == '(' ? Operator::LeftBrace : c == ')' ? Operator::RightBrace : Operator::Err; } char op_to_char (Operator op) { return op == Operator::Add ? '+' : op == Operator::Minus ? '-' : op == Operator::Multipy ? '*' : op == Operator::Divide ? '/' : '?'; } int main() { std::string line {}; std::stack<Operator> ops {}; char c {}; while (std::cin >> c) { const Operator op {prase_op(c)}; if (op == Operator::Err) { std::cout << c; continue; } if (op == Operator::RightBrace) { while (ops.top() != Operator::LeftBrace) { std::cout << op_to_char(ops.top()); ops.pop(); } ops.pop(); continue; } while (!ops.empty() && get_op_priority(ops.top(), op)) { std::cout << op_to_char(ops.top()); ops.pop(); } ops.push(op); } while (!ops.empty()) { std::cout << op_to_char(ops.top()); ops.pop(); } std::cout << "\n"; return 0; } ``` ### a119: 括號問題 只有一種括號能搞出什麼花樣。（汗 僅一種取值的堆疊所剩的資訊只有長度，無異於一個整型變數。 ```cpp= #include <iostream> int main () { int level {}; int number {}; char c {}; while (std::cin >> c) { if (c == '(') { level++; number++; } else { level--; if (level < 0) break; } } if (level != 0) number = 0; std::cout << number << "\n"; return 0; } ``` ### a276: 撲克牌遊戲：手風琴 順便練習一下疊代器的使用。 ```cpp= #include <iostream> #include <stack> #include <utility> #include <vector> using piles_t = std::vector<std::stack<std::pair<char, char>>>; bool match (const piles_t::iterator& a, const piles_t::iterator& b) { return a->top().first == b->top().first || a->top().second == b->top().second; } bool try_move (piles_t& piles) { for (auto from {piles.begin() + 1}; from != piles.end(); from++) { auto to {from}; while (true) { const auto i {to - piles.begin()}; if (i >= 3 && match(from, to - 3)) to -= 3; else if (i >= 1 && match(from, to - 1)) to -= 1; else break; } if (to == from) continue; to->push(from->top()); from->pop(); if (from->empty()) piles.erase(from); return true; } return false; } int main () { constexpr std::size_t cards_num {52}; while (true) { piles_t piles(cards_num); for (auto& pile : piles) { char rank {}, suit {}; std::cin >> rank >> suit; if (rank == '#') return 0; pile.push({rank, suit}); } while (try_move(piles)) {} if (piles.size() == 1) std::cout << "1 pile remaining:"; else std::cout << piles.size() << " piles remaining:"; for (const auto& pile : piles) { std::cout << " " << pile.size(); } std::cout << "\n"; } } ``` ### a074: 單線鐵路 無需儲存 A 端狀態，因為固定順序且無法回頭。亦無需儲存 B，因為完成的已與後續無關。 這是第一個 `fastio()` 能給出顯著提升的題目，就順道加了。 ```cpp= #include <iostream> #include <stack> void fastio () { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); } bool solve (int cars_num) { std::stack<int> station {}; int front_car {1}; // A 端最外面一臺之編號 bool fail {false}; while (cars_num--) { int n {}; std::cin >> n; if (!n) return false; if (fail) continue; if (!station.empty() && station.top() == n) { station.pop(); continue; } while (front_car < n) station.push(front_car++); if (front_car != n) fail = true; else front_car++; } if (fail) std::cout << "No\n"; else std::cout << "Yes\n"; return true; } int main () { fastio(); int cars_num {}; std::cin >> cars_num; while (cars_num) { while (solve(cars_num)) {} std::cin >> cars_num; } } ``` ### a163: 印表機佇列 ||~~前一題還在 90%，稍後補。~~|| 頭放尾、頭放尾、條件符合不放尾，頭放尾移動整個陣列不就相當於一動視線嗎？盡管這題名叫「佇列」，但用佇列解才是最麻煩的，其操作本質上顯然是「（單向）環狀鏈結串列」。 ```cpp= #pragma GCC optimize("O3") #include <array> #include <forward_list> #include <iostream> template <typename T> constexpr std::size_t u(T i) { return static_cast<std::size_t>(i); } int main () { constexpr int max_priority {9}; int tests {}; std::cin >> tests; while (tests--) { std::array<int, max_priority> priority_count {}; int length {}, target_i {}; std::cin >> length >> target_i; std::forward_list<int> notaqueue {}; auto last {notaqueue.before_begin()}; auto target {last}; int priority {}; for (int i = 0; i < length; i++) { int file {}; std::cin >> file; priority_count[u(file - 1)]++; last = notaqueue.insert_after(last, file); if (i == target_i) target = last; if (file > priority) priority = file; } int time {0}; while (true) { auto next {std::next(last)}; if (next == notaqueue.end()) last = notaqueue.before_begin(); else if (*next == priority) { time++; if (next == target) break; notaqueue.erase_after(last); priority_count[u(priority - 1)]--; while (!priority_count[u(priority - 1)]) priority--; } else last = next; } std::cout << time << "\n"; } } ``` 甚至這題都還不用真的使用鏈結串列，因為並沒有必要真的「擦除」印出來的東西，優先權打掉就好。反正只有九種優先權，仔細想想就會發現循環次數並不會超過九次。 ```cpp= #pragma GCC optimize("O3") #include <array> #include <iostream> #include <vector> template <typename T> constexpr std::size_t u(T i) { return static_cast<std::size_t>(i); } int main () { constexpr int max_priority {9}; int tests {}; std::cin >> tests; while (tests--) { std::array<int, max_priority> priority_count {}; int length {}, target {}; std::cin >> length >> target; std::vector<int> notaqueue(u(length)); int priority {}; for (int i = 0; i < length; i++) { int file {}; std::cin >> file; priority_count[u(file - 1)]++; notaqueue[u(i)] = file; if (file > priority) priority = file; } int time {0}; int index {0}; while (true) { if (notaqueue[u(index)] == priority) { time++; if (index == target) break; notaqueue[u(index)] = 0; priority_count[u(priority - 1)]--; while (!priority_count[u(priority - 1)]) priority--; } index = (index + 1) % length; } std::cout << time << "\n"; } } ``` ### a164: 團體佇列 ```cpp= #include <iostream> #include <map> #include <queue> #include <string> int main () { int id { 1 }; while (true) { std::map<int, int> member_groups {}; int group_num {}; std::cin >> group_num; if (group_num == 0) return 0; std::cout << "Scenario #" << id++ << '\n'; for (int group_id { 0 }; group_id < group_num; group_id++) { int member_num {}; std::cin >> member_num; while (member_num--) { int member {}; std::cin >> member; member_groups.emplace(member, group_id); } } std::map<int, std::queue<int>> grounps {}; std::queue<int> grounp_queue {}; while (true) { std::string command; std::cin >> command; if (command == "STOP") break; if (command == "ENQUEUE") { int ele {}; std::cin >> ele; const int grounp_id { member_groups.at(ele) }; auto& grounp { grounps[grounp_id] }; if (grounp.empty()) grounp_queue.push(grounp_id); grounp.push(ele); } else if (command == "DEQUEUE") { auto& grounp { grounps.at(grounp_queue.front()) }; std::cout << grounp.front() << '\n'; grounp.pop(); if (grounp.empty()) grounp_queue.pop(); } } std::cout << '\n'; } } ``` ## 8. [基礎資料結構 I ] 樹狀結構 ### a077: 小球落下 解釋待補.jpg ```cpp= #include <iostream> int main () { int tests {}; std::cin >> tests; while (tests--) { unsigned int depth {}, bolls {}; std::cin >> depth >> bolls; bolls--; unsigned int ans {1}; while (--depth) { ans <<= 1; ans |= bolls & 1; bolls >>= 1; } std::cout << ans << '\n'; } return 0; } ``` ### a076: 二元搜尋樹高度 比起硬壓，真寫一個二元樹感覺才是最合適的。 ```cpp= #include <algorithm> #include <iostream> struct BST { int value {}; BST* left {nullptr}; BST* right {nullptr}; int insert (int n, int deep = 1) { auto& next {n <= value ? left : right}; if (next != nullptr) return next->insert(n, deep + 1); next = new BST {n}; return deep + 1; } }; int main () { int n {}; std::cin >> n; BST root {n}; int maxdeep {0}; while (std::cin >> n) maxdeep = std::max(maxdeep, root.insert(n)); std::cout << maxdeep << '\n'; return 0; } ``` ### a122: 血緣關係 分治大法好。另外提醒基於樹為無環連通圖，任何一點都可做為根結點。 ```cpp= #pragma GCC optimize("O3") #include <iostream> #include <tuple> #include <utility> #include <vector> // C++14 都十年了還用啥前處理器巨集 using tree_t = std::vector<std::vector<int>>; constexpr void max_assign (int& a, int b) { if (a < b) a = b; } constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); } void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); } std::pair<int, int> max_distance_and_deep (const tree_t& tree, int node = 0) { int deep_first {0}; int deep_second {0}; int max_distance {0}; for (const auto& child : tree[u(node)]) { int distence {}, deep {}; std::tie(distence, deep) = max_distance_and_deep(tree, child); max_assign(max_distance, distence); if (deep >= deep_first) { deep_second = deep_first; deep_first = deep; } else max_assign(deep_second, deep); } max_assign(max_distance, deep_first + deep_second); return {max_distance, deep_first + 1}; } int main () { fastio(); int nodes_num {}; std::cin >> nodes_num; tree_t tree(u(nodes_num)); // vector<bool> std::vector<char> has_parent(u(nodes_num), false); for (int i {1}; i < nodes_num; i++) { int a {}, b {}; std::cin >> a >> b; tree[u(a)].push_back(b); has_parent[u(b)] = true; } int root {-1}; while (has_parent[u(++root)]) {} std::cout << max_distance_and_deep(tree, root).first << '\n'; return 0; } ``` ### a123: 樹狀圖分析 跟上一題幾乎一模一樣，不過小改了幾個地方的寫法。 ```cpp= #pragma GCC optimize("O3") #include <iostream> #include <utility> #include <vector> using tree_t = std::vector<std::vector<int>>; constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); } void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); } std::pair<int, int> max_deepsum_and_deep (const tree_t& tree, int node) { int max_deep {0}; int deep_sum_sum {0}; for (const auto& child : tree[u(node - 1)]) { const auto& child_data {max_deepsum_and_deep(tree, child)}; if (max_deep < child_data.second) max_deep = child_data.second; deep_sum_sum += child_data.first; } return {deep_sum_sum + max_deep, max_deep + 1}; } int main () { fastio(); int nodes_num {}; std::cin >> nodes_num; tree_t tree(u(nodes_num)); // vector<bool> std::vector<char> has_parent(u(nodes_num), false); for (auto& node : tree) { int child_num {}; std::cin >> child_num; while (child_num--) { int child {}; std::cin >> child; has_parent[u(child - 1)] = true; node.push_back(child); } } int root {0}; while (has_parent[u(root++)]) {} std::cout << root << '\n' << max_deepsum_and_deep(tree, root).first << '\n'; return 0; } ``` ## 9. [基礎資料結構 I ] 圖形結構 ### a051: 城市旅遊 此乃深度優先搜尋。 ```cpp= #pragma GCC optimize("O3") #include <bitset> #include <iostream> #include <vector> constexpr int max_cities {800}; using graph_t = std::vector<std::vector<int>>; constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); } void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); } bool dfs (const graph_t& graph, int target, int from, std::bitset<max_cities>& visited) { visited.set(u(from - 1)); for (const auto& to : graph[u(from - 1)]) { if ( to == target || !visited.test(u(to - 1)) && dfs(graph, target, to, visited) ) return true; } return false; } int main () { fastio(); int cities_num {}, roads_num {}; std::cin >> cities_num >> roads_num; graph_t graph(u(cities_num)); while (roads_num--) { int from {}, to {}; std::cin >> from >> to; graph[u(from - 1)].push_back(to); } int from {}, target {}; std::cin >> from >> target; std::bitset<max_cities> visited {}; if (dfs(graph, target, from, visited)) std::cout << "Yes\n"; else std::cout << "No\n"; return 0; } ``` ### a102: 油田 是的，完全沒在最佳化。 ```cpp= #pragma GCC optimize("O3") #include <bitset> #include <iostream> constexpr int max_width {100 + 2}; using ground_t = std::bitset<max_width * max_width>; constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); } void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); } void clear_nearby (ground_t& ground, int pos) { static constexpr int near[] { -max_width - 1, -max_width, -max_width + 1, -1, +1, +max_width - 1, +max_width, +max_width + 1 }; if (!ground[u(pos)]) return; ground[u(pos)] = false; for (const auto& diff : near) clear_nearby(ground, pos + diff); } int main () { fastio(); while (true) { int rows {}, colums {}; std::cin >> rows >> colums; if (rows == 0) return 0; ground_t ground {}; for (int y {1}; y <= rows; y++) { for (int x {1}; x <= colums; x++) { char symbol {}; std::cin >> symbol; if (symbol == '@') ground[u(y * max_width + x)] = true; } } int number {0}; while (true) { int pos {}; while (pos < ground.size() && !ground[u(pos)]) pos++; if (pos == ground.size()) break; number++; clear_nearby(ground, pos); } std::cout << number << '\n'; } } ``` ### a103: 小群體 ```cpp= #pragma GCC optimize("O3") #include <iostream> #include <vector> constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); } void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); } int main () { fastio(); int people {}; std::cin >> people; std::vector<int> friend_map(people); for (auto& frind : friend_map) std::cin >> frind; int grounps {}; for (int i = 0; i < people; i++) { int pos {i}; do { const int temp {friend_map[u(pos)]}; friend_map[u(pos)] = -1; pos = temp; } while (pos != -1 && pos != i); if (pos != -1) grounps++; } std::cout << grounps << '\n'; return 0; } ``` ### a124: 二分圖 題目描述直接給思路是不是太過貼心了。 還有另一種更好但更麻煩的解法懶得弄了。 ```cpp= #pragma GCC optimize("O3") #include <algorithm> #include <iostream> #include <stack> #include <vector> template <typename T> constexpr std::size_t u (T i) { return static_cast<std::size_t>(i); } void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); } int main () { fastio(); int vertices_num {}, edges_num {}; std::cin >> vertices_num >> edges_num; std::vector<std::vector<int>> graph(u(vertices_num)); while (edges_num--) { int from {}, to {}; std::cin >> from >> to; graph[u(from - 1)].push_back(to - 1); graph[u(to - 1)].push_back(from - 1); } // std::vector<bool> std::vector<char> visited(u(vertices_num)); std::vector<char> color(u(vertices_num)); int answer {0}; while (true) { int id {-1}; while (++id < vertices_num && visited[u(id)]) {} if (id == vertices_num) break; std::stack<int> to_visit {}; to_visit.push(id); int white {1}; int black {0}; visited[u(id)] = true; while (!to_visit.empty()) { const int now {to_visit.top()}; to_visit.pop(); for (const auto& near : graph[u(now)]) { if (visited[u(near)] && color[u(near)] == color[u(now)]) { std::cout << "0\n"; return 0; } if (visited[u(near)]) continue; visited[u(near)] = true; color[u(near)] = !color[u(now)]; if (color[u(near)]) black++; else white++; to_visit.push(near); } } answer += std::min(black, white); } std::cout << answer << '\n'; return 0; } ``` ### a125: 觀光景點 ```cpp= #pragma GCC optimize("O3") #include <iostream> #include <stack> #include <utility> #include <vector> #include <bitset> template <typename T> constexpr std::size_t u (T i) { return static_cast<std::size_t>(i); } void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); } int main () { fastio(); int vertices_num {}, root {}, max_cost {}; std::cin >> vertices_num >> root >> max_cost; std::vector<std::vector<std::pair<int, int>>> graph(u(vertices_num)); for (int i {0}; i < vertices_num - 1; i++) { int from {}, to {}, cost {}; std::cin >> from >> to >> cost; graph[u(from - 1)].emplace_back(to - 1, cost); graph[u(to - 1)].emplace_back(from - 1, cost); } std::stack<int> to_visit {}; std::bitset<5000> visited {}; visited.set(u(root - 1)); to_visit.push(root - 1); int answer {0}; while (!to_visit.empty()) { const int vertex {to_visit.top()}; to_visit.pop(); for (const auto& edge : graph[u(vertex)]) { if (visited[u(edge.first)] || edge.second < max_cost) continue; answer++; to_visit.push(edge.first); visited.set(u(edge.first)); } } std::cout << answer << '\n'; return 0; } ``` ### a126: 馬步問題 嘛不是很好看。罷了。 ```cpp= #include <bitset> #include <iostream> #include <stack> #include <vector> constexpr inline std::size_t u (int i) { return static_cast<std::size_t>(i); } int main () { static constexpr int dx[] { 1, 1, -1, -1, 2, 2, -2, -2 }; static constexpr int dy[] { 2, -2, 2, -2, 1, -1, 1, -1 }; constexpr int row {3}; constexpr int max_colum {10}; int colum {}; std::cin >> colum; const int length {colum * row}; std::vector<int> way {}; std::vector<int> answer(u(length), 100); std::stack<int> chooses {}; std::bitset<row* max_colum> visited {}; chooses.push(-1); way.push_back(0); visited[0] = true; while (!chooses.empty()) { const int choose {++chooses.top()}; if (choose == 8) { chooses.pop(); visited[u(way.back())] = false; way.pop_back(); continue; } const int x {way.back() % colum + dx[choose]}; const int y {way.back() / colum + dy[choose]}; const int pos {y * colum + x}; if (x >= colum || x < 0 || y >= row || y < 0 || visited[u(pos)]) continue; way.push_back(pos); visited[u(pos)] = true; if (way.size() != length) { chooses.push(-1); continue; } std::vector<int> temp(u(length)); for (int i = 0; i < length; i++) temp[u(way[u(i)])] = i + 1; if (temp < answer) answer = temp; chooses.push(7); } if (answer[0] == 100) { std::cout << "0\n"; return 0; } for (const auto& x : answer) std::cout << x << ' '; std::cout << '\n'; return 0; } ``` ## 10. [基礎演算法 I ] 複雜度分析、排序 ### a127: 連號或不連號 我宣布這是最簡單的一題，沒有之一。 ```cpp= #include <iostream> int main () { int num {}; std::cin >> num; int min {1000}; int max {0}; for (int i = 0; i < num; i++) { int number {}; std::cin >> number; if (max < number) max = number; if (min > number) min = number; } std::cout << min << ' ' << max << ' ' << (max - min + 1 == num ? "yes" : "no"); return 0; } ``` ### a148: 字元頻率 糾結了一下要用 `std::vector` + `std::sort` 還是直接用 `std::priority_queue`。 ```cpp= #include <algorithm> #include <iostream> #include <map> #include <string> #include <utility> #include <vector> int main () { std::string line {}; while (std::getline(std::cin, line)) { std::map<int, int> nums {}; for (const auto& c : line) nums[c]++; std::vector<std::pair<int, int>> answer(nums.begin(), nums.end()); std::sort(answer.begin(), answer.end(), [](const auto& a, const auto& b) { return a.second == b.second ? a.first > b.first : a.second < b.second; }); for (const auto& ele : answer) std::cout << ele.first << ' ' << ele.second << '\n'; std::cout << '\n'; } return 0; } ``` ### a128: Agar.io ```cpp= #include <algorithm> #include <iostream> #include <vector> template<typename T> void merge (std::vector<T>& to, const std::vector<T>& from) { to.insert(to.end(), from.begin(), from.end()); } int main () { std::size_t number {}; int times {}; std::cin >> number >> times; std::vector<std::vector<int>> cells(number); for (int i {0}; i < number; i++) cells[static_cast<std::size_t>(i)].push_back(i + 1); while (times--) { std::size_t a {}, b {}; std::cin >> a >> b; a--; b--; if (cells[b].size() > cells[a].size()) merge(cells[b], cells[a]); else merge(cells[a], cells[b]); } const auto max {std::max_element(cells.begin(), cells.end(), [](const auto& a, const auto& b) { return a.size() < b.size(); })}; std::cout << max - cells.begin() + 1 << '\n'; std::sort(max->begin(), max->end()); for (const auto& eat : *max) std::cout << eat << ' '; std::cout << '\n'; return 0; } ``` ### a129: 飛天桑妮 這題其實我少考慮情況 $d(t_1, t_{\pi(i+1)}) = d(t_1, t_{\pi(i)})$，不過顯然寫測資的人也沒考慮到，所以管他的。 ```cpp= #include <algorithm> #include <iostream> #include <utility> #include <vector> void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); } int main () { fastio(); std::size_t trees_num {}; std::cin >> trees_num; std::vector<std::pair<int, int>> trees(trees_num); for (auto& tree : trees) { int x {}, y {}, hight {}; std::cin >> x >> y >> hight; tree.first = x * x + y * y; tree.second = hight; } std::sort(trees.begin(), trees.end()); int happyness {0}; int highest {0}; for (const auto& tree : trees) { highest = std::max(highest, tree.second); happyness = std::max(happyness, highest - tree.second); } std::cout << happyness << '\n'; return 0; } ``` ## 11. [基礎演算法 I ] 排序與搜尋 ### a152: 二分搜尋 就先不邪道了，乖乖寫。 ```cpp= #include <iostream> #include <vector> int main () { std::size_t length {}; std::cin >> length; std::vector<int> numbers(length); for (auto& number : numbers) std::cin >> number; int target {}; std::cin >> target; std::size_t left {0}; // closed std::size_t right {length}; // open int times {0}; while (left != right) { times++; const std::size_t middle {(right - left + 1) / 2 + left - 1}; if (numbers[middle] > target) right = middle; else if (numbers[middle] < target) left = middle + 1; else { std::cout << middle << ' ' << times << '\n'; return 0; } } std::cout << "not found " << times << '\n'; return 0; } ``` ### a153: 二分法求解 我知道大家都有種寫 `std::log(2)` 的衝動，不過姑且假裝自己不知道函式長怎樣一下。 ```cpp= #include <cmath> #include <iostream> using num_t = double; num_t f (num_t x) { return 2 - std::exp(x); } constexpr num_t bigger {1}; constexpr num_t lower {0}; constexpr num_t TOL {1.0e-8}; int main () { num_t max {bigger}; num_t min {lower}; while (std::abs(f(max) - f(min)) > TOL) { const num_t middle {(min + max) / 2}; if (f(middle) > 0 == f(min) > 0) min = middle; else max = middle; } std::cout << min << '\n'; return 0; } ``` ### a290: 完美購書計畫 很醜。 ```cpp= #include <map> #include <iostream> int main () { int books_num {}; while (std::cin >> books_num) { std::map<int, int> books {}; while (books_num--) { int book {}; std::cin >> book; books[book]++; } int target {}; std::cin >> target; const int halfTarget {target / 2}; int answer {target + 1}; if (target % 2 == 0) { const auto half {books.find(halfTarget)}; if (half != books.end()) { if (half->second >= 2) answer = 0; else books.erase(half); } } for (auto book {books.begin()}; book != books.end(); books.erase(book++)) { if (!answer || book->first > halfTarget) break; const auto need {books.find(target - book->first)}; if (need == books.end()) continue; books.erase(need); answer = std::min(answer, halfTarget - book->first); } std::cout << "Peter should buy books whose prices are " << halfTarget - answer << " and " << halfTarget + answer + target % 2 << ".\n\n"; } return 0; } ``` ### a130: 人員調動 ```cpp= #include <iostream> #include <set> #include <utility> int main () { int tests {}; std::cin >> tests; while (tests--) { int peoples {}; std::cin >> peoples; std::multiset<std::pair<int, int>> pairs {}; int count {}; while (peoples--) { int from {}, to {}; std::cin >> from >> to; const auto reverse {pairs.find({to, from})}; if (reverse == pairs.end()) { pairs.emplace(from, to); } else { count++; pairs.erase(reverse); } } std::cout << count << '\n'; } return 0; } ``` ### a131: 大黑馬 來點比較舒服的寫法。 ```cpp= #include <iostream> #include <vector> constexpr inline std::size_t u (int i) { return static_cast<std::size_t>(i); } struct Team { int seed {}; int length {}; std::vector<int> average {}; std::vector<int> best {}; std::vector<int> worse {}; Team (int length) : length {length}, average(u(length)), best(u(length)), worse(u(length)) {} }; bool canBeat (const Team& team, const Team& opponent, bool chance) { if (team.seed == opponent.seed) return true; const int half {team.length / 2}; const auto& our_players {chance ? team.best : team.average}; const auto& opponent_players {chance ? opponent.worse : opponent.average}; for (int i {0}; i < half + 1; i++) { const int our_bp {our_players[u(i)]}; const int opponent_bp {opponent_players[u(half + i)]}; if (opponent_bp > our_bp || opponent_bp == our_bp && opponent.seed < team.seed) return false; } return true; } bool canWin (const Team& team, const std::vector<Team>& teams, bool chance) { for (const auto& opponent : teams) { if (!canBeat(team, opponent, chance)) return false; } return true; } int getBlackHorse (const std::vector<Team>& teams, bool chance) { int blackHorse {0}; for (const auto& team : teams) { if (team.seed > blackHorse && canWin(team, teams, chance)) blackHorse = team.seed; } return blackHorse; } int main () { int players_half {}, teams_num {}; std::cin >> players_half >> teams_num; std::vector<Team> teams(u(teams_num), Team(players_half * 2 + 1)); for (auto& team : teams) { std::cin >> team.seed; for (auto& bp : team.average) std::cin >> bp; for (auto& bp : team.best) std::cin >> bp; for (auto& bp : team.worse) std::cin >> bp; } std::cout << getBlackHorse(teams, false) << ' ' << getBlackHorse(teams, true) << '\n'; return 0; } ``` ### a132: 主機排程 ```cpp= #include <iostream> #include <map> #include <utility> struct Cost { int core {0}; int ram {0}; int bw {0}; Cost& operator+= (const Cost& b) { core += b.core; ram += b.ram; bw += b.bw; return *this; } Cost& operator-= (const Cost& b) { core -= b.core; ram -= b.ram; bw -= b.bw; return *this; } void max (const Cost& b) { if (core < b.core) core = b.core; if (ram < b.ram) ram = b.ram; if (bw < b.bw) bw = b.bw; } }; int main () { int tests {}, divisor {}; std::cin >> tests >> divisor; divisor *= 24; while (tests--) { int processes_num {}; std::cin >> processes_num; std::map<int, Cost> costs {}; Cost now_cost {0, 0, 0}; while (processes_num--) { int start_d {}, start_h {}, time {}; std::cin >> start_d >> start_h >> time; const int start {(start_d - 1) * 24 + start_h}; const int end {start + time}; Cost cost {}; std::cin >> cost.core >> cost.ram >> cost.bw; costs[start] += cost; costs[end % divisor] -= cost; if (end >= divisor) now_cost += cost; } std::cin >> processes_num; // ignore tail 0 Cost max_cost {now_cost}; for (const auto& cost : costs) { now_cost += cost.second; max_cost.max(now_cost); } std::cout << max_cost.core << ' ' << max_cost.ram << ' ' << max_cost.bw << '\n'; } return 0; } ``` ## 12. [基礎演算法 I ] 窮舉法 ### a088: 最大乘積 切三段分析法，另一種比較漂亮的等價方法之後再補。 ```cpp= #include <algorithm> #include <iostream> int main () { int test {1}; int num {}; while (std::cin >> num) { long long max_product {0}; long long middle {1}, last {1}, first {0}; bool avalible {false}; do { int next {0}; if (num) std::cin >> next; if (next == 0) { if (avalible) max_product = std::max({max_product, first * middle, last * middle, first * last * middle}); first = 0; middle = 1; last = 1; avalible = false; } else if (next > 0) { last *= next; avalible = true; } else if (!first) { if (avalible) max_product = std::max(max_product, last); first = last * next; last = 1; } else { middle *= last; last = next; avalible = true; } } while (num--); std::cout << "Case #" << test++ << ": The maximum product is " << max_product << ".\n\n"; } return 0; } ``` ### a133: 採蘑菇攻略問題 ```cpp= #include <iostream> #include <utility> int main () { int num {}; std::cin >> num; int sum {0}; int max_sum {0}; while (num--) { int number {}; std::cin >> number; sum = std::max(0, sum + number); max_sum = std::max(max_sum, sum); } std::cout << max_sum << '\n'; return 0; } ``` ### a154: 除法 使用乘法直式的概念一位一位算，進行回朔與剪枝。 嗯……`result` 和 `answers` 的用法的確很噁心，有空我再想想怎改。 ```cpp= #include <algorithm> #include <iomanip> #include <iostream> #include <vector> void check (int target, unsigned int used, int length, int carry, std::vector<int>& result, std::vector<int>& answers) { if (length == 5) { if (carry != 0) return; int x {0}; for (auto i {result.rbegin()}; i != result.rend(); i++) x = x * 10 + *i; answers.push_back(x); return; } for (int i {0}; i <= 9; i++) { if (used & (1 << i)) continue; const int product {i * target + carry}; const int j {product % 10}; if (i == j || used & (1 << j)) continue; result.push_back(j); check(target, used | (1 << i) | (1 << j), length + 1, product / 10, result, answers); result.pop_back(); } } int main () { std::cout << std::setfill('0'); while (true) { int target {}; std::cin >> target; if (!target) return 0; std::vector<int> answers {}; std::vector<int> result {}; check(target, 0, 0, 0, result, answers); if (answers.empty()) { std::cout << "There are no solutions for " << target << ".\n"; continue; } std::sort(answers.begin(), answers.end()); for (const auto& answer : answers) { std::cout << std::setw(5) << answer << " / " << std::setw(5) << answer / target << " = " << target << '\n'; } } } ``` ### a134: 回文日期問題 ```cpp= #include <algorithm> #include <ctime> #include <iostream> #include <string> #include <vector> void is_palindrome (const std::string& str, std::vector<int>& output) { for (std::size_t i {0}; i < str.length() / 2 + 1; i++) { if (str[i] != str[str.length() - i - 1]) return; } output.push_back(std::stoi(str)); } int main () { int tests {}; std::cin >> tests; while (tests--) { int year {}; std::cin >> year; const std::string yearstr {std::to_string(year)}; year = (year + 100) % 1000; std::tm date {}; date.tm_year = year; date.tm_mday = 1; std::vector<int> answers {}; while (date.tm_year == year) { const std::string monstr {std::to_string(date.tm_mon + 1)}; const std::string daystr {std::to_string(date.tm_mday)}; is_palindrome(yearstr + monstr + daystr, answers); if (monstr.length() == 1) is_palindrome(yearstr + "0" + monstr + daystr, answers); if (daystr.length() == 1) is_palindrome(yearstr + monstr + "0" + daystr, answers); if (monstr.length() == 1 && daystr.length() == 1) is_palindrome(yearstr + "0" + monstr + "0" + daystr, answers); date.tm_mday++; std::mktime(&date); } std::sort(answers.begin(), answers.end()); std::cout << answers.size(); for (const auto& answer : answers) std::cout << ' ' << answer; std::cout << '\n'; } return 0; } ``` ### a135: 巧克力擺盒 位元運算大法好，效率特高。 ```cpp= #include <algorithm> #include <iostream> #include <numeric> #include <utility> #include <vector> struct Row { std::pair<char, char> a {}; std::pair<char, char> b {}; std::pair<char, char> c {}; unsigned int used {0}; unsigned int conditions {0}; }; int main () { std::vector<std::pair<char, char>> chocolates {}; for (const auto& f : {'B', 'P', 'Y'}) { for (const auto& s : {'C', 'S', 'T'}) chocolates.emplace_back(f, s); } std::vector<Row> rows {}; std::vector<unsigned int> nums(9); std::iota(nums.begin(), nums.end(), 0); do { rows.push_back({ chocolates[nums[0]], chocolates[nums[1]], chocolates[nums[2]], static_cast<unsigned int>(1 << nums[0] | 1 << nums[1] | 1 << nums[2]) }); std::reverse(nums.begin() + 3, nums.end()); } while (std::next_permutation(nums.begin(), nums.end())); int rules_num {}; std::cin >> rules_num; unsigned int pass_all {0}; unsigned int pass {1}; while (rules_num--) { int type {}; std::cin >> type; if (type == 2) { char a_f {}, a_s {}, b_f {}, b_s {}; std::cin >> a_f >> a_s >> b_f >> b_s; for (auto& row : rows) { if ( (a_f == '?' || a_f == row.a.first) && (a_s == '?' || a_s == row.a.second) && (b_f == '?' || b_f == row.b.first) && (b_s == '?' || b_s == row.b.second) || (a_f == '?' || a_f == row.b.first) && (a_s == '?' || a_s == row.b.second) && (b_f == '?' || b_f == row.c.first) && (b_s == '?' || b_s == row.c.second) ) row.conditions |= pass; } } else { char a_f {}, a_s {}, b_f {}, b_s {}, c_f {}, c_s {}; std::cin >> a_f >> a_s >> b_f >> b_s >> c_f >> c_s; for (auto& row : rows) { if ( (a_f == '?' || a_f == row.a.first) && (a_s == '?' || a_s == row.a.second) && (b_f == '?' || b_f == row.b.first) && (b_s == '?' || b_s == row.b.second) && (c_f == '?' || c_f == row.c.first) && (c_s == '?' || c_s == row.c.second) ) row.conditions |= pass; } } pass_all |= pass; pass <<= 1; } int answer {0}; for (auto a {rows.begin()}; a != rows.end(); a++) { for (auto b {a + 1}; b != rows.end(); b++) { if (a->used & b->used) continue; const unsigned int condition_ab {a->conditions | b->conditions}; const unsigned int used_ab {a->used | b->used}; for (auto c {b + 1}; c != rows.end(); c++) { if (!(used_ab & c->used) && (condition_ab | c->conditions) == pass_all) answer += 6; } } } std::cout << answer << '\n'; return 0; } ``` ## 13. [基礎資料結構 II 及基礎演算法 II ] 貪婪法 ### a091: 加總的代價 ```cpp= #include <iostream> #include <queue> #include <vector> int main () { while (true) { int numbers_count {}; std::cin >> numbers_count; if (!numbers_count) return 0; std::priority_queue<int, std::vector<int>, std::greater<int>> numbers {}; while (numbers_count--) { int number {}; std::cin >> number; numbers.push(number); } long long cost {0}; while (numbers.size() > 1) { int sum {numbers.top()}; numbers.pop(); sum += numbers.top(); numbers.pop(); numbers.push(sum); cost += sum; } std::cout << cost << '\n'; } } ``` ### a071: 排隊買飲料 真就照題目說的模擬。 ```cpp= #include <iostream> #include <vector> int main () { int customers_count {}; std::cin >> customers_count; std::size_t staffs_count {}; std::cin >> staffs_count; std::vector<int> staffs(staffs_count, 0); int clock {-1}; bool conti {true}; while (conti) { clock++; conti = false; for (auto& staff : staffs) { if (staff != 0) staff--; if (!staff && customers_count) { std::cin >> staff; customers_count--; conti = true; } else if (staff) conti = true; } } std::cout << clock << '\n'; return 0; } ``` ### a141: 基地台 所以[二分法求解](#a153-二分法求解)為什麼不用這題？ ```cpp= #include <algorithm> #include <cmath> #include <iostream> #include <set> #include <stdexcept> #include <vector> void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); } bool is_distance_possible (const std::vector<int>& points, int max_number, int distance) { int number {1}; int left_point {points[0]}; for (const auto& point : points) { if (point - left_point <= distance) continue; number++; if (number > max_number) return false; left_point = point; } return true; } int main() { fastio(); std::set<int> possible_disances {}; int points_num {}; int max_number {}; std::cin >> points_num >> max_number; std::vector<int> points(points_num); for (auto& point : points) std::cin >> point; std::sort(points.begin(), points.end()); int max {points.back() - points.front()}; int min {0}; while (max - min > 1) { const int middle {(max + min) / 2}; if (is_distance_possible(points, max_number, middle)) max = middle; else min = middle; } std::cout << max; return 0; } ``` ### a139: 背包置物問題 ```cpp= #include <algorithm> #include <iostream> #include <istream> #include <set> #include <vector> int main() { int books_num {}; int max_carry {}; std::cin >> books_num >> max_carry; std::vector<int> needs {}; int input {}; while (std::cin >> input) { needs.push_back(max_carry); max_carry = input; } std::set<int> bag {}; int times {0}; for (auto need {needs.begin()}; need != needs.end(); need++) { if (bag.count(*need)) continue; if (bag.size() < max_carry) { bag.insert(*need); continue; } bag.erase(std::max_element(bag.begin(), bag.end(), [&need, &needs](int a, int b) { const auto a_next_use {std::find(need, needs.end(), a)}; const auto b_next_use {std::find(need, needs.end(), b)}; return a_next_use < b_next_use; })); bag.insert(*need); times++; } std::cout << times << '\n'; return 0; } ``` ### a075: 醜數 比較簡單的貪婪解： ```cpp= #include <iomanip> #include <iostream> #include <set> int main() { static const int factors[] {2, 3, 5}; int n {}; std::cin >> n; std::set<int> ugly {}; ugly.insert(1); while (--n) { const auto first {ugly.begin()}; for (const int x : {2, 3, 5}) ugly.insert(*first * x); ugly.erase(first); } std::cout << *ugly.begin(); return 0; } ``` 較為複雜但有極小的一咪咪提升的動態規劃解： ```cpp= #include <algorithm> #include <iostream> #include <vector> int main() { int n {}; std::cin >> n; std::vector<int> ugly {1}; ugly.reserve(n); auto i2 {ugly.begin()}, i3 {i2}, i5 {i2}; while (--n) { const int x2 {*i2 * 2}, x3 {*i3 * 3}, x5 {*i5 * 5}; int next = std::min({x2, x3, x5}); ugly.push_back(next); if (x2 == next) i2++; if (x3 == next) i3++; if (x5 == next) i5++; } std::cout << ugly.back() << '\n'; return 0; } ``` ## 14. [基礎資料結構 II 及基礎演算法 II ] 分而治之與回溯法 ### a165: 最近點對問題 就照課本說的寫。 ```cpp= #include <algorithm> #include <cmath> #include <iomanip> #include <iostream> #include <utility> #include <vector> void fastio () { std::cin.tie(nullptr)->sync_with_stdio(false); } constexpr long long max_distance {10000 * 10000 + 1}; using Point = std::pair<long long, long long>; long long distance (Point a, Point b) { const long long dx {a.first - b.first}; const long long dy {a.second - b.second}; return std::min(dx * dx + dy * dy, max_distance); } long long get_min_distance (const std::vector<Point>& points, std::size_t from, std::size_t to) { if (to == from) return max_distance; const std::size_t middle {(from + to) / 2}; long long min_distance {std::min(get_min_distance(points, from, middle), get_min_distance(points, middle + 1, to))}; for (std::size_t i {middle}; i >= from && i != -1; i--) { if (points[middle].first - points[i].first > min_distance) break; for (std::size_t j {middle + 1}; j <= to; j++) { if (points[j].first - points[middle].first > min_distance) break; min_distance = std::min(min_distance, distance(points[i], points[j])); } } return min_distance; } int main() { fastio(); std::cout << std::fixed << std::setprecision(4); while (true) { std::size_t points_num {}; std::cin >> points_num; if (!points_num) return 0; std::vector<Point> points(points_num); for (auto& point : points) std::cin >> point.second >> point.first; std::sort(points.begin(), points.end()); const long long min_distance {get_min_distance(points, 0, points.size() - 1)}; if (min_distance == max_distance) std::cout << "INFINITY\n"; else std::cout << std::sqrt(min_distance) << '\n'; } } ``` ### a089: 蘇丹王位繼承者 先解完八皇后再解題目。 ```cpp= #include <iomanip> #include <iostream> #include <vector> constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); } bool check (const std::vector<int>& choose) { int y {static_cast<int>(choose.size() - 1)}; if (y == 0) return true; for (int i {0}; i < y; i++) { if ( choose.back() == choose[u(i)] || choose.back() + y == choose[u(i)] + i || choose.back() - y == choose[u(i)] - i ) return false; } return true; } auto solve8qreen () { std::vector<std::vector<int>> results {}; std::vector<int> choose {-1}; while (!choose.empty()) { choose.back()++; if (choose.back() == 8) { choose.pop_back(); continue; } if (!check(choose)) continue; if (choose.size() == 8) results.push_back(choose); else choose.push_back(-1); } return results; } int main () { auto soluctions {solve8qreen()}; int tests {}; std::cin >> tests; while (tests--) { std::vector<std::vector<int>> board (8, std::vector<int>(8)); for (auto& row : board) for (auto& grid : row) std::cin >> grid; int max_sum {-1}; for (const auto& soluction : soluctions) { int sum {0}; for (int i {0}; i < 8; i++) sum += board[u(i)][u(soluction[u(i)])]; if (sum > max_sum) max_sum = sum; } std::cout << std::setw(5) << max_sum << '\n'; } return 0; } ``` ### a090: 質數環 好看什麼的之後再說。 ```cpp= #include <algorithm> #include <iostream> #include <vector> constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); } bool has (const std::vector<int>& array, int element) { return std::find(array.begin(), array.end(), element) != array.end(); } auto generatePrimes (int max) { std::vector<int> primes {2}; const auto isPrime {[&primes](int x) { for (const auto& prime : primes) { if (x % prime == 0) return false; } return true; }}; while (primes.back() < max) { int x {primes.back() + 1}; while (!isPrime(x)) x++; primes.push_back(x); } return primes; } auto generatePairs (int max) { std::vector<int> primes {generatePrimes(max * 2 - 1)}; std::vector<std::vector<int>> pairs(u(max)); for (int i {1}; i <= max; i += 2) { for (int j {2}; j <= max; j += 2) { if (!has(primes, i + j)) continue; pairs[u(i - 1)].push_back(j); pairs[u(j - 1)].push_back(i); } } return pairs; } int main () { const auto pairs {generatePairs(16)}; int cases {1}; int length {}; while (std::cin >> length) { std::vector<std::vector<int>> answers {}; std::vector<int> choose {-1}; std::vector<int> numbers {1}; while (!choose.empty()) { int next {++choose.back()}; auto& list {pairs[u(numbers.back() - 1)]}; if (numbers.size() == length) { if (has(pairs[0], numbers.back())) answers.push_back(numbers); } if (numbers.size() == length || next >= list.size() || list[u(next)] > length) { choose.pop_back(); numbers.pop_back(); continue; }; if (has(numbers, list[u(next)])) continue; numbers.push_back(list[u(next)]); choose.push_back(-1); } std::cout << "Case " << cases << ":\n"; for (const auto& answer : answers) { for (const auto& number : answer) std::cout << number << ' '; std::cout << '\n'; } std::cout << '\n'; cases++; } return 0; } ``` ### a286: 23 乘法的部分還是剪的，只是要倒過來算。 ```cpp= #include <bitset> #include <iostream> #include <vector> bool test (int level, int x, const std::bitset<5>& used, const std::vector<int>& numbers) { if (level == 5) return x == 0; for (std::size_t i {0}; i < 5; i++) { if (used[i]) continue; const std::bitset<5> new_used {used | std::bitset<5>(1 << i)}; if (level < 4 && x % numbers[i] == 0 && test(level + 1, x / numbers[i], new_used, numbers)) return true; if (level < 4 && test(level + 1, x + numbers[i], new_used, numbers)) return true; if (test(level + 1, x - numbers[i], new_used, numbers)) return true; } return false; } int main() { while (true) { std::vector<int> numbers(5); for (auto& n : numbers) std::cin >> n; if (numbers[0] == 0) return 0; if (test(0, 23, std::bitset<5>{}, numbers)) std::cout << "Possible\n"; else std::cout << "Impossible\n"; } } ``` ### a142: 無刻度容器倒水問題 這題是圖論之廣度優先搜尋。 只有兩杯那倒法就不用迴圈寫法了。 ```cpp= #include <algorithm> #include <iostream> #include <queue> #include <set> #include <utility> int soluction () { using pii = std::pair<int, int>; int a_limit {}, b_limit {}, target {}; std::cin >> a_limit >> b_limit >> target; std::queue<pii> visiting {}, to_visit {}; visiting.emplace(0, 0); std::set<pii> visited {{0, 0}}; const auto visit {[&visited, &to_visit, target] (pii state) { if (state.first == target || state.second == target) return true; if (visited.count(state)) return false; to_visit.push(state); visited.insert(state); return false; }}; int depth {1}; while (!visiting.empty()) { pii now {visiting.front()}; visiting.pop(); const int sum {now.first + now.second}; if ( visit({now.first, 0}) || visit({0, now.second}) || visit({now.first, b_limit}) || visit({a_limit, now.second}) || visit({std::max(sum - b_limit, 0), std::min(sum, b_limit)}) || visit({std::min(sum, a_limit), std::max(sum - a_limit, 0)}) ) return depth; if (!visiting.empty()) continue; std::swap(visiting, to_visit); depth++; } return -1; } int main () { int tests {}; std::cin >> tests; while (tests--) std::cout << soluction() << '\n'; return 0; } ``` ## 15. [基礎資料結構 II 及基礎演算法 II ] 動態規劃 ### a098: 計算方法數 法一： ```cpp= #include <iostream> #include <numeric> #include <vector> constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); } int main () { const std::vector<int> coins {1, 5, 10, 25, 50}; // dp[sum][last use] = method types std::vector<std::vector<long long>> dp {{1}}; int target {}; while (std::cin >> target) { for (int i {static_cast<int>(dp.size())}; i <= target; i++) { dp.emplace_back(coins.size(), 0); for (int j {0}; j < coins.size(); j++) { if (coins[u(j)] == i) dp[i][j] = 1; if (coins[u(j)] >= i) break; for (int k {0}; k <= j; k++) dp[u(i)][u(j)] += dp[u(i - coins[u(j)])][u(k)]; } } const long long answer {std::accumulate(dp[u(target)].begin(), dp[u(target)].end(), 0LL)}; if (answer == 1) { std::cout << "There is only 1 way to produce "; } else { std::cout << "There are " << answer << " ways to produce "; } std::cout << target << " cents change.\n"; } return 0; } ``` 法二： ```cpp= #include <iostream> #include <vector> constexpr std::size_t u (int i) { return static_cast<std::size_t>(i); } int main () { std::vector<long long> methods(30000 + 1, 0); methods[0] = 1; for (const int coin : {1, 5, 10, 25, 50}) { for (int i {coin}; i <= 30000; i++) { methods[u(i)] += methods[u(i - coin)]; } } int target {}; while (std::cin >> target) { if (methods[u(target)] == 1) { std::cout << "There is only 1 way to produce "; } else { std::cout << "There are " << methods[u(target)] << " ways to produce "; } std::cout << target << " cents change.\n"; } return 0; } ``` ### a155: 雙子星塔 ```cpp= #include <algorithm> #include <iostream> #include <vector> int main () { for (int test {1}; ; test++) { std::size_t a_hight {}, b_hight {}; std::cin >> a_hight >> b_hight; if (!a_hight) return 0; std::vector<int> a_tower(a_hight); for (auto& brick : a_tower) std::cin >> brick; std::vector<int> b_tower(b_hight); for (auto& brick : b_tower) std::cin >> brick; std::vector<int> dp1(b_hight, 0), dp2(b_hight, 0); for (std::size_t i {0}; i < a_hight; i++) { for (std::size_t j {0}; j < b_hight; j++) { dp2[j] = std::max({ dp1[j], j == 0 ? 0 : dp2[j - 1], (j == 0 ? 0 :dp1[j - 1]) + (a_tower[i] == b_tower[j]) }); } std::swap(dp1, dp2); } std::cout << "Twin Towers #" << test << "\nNumber of Tiles : " << dp1.back() << "\n\n"; } } ``` ### a144: 農作物採收問題 ```cpp= #include <algorithm> #include <iostream> #include <vector> int main () { int width {}; std::cin >> width; std::vector<std::vector<int>> field(width, {0}); for (auto& row : field) { for (int i {0}; i < width; i++) { int block {}; std::cin >> block; row.push_back(row.back() + block); } } int max {0}; for (std::size_t from {0}; from < width; from++) { for (std::size_t to {from}; to < width; to++) { int sum {0}; for (const auto& row : field) { sum = std::max(sum + row[to + 1] - row[from], 0); max = std::max(max, sum); } } } std::cout << max << '\n'; } ``` ### a101: 分銅幣 實在想不到，只好作弊用位元運算了。 ```cpp= #include <bitset> #include <cmath> #include <iostream> #include <set> int main () { constexpr std::size_t maxdiff {500 * 100}; int tests {}; std::cin >> tests; while (tests--) { std::bitset<maxdiff> diffs {0b1}; int coins {}; std::cin >> coins; while (coins--) { unsigned int coin {}; std::cin >> coin; std::bitset<maxdiff> diffs_new {(diffs << coin) | (diffs >> coin)}; for (std::size_t i {0}; i < coin; i++) { if (!diffs[i]) continue; diffs_new[coin - i] = true; } diffs = std::move(diffs_new); } for (std::size_t i {0}; i < maxdiff; i++) { if (!diffs[i]) continue; std::cout << i << '\n'; break; } } return 0; } ``` ### a143: 關鍵字搜尋模擬 ```cpp= #include <algorithm> #include <cmath> #include <iostream> #include <sstream> #include <stdexcept> #include <string> #include <utility> #include <vector> float getScore (const std::string& a, const std::string& b) { int max {0}; std::vector<int> dp(b.size(), 0); for (std::size_t i {0}; i < a.size(); i++) { for (std::size_t j {b.size() - 1}; j != -1; j--) { if (a[i] == b[j]) dp[j] = (j == 0 ? 0 : dp[j - 1]) + 1; else dp[j] = 0; if (dp[j] > max) max = dp[j]; } } return static_cast<float>(max) / a.size(); } int main() { std::vector<std::string> searchs {}; std::string input {}; std::getline(std::cin, input); { std::stringstream sstream {input}; while (sstream >> input) searchs.push_back(input); } int files_num {}; std::cin >> files_num; std::vector<std::pair<int, int>> files {}; bool flag {false}; while (files_num--) { int id {}; std::cin >> id; std::getline(std::cin, input); std::stringstream sstream {input}; float scoreSum {}; while (sstream >> input) { float score {}; for (const auto& searchkeyword : searchs) score = std::max(score, getScore(searchkeyword, input)); scoreSum += score; } if (scoreSum > 0) flag = true; files.emplace_back(id, std::round(scoreSum * 100)); } std::sort(files.begin(), files.end(), [](const auto& a, const auto& b) { return a.second == b.second ? a.first < b.first : a.second > b.second; }); if (!flag) { std::cout << "FALSE\n"; return 0; } for (const auto& file : files) std::cout << file.first << ' '; std::cout << '\n'; return 0; } ``` ### a145: 搬家規畫問題 ```cpp= #include <algorithm> #include <iostream> #include <sstream> #include <string> #include <vector> int main () { std::vector<std::pair<int, int>> items {}; { std::string input {}; std::getline(std::cin, input); std::stringstream sstream {input}; int weight {}; while (sstream >> weight) items.emplace_back(weight, 0); } for (auto& item : items) std::cin >> item.second; int max_weight {}; std::cin >> max_weight; std::vector<int> max_values(max_weight + 1, 0); for (const auto& item : items) { for (std::size_t i {max_weight}; i >= item.first && i != -1; i--) { max_values[i] = std::max(max_values[i], max_values[i - item.first] + item.second); } } std::cout << max_values.back() << '\n'; } ``` ## 16. [基礎資料結構 II 及基礎演算法 II ] 樹狀/圖形結構演算法 ### a136: 元件測試排程問題 ```cpp= #include <algorithm> #include <iostream> #include <queue> #include <utility> #include <vector> int main() { int items_num{}, needs_num{}; std::cin >> items_num >> needs_num; std::vector<int> items(items_num); std::vector<std::pair<int, int>> edges(needs_num); for (auto& edge : edges) { char first{}, second{}; std::cin >> first >> second; edge = { first - 'A', second - 'A' }; items[edge.second]++; } std::queue<int> to_visit{}; std::vector<int> sorted{}; bool noanswer{ false }; int lastuse{ -1 }; for (int i{ 0 }; i < items_num; i++) { if (items[i] == 0) to_visit.push(i); } while (sorted.size() < items_num) { if (to_visit.empty()) { const auto& edge = edges.back(); edges.pop_back(); if (items[edge.first] == 0) continue; if (--items[edge.second] > 0) continue; to_visit.push(edge.second); } while (!to_visit.empty()) { const int now{ to_visit.front() }; to_visit.pop(); if (!noanswer && !to_visit.empty()) noanswer = true; sorted.push_back(now); for (const auto& edge : edges) { if (edge.first != now) continue; if (--items[edge.second] != 0) continue; to_visit.push(edge.second); if (edges.size() != needs_num) continue; lastuse = std::max(lastuse, static_cast<int>(std::find(edges.begin(), edges.end(), edge) - edges.begin())); } } } if (edges.size() != needs_num) std::cout << "Order conflict after getting pair " << edges.size() + 1 << '\n'; else if (noanswer) std::cout << "No answer\n"; else { std::cout << "Determine the testing sequence after getting pair " << lastuse + 1 << " : "; for (const auto& item : sorted) std::cout << static_cast<char>('A' + item); std::cout << '\n'; } return 0; } ``` ### a137: 勇者冒險 ```cpp= #include <algorithm> #include <iostream> #include <queue> #include <utility> #include <vector> int main() { using pos_t = std::pair<int, int>; int rows {}, columns {}; std::cin >> rows >> columns; pos_t start {}, end {}; std::cin >> start.first >> start.second >> end.first >> end.second; std::vector<std::vector<int>> map (rows, std::vector<int>(columns, -1)); map[end.first][end.second] = 0; int blocks_num {}; std::cin >> blocks_num; while (blocks_num--) { pos_t pos {}; std::cin >> pos.first >> pos.second; std::cin >> map[pos.first][pos.second]; } std::vector<std::vector<int>> min_levels (rows + 1, std::vector<int>(columns + 1, -1)); min_levels[start.first][start.second] = 0; const auto comp = [&min_levels](pos_t a, pos_t b) { const int a_distance {min_levels[a.first][a.second]}; const int b_distance {min_levels[b.first][b.second]}; return a_distance > b_distance; }; std::priority_queue<pos_t, std::vector<pos_t>, decltype(comp)> to_visit {comp}; to_visit.push(start); while (!to_visit.empty()) { const pos_t pos {to_visit.top()}; to_visit.pop(); const int base_level {min_levels[pos.first][pos.second]}; pos_t dpos {0, 1}; for (int i {0}; i < 4; i++) { dpos = {dpos.second, -dpos.first}; const pos_t new_pos {pos.first + dpos.first, pos.second + dpos.second}; if (new_pos.first < 0 || new_pos.first >= rows || new_pos.second < 0 || new_pos.second >= columns) continue; const auto level {map[new_pos.first][new_pos.second]}; if (level == -1) continue; const int come_level {std::max(level, base_level)}; auto& min_level {min_levels[new_pos.first][new_pos.second]}; if (min_level != -1 && come_level >= min_level) continue; min_level = come_level; to_visit.push(new_pos); } } std::cout << min_levels[end.first][end.second] << '\n'; return 0; } ``` ### a138: 最小花費的航空之旅 ```cpp= #include <algorithm> #include <iostream> #include <queue> #include <utility> #include <vector> #include <map> struct State { int cost {}; int city {}; std::vector<int>::iterator complete {}; std::vector<int> used {}; bool is_used (int ticket_id) const { return std::find(used.begin(), used.end(), ticket_id) != used.end(); } bool operator< (const State& other) const { return cost > other.cost; } }; struct Ticket { int id {}; int cost {}; std::vector<int> path {}; }; int main() { int tickets_num {}; std::cin >> tickets_num; std::map<int, std::vector<Ticket>> tickets {}; for (int i {1}; i <= tickets_num; i++) { Ticket ticket {i}; std::cin >> ticket.cost; int length {}, start {}; std::cin >> length >> start; ticket.path.resize(length - 1); for (auto& city : ticket.path) std::cin >> city; tickets[start].push_back(ticket); } int route_length {}; std::cin >> route_length; std::vector<int> route(route_length); for (auto& city : route) std::cin >> city; std::priority_queue<State> states {}; states.push({0, route.front(), ++route.begin()}); while (states.top().complete != route.end()) { const State state {states.top()}; states.pop(); for (const auto& ticket : tickets[state.city]) { if (state.is_used(ticket.id)) continue; State new_state {state}; new_state.used.push_back(ticket.id); new_state.cost += ticket.cost; for (const auto& city : ticket.path) { if (new_state.complete == route.end()) break; if (city == *new_state.complete) new_state.complete++; new_state.city = city; states.push(new_state); } } } std::cout << "Cost = " << states.top().cost << ", Tickets used: "; bool first {true}; for (const auto& ticket_id : states.top().used) { if (!first) std::cout << ", "; std::cout << ticket_id; if (first) first = false; } std::cout << "\n"; return 0; } ``` ## 17. [題目解析] APCS 程式開發環境、題目解析 ### a160: 線段覆蓋長度 ```cpp= #include <algorithm> #include <iostream> #include <utility> #include <vector> int main () { int lines {}; std::cin >> lines; std::vector<std::pair<int, int>> points {}; while (lines--) { int start {}, end {}; std::cin >> start >> end; points.emplace_back(start, 1); points.emplace_back(end, -1); } std::sort(points.begin(), points.end()); int lastpos {}; int length {0}; int lines_num {0}; for (const auto& point : points) { if (lines_num > 0) length += point.first - lastpos; lines_num += point.second; lastpos = point.first; } std::cout << length << '\n'; return 0; } ``` ### a140: 物品堆疊 ```cpp= #include <algorithm> #include <iostream> #include <vector> #include <utility> int main () { int items_num {}; std::cin >> items_num; std::vector<std::pair<int, int>> items(items_num); for (auto& item : items) std::cin >> item.first; for (auto& item : items) std::cin >> item.second; std::sort(items.begin(), items.end(), [](const auto& a, const auto& b) { return a.first * b.second < b.first * a.second; }); long long sumw {0}; long long sumcost {0}; for (const auto& item : items) { sumcost += sumw * item.second; sumw += item.first; } std::cout << sumcost << '\n'; return 0; } ```