# 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)|
|質數篩法 Sieve|[link](https://hackmd.io/@ShanC/prime_sieve)|
|快速冪與倍增法 Binary Exponentiation and Lifting|[link](https://hackmd.io/@ShanC/Binary-Exponentiation-and-Lifting)|
|暴力搜尋演算法 Brutal Force Algoritms|link|

## 競程章節
到這裡才是競程要搞的東西
原則上基礎圖論系列要一起讀

---

### 常見資料結構 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
| 章節 | 連結 |
| -------- | -------- |
|深度優先搜尋樹 DFS Tree Structure|[link](https://hackmd.io/@ShanC/dfs-tree)|
|拓樸排序 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)|
|Tarjan 離線 LCA 演算法|[link](https://hackmd.io/@ShanC/Tarjan-LCA)|
|樹壓平 Euler Tour Technique|[link](https://hackmd.io/@ShanC/Euler-Tour-Technique)|
|輕重樹鏈剖分 Heavy-light decomposition|link|

#### 路徑、迴路與環 Paths、Circuits and Cycles
| 章節 | 連結 |
| -------- | -------- |
|最短路徑問題 Shortest Path Problem|[link](https://hackmd.io/@ShanC/Shortest-Path)|
|Dijkstra's Algorithm|[link](https://hackmd.io/@ShanC/Dijkstra)|
|0-1 BFS|[link](https://hackmd.io/@ShanC/01-BFS)|
|Bellman-Ford Algorithm|[link](https://hackmd.io/@ShanC/Bellman-Ford-Algorithm)|
|Shortest Path Faster 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)|
|穩定婚配問題 Stable Matching|link|

#### 流量網路 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

#### 群論 Group Theory
群論編在這不是為了 cover 所有群論的內容，只是覺得多一個思考的工具，解題時就會多很多不同的視角。反正這是我的筆記，我想寫什麼就寫什麼

由於作者並非數學系出身，若內容有誤請提醒一下
| 章節 | 連結 |
| -------- | -------- |
|基礎群論 Basic Group Theory|link|
|拉格朗日定理 Lagrange's Theorem|[link](https://hackmd.io/@ShanC/Lagrange-Theorem)|
|商群 Quotient Group|link|
|群作用 Group Actions|link|
|軌道－穩定點定理 Orbit-stabilizer Theorem|link|
|同構定理 Isomorphism Theorems|link|
|Pólya 計數 Pólya Enumeration Theorem|link|

#### 數論 Number Theory

因為數論本身的證明有點麻煩，能用 group 就用，如果看不懂就看不懂吧!
反正我們資工的記結論就好
| 章節 | 連結 |
| -------- | -------- |
|基礎數論 Basic Number Theory|link|
|歐基里德演算法 Euclidean Algorithm|link|
|模運算 Modular Arithmetic|link|
|離散根號 Discrete Square Root|link|
|大步小步演算法 Baby-step Giant-step|link|
|費馬小定理 Fermat's Little Theorem|link|
|歐拉定理 Euler's Theorem|link|
|中國剩餘定理 Chinese Remainder Theorem|link|
|數論分塊|link|

#### 記數問題 Counting
| 章節 | 連結 |
| -------- | -------- |
|鴿籠原理 Pigeonhole Principle|[link](https://hackmd.io/@ShanC/Pigeonhole)|
|排列組合 Permutation and Combination|link|
|一些神奇的數列 Number Sequences|link|

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

#### 矩陣 Matrices
| 章節 | 連結 |
| -------- | -------- |
|矩陣基本操作 Basic Matrix Operations|link|
|高斯消去法 Gaussian Elimination|link|
|矩陣快速冪 Matrix Binary Exponentiation|link|

#### 賽局 Games
| 章節 | 連結 |
| -------- | -------- |
|零和賽局 Zero-sum Games|link|
|Sprague–Grundy 定理|link|

---

### 計算幾何 Computational Geometry
| 章節 | 連結 |
| -------- | -------- |
|點與線段 Points and Line Segments|link|
|凸包 Convex Hull|link|
|皮克定理 Pick's Theorem|link|
|多邊形 Polygons|link|

---

### 動態規劃 Dynamic Programming
DP 會這樣排是有我的想法的，不是亂排

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

| 章節 | 連結 |
| -------- | -------- |
|動態規劃導論 Introduce to Dynamic Programming|[link](https://hackmd.io/@ShanC/Intro-to-DP)|
|經典動態規劃問題 Classic DP Problems|[link](https://hackmd.io/@ShanC/classic-dp)|
|有向無環圖動態規劃 DP on Directed Acyclic Graph|link|
|最長遞增子序列 Longest Increasing Subsequence|[link](https://hackmd.io/@ShanC/LIS)|
|雙序列比對動態規劃 Two-Sequence DP|link|

#### 子集和動態規劃 Subset-Sum DP
| 章節 | 連結 |
| -------- | -------- |
|背包問題 Knapsack Problem |link|
|找零錢問題 Coin Change Problem|link|
|子集和動態規劃 Subset-Sum DP|link|
|P、NP 與 Pseudo-ploynomial|link|

#### 各種動態規劃 Various DP
| 章節 | 連結 |
| -------- | -------- |
|樹上動態規劃 DP on Tree|link|
|區間動態規劃 Interval DP|[link](https://hackmd.io/@ShanC/interval-dp)|
|位元壓縮動態規劃 Bitmask DP|link|
|數位動態規劃 Digit DP|link|
|子集求和動態規劃 Sum Over Subsets DP|link|
|Bitonic Travelling Salesman Problem|link|
|記數 & 機率動態規劃 Counting and Probability DP|link|

#### 優化 Optimizations

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

---

### 字串 String
#### 字串資料結構 String Data Structures
| 章節 | 連結 |
| -------- | -------- |
|有限自動機 Finite Automata|link|
|AC 自動機 Aho–Corasick Algorithm|link|
|後綴陣列 Suffix Array|link|
|後綴自動機 Suffix Automata|link|
|Trie|link|

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

---

### 其他怪怪的東西 Wired Things
#### {喵喵喵|Meow Meow Meow}
| 章節 | 連結 |
| -------- | -------- |
|VScode 設定|link|
|競程會用的怪東西 Wired CP Habits|link|
|競賽技巧|link|
|hackmd 筆記: md 語法與 $\LaTeX$ 語法|link|

#### 奇妙的{喵喵喵|Meow Meow Meow}
| 章節 | 連結 |
| -------- | -------- |
|三分搜尋法 Ternary search|[link](https://hackmd.io/@ShanC/ternary-search)|
|基礎線性規劃 Basic Linear Programming|link|
|均攤分析 Amortized Analysis|link|
|可滿足性問題 SAT Problems|link|
|圖靈機 Turing Machine|link|
|複雜度分類 Complexity Classes|link|
|可計算的問題 Computable Problem|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/)

----

## 關於本篇
- 之前好像 hackmd 有更新一些東西，所以調了排版
- 明明寫說是給初學者，但是卻放一堆進階的章節，基礎章節都不更新

(2026/1/21)