HackMD前言
我陸陸續續都有在寫演算法的筆記，只是沒有做一個比較完善的統整，剛好有CPE課程這個機會，所以就寫了這篇文。
參考資料全在我的主頁面的演算法連結，有些沒有的會放進去筆記裡面
資訊
- 前言
- CPE是什麼
- 教學規劃
- 課程須知
- 比賽資訊
- 各項檢定
- 日常
c++ 基礎知識
- 變數的宣告與指派
- 基本輸入輸出及標頭檔
- 進階輸入輸出
- 四則運算
- 條件判斷與基礎邏輯
- 進階運算
- 陣列
- 迴圈
- 迴圈特殊應用
- 函式
- 遞迴
- 區域、全域變數、靜態變數
演算法介紹
- 何謂演算法
- 演算法
- 寫演算法的好習慣及小技巧
- 演算法優劣
- 複雜度
- 複雜度的分析
- 複雜度的表示
- 大O記號
- 空間複雜度
- 時間複雜度
- 常見複雜度例子
- 偽多項式時間複雜度
- P，NP問題
- P
- NP
- NP-Complete
- NP-hard
- 結尾
基礎資料結構
- STL
- vector
- iterator 迭代器
- linked-list (競賽不常用)
- pair
- map
- queue
- deque
- set
- struct
- auto
排序搜尋
排序
- 選擇排序法
- 氣泡排序法
- 插入排序法
- 合併排序法
- 快速排序法
- c++內建排序
搜尋
- 線性搜尋(暴力搜)
- 二分搜尋
- 內建二分搜
- 三分搜尋
- 經典演算法DFS/BFS
greedy algorithm (貪婪法)
- 簡介
- 核心原理
- 換硬幣問題
- 單欄位資料排序
- 結構資料排序
- 外掛二分搜
- 掃描線演算法 sweep-line
Divide and Conquer (分治法)
- 簡介
- 核心想法
- 最大值與最小值問題
- 回顧合併排序法(待補)
- 回顧快速排序法(待補)
- 分治的複雜度
- 經典例子 反序問題
Dynamic Programming (動態規劃)
- 簡介
- 基本思維與步驟
- 狀態轉移
- 分類與複雜度
- bottom up / top down
- 經典LCS例子(最長共同序列)
- 經典背包問題
- 01背包
- 完全背包
- 多重背包
DP DP DP 深入動態規劃
- 滾動數組
- 狀態壓縮
- 滾動DP/狀壓DP(位元DP)
- 單調性質(monotonicity)
- 單調隊列優化
- 斜率優化
基本數論I
- 快速冪
- 模運算 & 模逆元
- 矩陣快速冪
- 質因數分解
- 歐幾里得算法(輾轉)
- 拓展歐幾里得(extgcd)
- 中國剩餘定理(Chinese remainder theorem, CRT)
- 排容定理
- 鴿籠原理 :dove_of_peace:
基本圖論I 未完工
進階 (尚未):
- 匹配與網路流 Flow / Match / KM / 二分圖
- 樹論 Tree Hash / DSU on Tree / Heavy Light Decomposition
- 字串 SA / Palindromic Tree / Minimum Rotation
- DP與數學 狀態壓縮 / SOS DP / 莫比烏斯反演 / 歐拉 / Pólya lemma / burnside lemma
- 進階圖論 SCC / BCC / 2-SAT
- 綜合數學 Miller Rabin/ Pollard Rho / DiscreteSqrt / 高斯消 / FFT / NTT / Josephus Queries /
- 計算幾何 掃描線 / Pick 定理 / 凸包操作
- CDQ分治 / 二維資節 / 持久化 / 莫隊排序
