課前自我鍛鍊

先到各大 Online Judge 申請帳號寫題目吧!

舒適的打比賽環境

  • 建置你的開發環境
  • 測試比賽環境指南
  • 點心 x 飲料 x 氣球

預備的預備知識

  • 網路資源
  • 你的好友

初階資料結構

預備知識

  • 前綴和、差分
  • C++ 指標

課程大綱

  • std::bitset
  • 併查集
  • Sparse Table
  • 線段樹、BIT、樹堆
  • 懶人標記、持久化、動態開點

樹上資料結構

上課不會複習的預備知識

  • 基礎基礎圖論(什麼是生成樹?什麼是連通圖?等等)
  • C++ 指標

上課會複習的預備知識

  • 自平衡二元搜尋樹之 splay tree
  • 樹鏈剖分與重心剖分

課程大綱

  • Link cut tree
  • Euler tour tree
  • Top tree
  • 動態樹(傳說中的 AAA 樹?)
  • 動態連通性

數學

預備知識

  • 高中排列組合
  • 高中矩陣運算
  • 高中微積分

課程大綱

  • 計數原理
  • 生成函數
  • 數論
  • 線性代數
  • Burnside’s lemma

動態規劃

預備知識

  • 經典 DP 問題(背包、LCS、LIS)
  • 前綴和

課程大綱

  • 單調隊列優化
  • 斜率優化
  • 1D/1D 凹、凸優化
  • 2D/1D 凹、凸優化
  • Aliens 優化
  • SMAWK

初階圖論

預備知識

  • DFS、BFS
  • 並查集
  • 最短路(dijkstra)

課程大綱

  • 連通分量
  • 樹論
  • 最短路(差分約束、同餘最短路)
  • 歐拉迴路
  • 優化建圖

進階圖論

預備知識

  • 最短路演算法(Dijkstra、Floyd-Warshall、Bellman-Ford、SPFA)
  • DFS、BFS、生成樹
  • 強連通分量
  • 最小生成樹
  • 簡單的數論
  • 高斯消去法

課程大綱

  • 再談最短路
  • 困難問題的 special cases
  • 環與迴路
  • 平面圖
  • 不帶權二分圖匹配
  • Matroid

網路流

預備知識

  • 基礎的圖論

課程大綱

  • 網路流演算法實作
  • 網路流演算法應用
  • Stoer-Wagner Algorithm & Gomory-Hu Tree

隨機算法

預備知識

  • C++ 內建的 rand 函數
  • 一些基礎的機率、統計、字串和計算幾何

課程大綱

  • Random generator
  • 隨機與 hash
  • 隨機與小聰明
  • 隨機與環形分堆
  • 隨機與誤差
  • 隨機增量法
  • 隨機與 NPC 問題(最大團、最短漢米爾頓路徑)

非典型題目

預備知識

  • 高中數學
  • 基礎資料結構
  • 基礎圖論

課程大綱

  • 互動題
  • Two Steps 與資訊壓縮
  • Output Only 題與 Heuristic
  • 構造程式題