營隊課程

(註：課程內容課綱可能會有所微調，部分課程會能力分班以調整上課狀況，最終結果會再逕行公告)

程式競賽基本知識與技巧

首先會先介紹一些基本的觀念，以及針對基礎語法進行補強的教學，並且會有多年程式競賽經驗的選手分享比賽的過程。

排序與搜尋

排序與搜尋是演算法的入門。各位以前應該都學過氣泡排序法 (bubble sort)、選擇排序法 (selection sort) 等等簡單的排序法,然而這些 O(N^2) 的排序法難以解決規模較大的問題。本章節將介紹幾種時間複雜度為 O(N log N) 的排序法,並且介紹如何藉由單調性加速我們搜尋的效率。

• Merge sort, Quick sort
• Priority queue
• 二分搜尋法、三分搜尋法

動態規劃 ( 基礎/進階 )

基礎班：

動態規劃（Dynamic Programming, DP）是一種通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。

課程會分成三個部分，每個部分講解三題例題：

• 第一部分用簡單的問題介紹各種動態規劃的基本觀念與理論。
• 第二部分講解LIS、LCS與背包問題這三個經典的動態規劃問題。
• 第三部分用較進階但實作簡單的問題，來補充各種解題技巧和思考方法。

先備知識：熟悉C或C++基本語法當中的輸入輸出、基本運算、變數、一維陣列與二維陣列、if判斷式、for迴圈。

進階班：

進階班主要希望已經有DP基礎的同學可以更深入了解理論，並且學到一些技巧。

課程會分成三個部分共7題例題，其中5題例題集中在第二部分，因為第一與第三部分主要希望同學能接觸證明的邏輯：

• 第一部分主要講DP的理論面，包括圖論觀點與證明方法。
• 第二部分講解常見的DP優化方式，分別為紀錄前綴和、線段樹DP、單調佇列優化。
• 第三部分藉由講解divide and conquer DP 優化技巧讓讀者接觸並欣賞進階的優化技巧及證明。

先備知識：基礎DP，基礎資料結構如線段樹，平衡搜索樹，陣列等等。

資料結構 ( 基礎/進階 )

資料結構 + 演算法 = 程式，介紹⼀些基本資料結構，⾸先介紹常⽤的 Stack、Queue、Priority Queue 等基本資料結構。後面介紹當今解決序列操作問題不可或缺的技巧—線段樹、樹堆以及分塊與其應⽤。

基礎班：

• STL (vector / queue / stack / ...)
• Disjoint Set
• 基礎分塊
• 基礎線段樹
• Binary Indexed Tree

進階班：

進階班課程會圍繞在序列問題上。

• 線段樹區間修改
• 線段樹各種常見應用與技巧
• 樹堆 Treap
• 持久化資料結構
• 分塊法
• 莫隊算法

先備知識：線段樹、樹、遞迴與指標使用等。

貪心策略

貪心是三大演算法觀念其中之一，其概念相當抽象，做法簡單，但要證明方法正確是不容易的事情。在本章節透過經典題型的演練，以及證明的輔助來窺探貪心策略的蓋念。

數論(Number Theory)

競賽中數論問題通常會與⼀些性質結合，會講解⼀些基本的數論定義、定理，以及利⽤藉由定理基礎寫出競賽中能夠使⽤的演算法。

計算幾何(Computational Geometry) ( 基礎/進階 )

計算幾何融合了解析幾何和演算法，⼀般的幾何問題到電腦中必須要⽤數值的⽅式表⽰並計算，除了點、線、⾯要如何表⽰之外還要解決浮點數的精度誤差。

字串處理 ( 基礎/進階 )

相對於整數，字串是資訊科學特有的資料結構。應⽤也很廣泛，從資料庫、掃毒軟體、文字編輯器都看得到他的⾝影。字串處理問題是十分常見的問題，除了可以利用資料結構處裡之外，也可以設法擷取字串的資訊，讓問題有更進一步的轉變。

• How to use std::string
• KMP / Z-value
• 後綴數組SA / 最⻑共同前綴LCP

圖論 ( 基礎/進階 )

此處的圖並不是指圖片 (Picture)，⽽是更近似於關係圖的概念。⼀個圖 (Graph) G 是由節點 (Vertex) 的集合 V 和邊 (Edge) 的集合 E 所組成的離散結構，圖論會需要結合較多的概念來完成實作。

• How to build graph
• Tree
• Shortest Path, A* ,DFS / BFS
• 最⼩⽣成樹MST