# ShanC 程式競賽筆記

這份筆記是寫給初學者，原本目的是為了供內湖高中 AI 專班(資訊班)的學生認識競賽型程式，但是好像沒啥人要看，又因為 ShanC 現在學太多這些有的沒的東西，所以就寫起來做個紀錄，內容有很多來自筆者的自言自語，供網上的各位參考

筆記搭配 [CSES](https://cses.fi/problemset/) 、[高中生程式解題系統 Zerojudge](https://zerojudge.tw/)、[AtCoder](https://atcoder.jp/)、[Codeforces](https://codeforces.com/) 等網站上的題目
為了配合競賽需求，因此可能會挑難一點的題目，請斟酌使用

> 作者：ShanC

----

## 銜接章節
這些東西是 for 認識競程 && C 到 C++ 銜接的

| 章節 | 連結 |
| -------- | -------- |
|認識競技程式|[link](https://hackmd.io/@ShanC/introduction_to_cp)|
|進階輸入輸出與資料型態|[link](https://hackmd.io/@ShanC/advanced-io-method)|
|C++ 內建函式與資料結構|link|
|位元運算|[link](https://hackmd.io/@ShanC/bitwise-operation)|
|時間複雜度分析|[link](https://hackmd.io/@ShanC/complexity-analysis)|

## 基礎章節
有這些概念就可以搞懂 APCS 實作題，但是熟練這些內容只是剛離開新手村而已

| 章節 | 連結 |
| -------- | -------- |
|Stack 與 Queue|link|
|排序 Sorting|link|
|前綴和 Prefix Sum|link|
|遞迴與分治法 Recursion / Divide and Conquer|link|
|二分搜尋法 Binary Search|[link](https://hackmd.io/@ShanC/binary-search)|
|貪心法 Greedy Method|link|
|BFS 與 DFS|[link](https://hackmd.io/@ShanC/bfs_dfs)|
|質數篩選|link|
|快速冪與倍增法 Binary Exponentiation and Lifting|[link](https://hackmd.io/@ShanC/Binary-Exponentiation-and-Lifting)|

## 競程章節
到這裡才是競程要搞的東西
~~由於筆者讀了很多圖論相關的數學書所以會寫比較多~~
原則上基礎圖論系列要一起讀

---

### 常見資料結構 Common Data Structures
| 章節 | 連結 |
| -------- | -------- |
|線段樹 Segment Tree|link|
|併查集 Disjoint Set (Union-find)|[link](https://hackmd.io/@ShanC/dsu)|
|Fenwick Tree (BIT)|[link](https://hackmd.io/@ShanC/Fenwick-Tree)|

---

### 圖論 Graph Theory
#### 基礎圖論 Introduce to Graph Theory
| 章節 | 連結 |
| -------- | -------- |
|基礎圖論 (一) : 圖的簡介與種類 |[link](https://hackmd.io/@ShanC/basic-graph-theory-1)|
|基礎圖論 (二) : 連通結構、路徑與環|[link](https://hackmd.io/@ShanC/basic-graph-theory-2)|
|基礎圖論 (三) : 有趣的圖論 Topics |[link](https://hackmd.io/@ShanC/basic-graph-theory-3)|
|基礎圖論 (四) : 圖的表示與儲存|[link](https://hackmd.io/@ShanC/basic-graph-theory-4)|

#### 圖論結構問題 Structural Problems
| 章節 | 連結 |
| -------- | -------- |
|拓樸排序 Topological Sort|[link](https://hackmd.io/@ShanC/topological_sort)|
|Kosaraju 演算法找強連通塊 Kosaraju's Algorithm for SCC|[link](https://hackmd.io/@ShanC/Kosaraju)|
|連通塊 Connected Component|[link](https://hackmd.io/@ShanC/connected_component)|
|尋找雙連通塊 Finding Biconnected Component|link|
|二分圖判斷 Bipartite Graph Recognition|[link](https://hackmd.io/@ShanC/Bipartite-Graph-Recog)|

#### 樹 Tree
| 章節 | 連結 |
| -------- | -------- |
|樹的基本性質 Basic Properties of Trees|[link](https://hackmd.io/@ShanC/Trees-Basic-Properties)|
|列舉生成樹 : Cayley's Formula 與 Prüfer Code|[link](https://hackmd.io/@ShanC/Cayleys-Formula-Prufer-Code)|
|最小生成樹 Minimum Spanning Tree|[link](https://hackmd.io/@ShanC/minimum-spanning-tree)|
|樹的路徑與特別的點 Path, Diameter and Centroid|[link](https://hackmd.io/@ShanC/special-vertices-on-tree)|
|最低共同祖先 Lowest Common Ancestor|[link](https://hackmd.io/@ShanC/Lowest-Common-Ancestor)|
|樹壓平 Euler Tour Technique|[link](https://hackmd.io/@ShanC/Euler-Tour-Technique)|
|輕重樹鏈剖分 Heavy-light decomposition|link|

#### 路徑、迴路與環 Paths、Circuits and Cycles
| 章節 | 連結 |
| -------- | -------- |
|最短路徑問題 Shortest Path Problem|link|
|Dijkstra's Algorithm|[link](https://hackmd.io/@ShanC/Dijkstra)|
|Bellman-Ford Algorithm|link|
|Floyd-Warshall Algorithm|link|
|歐拉路徑 Euler Path|link|
|漢米爾頓路徑 Hamiltonian Cycle|link|

#### 匹配問題 Matching Problems
| 章節 | 連結 |
| -------- | -------- |
|匹配與霍爾定理 Matching and Hall's Theorem |[link](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem)|
|Kőnig 定理|[link](https://hackmd.io/@ShanC/konig-theorem)|
|擴充路徑演算法 Augmenting Path Algorithm|[link](https://hackmd.io/@ShanC/Augmenting-Path-Algorithm)|
|匈牙利演算法 Hungarian Algorithm|[link](https://hackmd.io/@ShanC/Hungarian-Algorithm)|

#### 流量網路 Network Flow
| 章節 | 連結 |
| -------- | -------- |
|連通性與 Menger 定理|[link](https://hackmd.io/@ShanC/Menger-Theorem)|
|最大流量-最小割定理 Max-flow Min-cut Theorem|[link](https://hackmd.io/@ShanC/maxflow-mincut-theorem)|
|二分圖匹配與網路流 Bipartite Matching and Flow|[link](https://hackmd.io/@ShanC/bipartite-and-flow)|
|Edmonds-Karp 演算法與 Dinic 演算法|[link](https://hackmd.io/@ShanC/Edmonds-Karp-and-Dinic)|
|最小費用-最大流量問題 Min-cost Max-flow Problem|link|
|經典網路流問題 Classic Flow Problems|[link](https://hackmd.io/@ShanC/Classic-Flow-Problems)|

---

### 數學問題 Math Problems
#### 數論 Number Theory
| 章節 | 連結 |
| -------- | -------- |
|貝祖定理 Bézout's Lemma|link|
|LCM 與 GCD|link|
|取逆元 Inverse Element|link|

#### 記數問題 Counting
| 章節 | 連結 |
| -------- | -------- |
|排列組合 Permutation and Combination|link|
|鴿籠原理 Pigeonhole Principle|link|

#### 多項式 Polynomial
| 章節 | 連結 |
| -------- | -------- |
|多項式計數 Polynomial Counting|link|
|生成函數 Generating Functions|link|
|快速傅立葉轉換 Fast Fourier Transform|link|

#### 矩陣 Matrices
| 章節 | 連結 |
| -------- | -------- |
|矩陣基本操作 Basic Matrix Operations|link|
|矩陣快速冪 Matrix Binary Exponentiation|link|

---

### 計算幾何 Computational Geometry
| 章節 | 連結 |
| -------- | -------- |
|點與線段 Points and Line Segments|link|
|凸包 Convex Hull|link|

---

### 動態規劃 Dynamic Programming
#### 動態規劃入門 Basic DP

| 章節 | 連結 |
| -------- | -------- |
|動態規劃導論 Introduce to Dynamic Programming|[link](https://hackmd.io/@ShanC/Intro-to-DP)|
|經典動態規劃問題 Classic DP Problems|link|
|背包問題 Knapsack Problems|link|
|複雜度分類 Complexity Classes|link|

#### 各種動態規劃 Various DP

| 章節 | 連結 |
| -------- | -------- |
|有向無環圖動態規劃 DP on Directed Acyclic Graph|link|
|樹上動態規劃 DP on Tree|link|
|區間動態規劃 Interval DP|[link](https://hackmd.io/@ShanC/interval-dp)|
|位元壓縮與子集和動態規劃 Bitmask and SOS DP|link|
|數位動態規劃 Digit DP|link|
|記數 & 機率動態規劃 Counting and Probability DP|link|

#### 優化 Optimizations

| 章節 | 連結 |
| -------- | -------- |
|滾動優化 Rolling Method|link|
|單調對列優化 Monotonic Queue Optimization|link|
|凸包 (斜率) 優化 Convex Hull Optimization|link|
|分治優化 Divide and Conquer Optimization|link|

---

### 字串演算法 String Algorithm
#### 字串資料結構 String Data Structures
| 章節 | 連結 |
| -------- | -------- |
|Hash Table|link|
|AC 自動機 Aho–Corasick Algorithm|link|
|後綴陣列 Suffix Array|link|
|Trie|link|

#### 字串演算法 String Algorithms
| 章節 | 連結 |
| -------- | -------- |
|KMP 演算法 Knuth–Morris–Pratt Algorithm|link|
|馬拉車演算法 Manacher's Algorithm|link|
|Z 演算法 Z-function|link|

---

### 其他怪怪的東西 Wired Things
| 章節 | 連結 |
| -------- | -------- |
|競程會用的怪東西 Wired CP Habits|link|
|三分搜尋法 Ternary search|[link](https://hackmd.io/@ShanC/ternary-search)|
|暴力搜尋演算法 Brutal Force Algoritms|link|
|均攤分析 Amortized Analysis|link|
|穩定婚配問題 Stable Matching|link|
|可滿足性問題 SAT Problems|link|

----

### 相關連結
- [C程式設計導論](https://hackmd.io/@ShanC/SkZLe3v50)
- [CSES Competitive Programer's Handbook](https://cses.fi/book/book.pdf)
- [高中生解題系統 Zerojudge](https://zerojudge.tw/)
- [CSES Problem Set](https://cses.fi/problemset/)

----

## 關於本篇
ShanC 很廢，很喜歡理論的東西，不太喜歡碰程式

(2025/6/10)