:+1: 2020 競技程設教材 HackMD Book :+1: 第三週教材中分治法，提到了每個子問題都需互相獨立，就是每分割都將產生全新的問題 而本次介紹的動態規劃則適合大部分的子問題互相重疊 回憶教材中的那段話： "從邊界遞推地紀錄所有問題的解，且一個項用到前一項的最佳結果，就是動態規劃的精神。" 這裡給出正式的定義： 問題若能用 Dynamic Programming (以下簡稱 DP) 求解，其該問題含有以下三個性質：

:+1: 2020 競技程設教材 HackMD Book :+1: Computer programming is an art, because it applies accumulated knowledge to the world, because it requires skill and ingenuity, and especially because it produces objects of beauty. A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better. --- Donald Knuth 教材簡介 本教材由成大電腦網路愛好社社員以及成大競技程式設計課程助教共同編輯，雖然市面上已經有很多很棒的演算法的教材及參考書，但我們的目標在於寫出平易近人的競賽程式設計入門書及參考資料，同時加深我們自己對各種演算法的理解。 本著作採用創用 CC 姓名標示-相同方式分享 3.0 台灣 授權條款授權， 任何人都可以自由使用及分享我們的文字[^editor]

:+1: 2020 競技程設教材 HackMD Book :+1: 這週要介紹的搜尋方法是以數列呈現 子集生成 顧名思義，是將集合的所有子集挑出來，所有可能子集的集合又稱冪集合[^ps-1] 例如 ${A, B}$ 的所有子集為 ${ \emptyset, {A}, {B}, {A, B} }$ 遞迴法 void powerset(int dep) {

:+1: 2020 競技程設教材 HackMD Book :+1: 在演算法競賽中，通常涉及的數論大部份是整數的代數性質 Greatest Common Divisor 中譯 最大公因數，以下簡稱 GCD 給定整數 $a, b$，它倆各自有自己的因數[^factor]，取相同的因數中最大的數，即最大公因數 $\gcd(a, b)$ #include<algorithm> 有內建的 __gcd 函數

:+1: 2020 競技程設教材 HackMD Book :+1: 數大便是美 本週繼續由第十四週主題延伸， 也就是說以下內容或多或少需要最大公因數以及模運算的相關定理。 大數乘法 大數字的乘法，普通的直式乘法 $O(N^2)$ 不夠快，因此將介紹快速的乘法運算

:+1: 2020 競技程設教材 HackMD Book :+1: 本主題會用到第五週教材的內容 Articulation point (AP) Articulation point 中譯 關節點 當連通圖上此關節點被拔除，圖會分為多塊連通圖 通常只要求此連通圖為弱連通的

:+1: 2020 競技程設教材 HackMD Book :+1: 本週要繼續介紹些基本的資料結構 並且接下來將使用這些資料結構構造(解釋)一些演算法 底下的術語挺多的，各位不需馬上就得記起來，等到未來碰到再回來多複習幾遍 Graph 圖 (Graph)，是一個由邊 (Edge) 集合與點 (Vertex) 集合所組成的資料結構

:+1: 2020 競技程設教材 HackMD Book :+1: 這週介紹一些基本的排序演算法 學習這些排序演算法，並不一定只為了解決排序問題 例如 merge sort 能應用在逆序數對問題，quick sort 的 partition 能快速找出數列中第 $k$ 大的數字，counting sort 或 radix sort 能解決更複雜的排序問題 而且這些演算法的實現想法，非常值得模仿與吸收 排序

:+1: 2020 競技程設教材 HackMD Book :+1: 本主題會用到第五週及第七週教材的內容 不熟的話，底下介紹的都看不懂了 圖論最為重要觀念就是 "連通"， 若說此圖為連通圖，則所有點能透過邊接到任一點 (弱連通)^1。 而不只接上還能走過去(有向邊)[^directed_edge]，則為強連通。

:+1: 2020 競技程設教材 HackMD Book :+1: 接下來的章節，採用 C++ 作為主要的程式語言，原因是相對於其他主流的高階語言(e.g. Python, JavaScript...)，C++ 作為編譯語言有相對快的執行速度，且在某些細節操作上更加自由。不過在部分時間或空間限制較寬鬆的題目中採用 Python 解題可以提升解題速度，這部分就交給讀者自行探索。 Input/Output 在 C++ 中，主要有兩種教派(?)，std::cin, std::cout 派與 scanf, printf 派 在一般情況，兩種輸出入函式可以混用，他們會同步使用同一塊緩衝區。 但這樣對於 cin/cout 的負擔很大[^sync]，所以<B>==純用==</B> cin/cout 的話建議在使用前加入這行： std::ios_base::sync_with_stdio(false);

:+1: 2020 競技程設教材 HackMD Book :+1: 設計演算法的思維 本章先以最大連續和問題探討常見的設計演算法切入點： 枚舉 分治 動態規劃 貪心

意義不明的糖果 Task Provider: ys Task Setter: ys 首殺 team21_24 (00:04) 解法說明 根據題意： 番茄糖可以給真姬、千歌、璃奈

:+1: 2020 競技程設教材 HackMD Book :+1: 本篇將介紹些 CP 值較高的資料結構 其中 C 代表的是 coding 複雜度，或把 CP 譯作競程 Sparse Table: RMQ RMQ 全名 Range Maximum/Minimum Query :::info 給定長度 $n$ 的數列 $a$，查詢任意區間極(最大/最小)值

Materials Week1: Introduction Week2: C++ Week3: Way of Thinking Week4: Search

TIOJ 2134 魔法藥水 TIOJ 2128 殿壬發大財 UVa OJ 820 Internet Bandwidth UVa OJ 10330 Power Transmission Uva OJ 10779 Collector’s Problem UVa OJ 11418 Clever Naming Patterns Uva OJ 11987 Almost Union-Find

倍倍儲蓄法 Task Provider: D4nnyLee Task Setter: D4nnyLee 首殺 team21_11 (00:02) 解法說明 這題用暴力破解就可以 AC。 標準程式

懶惰的旅人 Task Provider: D4nnyLee Task Setter: D4nnyLee 首殺 team21_24 (00:04) 解法說明 這題因為道路的長度都是大於 $0$，所以其實 $x_i$ 就只是與 $i$ 之間有直達道路的所有城市中最近的那個城市。 標準程式

forbid patrn Task Provider: GY Task Setter: ys 首殺 team21_32 (00:06) 解法說明 觀察到 $n = 3$ 的情況 100

區間 xor Task Provider: leo Task Setter: leo 首殺 team21_25 (00:02) 解法說明 整數的 xor 運算符合以下條件，下方以「$\oplus$」當作 xor 運算符： 交換律：$a\oplus b=b\oplus a$

無線通訊網路 Task Provider: leo Task Setter: leo 首殺 team21_28 (00:28) 解法說明 「保證任兩個不同的基地台都有辦法互相傳輸資料， 且兩基地台之間傳輸資料的路徑唯一。」 題目敘述最後的這句話是關鍵，