營隊課程
程式競賽基本知識與技巧
程式競賽基本知識與技巧
由多年程式競賽經驗的選手分享比賽的過程,以及針對C++的基礎語法進行補強的教學
排序與搜尋 (New Topic)
排序與搜尋 (New Topic)
吸收了去經驗,我們將基礎觀念的排序與搜尋獨立成一個單元,希望對於初學者可以跳脫一般課本/參考資料對於搜尋法的認知
- 排序演算法的分類
- std::sort
- priority queue
- 二分搜尋法、upper_bound、lower_bound
- 三分搜尋法
貪心策略
貪心策略
貪心是三大演算法觀念其中之一,其概念相當抽象,做法簡單,但要證明方法正確是不容易的事情。在本章節透過經典題型的演練,以及證明的輔助來窺探貪心策略的蓋念。
- 經典題目演練
動態規劃
動態規劃
動態規畫也是三大演算法觀念其中之一,堪稱是程式設計的排列組合題目,如何透過遞迴與數學觀念,巧妙的將問題轉換成容易解決的形式是相當重要的一件事情。
- 經典問題:背包問題、LCS
- 數位統計DP (new)
- 遊戲必勝策略(new)
- 位元DP
資料結構
資料結構
資料結構 + 演算法 = 程式,在本單元中,本次由請資料結構大師,樹的傳人來帶領大家實作並應用競賽常見的資料結構。本單元較困難的部份於晚上進階班授課。
- STL (vector / queue / stack/...)
- Binary Index Tree
- Disjoint Set
- 分塊法 (new)
- 線段樹
數學方法
數學方法
利用程式來解決純數學問題會需要應用到一些數學的定理本單元節選了常見的質數/取模問題,以及新加入了計算幾何學,透過凸多邊形包覆,來讓大家認識如何在程式設計精準的處裡座標點的問題。
- 質數
- 模運算與求整數解
- 向量觀念 (new)
- 凸包 (new)
字串處理
字串處理
字串處理問題是十分常見的問題,除了可以利用資料結構處裡之外,也可以設法擷取字串的資訊,讓問題有更進一步的轉變。
- How to use std::string
- KMP/Z
- SA/LCP
圖論
圖論
圖論是本次營隊的最後一個章節,相較於前項主題,圖論會需要結合較多的概念來完成實作,除了經典問題之外,本次還加入了A*演算法來拓展圖論的應用層面。
- How to build graph
- DFS / BFS
- Shortest Path, A* (new)
- MST
- Basic Tree