---
title: 110下學期 競程 預定課程
---
## 簡介

在程式競賽中, 參賽者會需要絞盡腦汁發明一些演算法來解決各式各樣的程式問題, 而這堂課會教大家在程式競賽中, 一些泛用演算法背後的思想, 以及一些具有啟發性的演算法問題, 希望能夠幫助想要投入程式競賽的人.

[還不了解什麼是競賽程式的可以點這裡](https://drive.google.com/file/d/1zO3rwD2ERsC25kFQLngWKkbQZpj0CQ1o/view?usp=sharing)

## 預防針(?

如果認真想投入程式競賽的話, 光靠聽課是不夠的, 課程只能教各種演算法的概念以及實作.

要成為一個合格的競程選手主要還是需要自己花費大量的時間想題目, 學習如何觀察題目的性質以及思考各種演算法的使用時機.

## 各大競程題庫/比賽平台/學習資源

[AtCoder](https://atcoder.jp/)
[Codeforce](https://codeforces.com/)
[CSES](https://cses.fi/problemset/)
[TIOJ](https://tioj.ck.tp.edu.tw/)
[POI](https://szkopul.edu.pl/)

[AP325 作者: 吳邦一教授](https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m?fbclid=IwAR12n0wUw8Ye2PXFlVJqQbhhDHDEYx3NgQyWQflQx5CaTYIyKDK1vuHYP64)
[USACO guide](https://usaco.guide/)
[板中講義](https://sites.google.com/site/pcshic/zi-xun-pei-xun)

## 上學期的課程內容

[introduction](https://hackmd.io/@cpsd/rkUsjuoGK)
[complexity(時間複雜度分析)](https://hackmd.io/@cpsd/cpp_advanced_l2)
[STL/basic data structure](https://hackmd.io/@cpsd/cpp_advanced_l3)
[enumeration(枚舉)](https://hackmd.io/@cpsd/cpp_advanced_l4)
[basic graph theory(基礎圖論)](https://slides.com/shioko/test#/6/5)

## 先備知識

- C的語法基礎
- 變數
- 運算子
- 迴圈
- 陣列
- 條件判斷
- 輸入/輸出
- 結構(struct)
- 函式
- 遞迴
- 位元操作
- 熟悉C++的[STL(標準模板庫)](https://hackmd.io/@cpsd/cpp_advanced_l3)
- iterator
- sort
- vector
- set/map
- stack/queue/deque
- priority_queue
- pair
- 了解[時間複雜度]((https://hackmd.io/@cpsd/cpp_advanced_l2))的估算

##### optional

希望大家可以讀得懂英文題目, 因為練習的題目還是英文居多QQ

[範例-Codeforce](https://codeforces.com/problemset/problem/1634/A)
[範例-AtCoder](https://atcoder.jp/contests/abc238/tasks/abc238_b)
[範例-CSES](https://cses.fi/problemset/task/1094)

## 日程

預計是每個禮拜六的下午時段(約3.~5.) 採用線上同步教學

至於週三社課時間還不確定要做啥 有想要做啥的都可以提出來喔><

3/12 : [greedy(貪心法)](https://slides.com/shioko/deck)
3/19 : divide and concour(分治法)
3/26 (段考)
4/2 (連假)
4/9 (班排)
4/16 : 其他常用算法跟一些數學東東
4/23 : basic dynamic programming - part1
4/30 : basic dynamic programming - part2
5/7 : (段考)
5/14 : basic graph theory - part1
5/21 : basic graph theory - part2
5/28 : basic graph theory - part3
6/4 (連假)
6/11 : graph + dynamic programming
6/18 : advanced data structure
6/25 (段考)

## 課程細節

#### 01. greedy(貪心法)
- 貪心法的核心想法
- exchange argument

#### 02. divide and concour(分治法)
- maximum subarray problem(最大連續子序列和問題)
- merge sort(合併排序法)

#### 03. 其他常用算法跟一些數學東東

- binary search(二分搜)
- two pointer(雙指標)
- fast exponential(快速冪)
- modulo(模除)
- modular multiplicative inverse(模逆元)
- Euler's theorem(歐拉定理)
- 質數篩法
- Harmonic series(調和級數)
- sieve of Eratosthenes(埃氏篩法)

#### 04. basic dynamic programming(基礎動態規劃)

##### part1:

- DP properties(DP的性質)
- classic DP problems(經典DP問題)
- fibonacci sequence(斐波那契數列)
- path on grid(方格路徑)

##### part2:

- classic DP problems(經典DP問題)
- knapsack problem(背包問題)
- longest increasing subsequence, LIS(最長遞增子序列)
- longest common subsequence, LCS(最長共同子序列)
- range DP(區間DP)

#### 05. basic graph theory(基礎圖論)

##### part1:

- store graph(存圖)
- adjacent list(鄰接串列)
- adjacent matrix(鄰接矩陣)
- BFS(廣度優先搜索)
- DFS(深度優先搜索)

##### part2:

- shortest path(最短路徑)
- some properties of SP(最短路徑的一些性質)
- relaxtion(鬆弛)
- Bellman-Ford algorithm
- Dijkstra's algorithm
- Floyd-Warshall algorithm

##### part3:

- properties of tree(樹的性質)
- minimum spanning tree(最小生成樹)
- Disjoint Set(並查集)
- Prim's algorithm
- Kruskal's algorithm
- binary lifting(倍增法)
- lowerest common ancestor, LCA(最低共同祖先)

#### 06. graph + dynamic programming

- topological sort(拓撲排序)
- bitmask DP(位元DP)
- travelling salesman problem, TSP(旅行推銷員問題)
- hamiltonial path(哈密頓路徑)
- tree dp(樹dp)

#### 07. advanced data structure(進階資料結構)

- prefix sum(前綴和)
- difference(差分)
- discretization(離散化)
- binary indexed tree, BIT(樹狀數組)

#### 一些放不下的主題, 有額外時間的話可能會講吧(??

- data structure - segment tree(線段樹)
- data structure - sparse table(稀疏表)
- graph theory - eulerian tour(一筆劃問題)
- graph theory - bipartite graph(二分圖判定)
- graph theory - 2CC/BCC/SCC(點(邊)雙連通元件/強連通元件)
- dynamic programming - optimization(DP優化)
- string - KMP algorithm
- string - Gusfield's algorithm
- string - Manacher's algorithm
- string - rolling hash(雜湊)
- string - trie(字典樹)