NOIP/CSP 算法競賽 C++ 知識體系全景圖：從入門到省隊的完整學習路線

核心算法知識圖譜

1. 基礎算法與數據結構（必修）

• 排序：快排、歸並、堆排、基數排序、std::sort 實現原理
• 查找：二分查找變體（下界/上界/最近值）、三分查找
• 數據結構：鏈表、棧/隊列、堆（優先隊列）、並查集、線段樹、樹狀數組、Trie 字典樹、平衡樹（Treap/SBT/红黑樹原理）

2. 搜索與圖論（核心分值）

3. 動態規劃（靈魂考點）

• 線性 DP：最長上升子序列(LIS)、背包完全/多重/分組/依賴、區間 DP(石子合併/矩陣鏈乘法)
• 樹形 DP：樹上背包、樹的直徑/重心、獨立集/支配集
• 狀態壓縮 DP：漢密爾頓路徑、旅行商問題(TSP)、插頭 DP(連通性狀態)
• 數位 DP：計數問題、位運算優化
• 優化技巧：單調隊列/凸包/斜率/分治/四邊形不等式/狀態壓縮

4. 字符串算法

• KMP、Z-function、Manacher、AC 自動機、後綴數組/自動機 (SA/SAM)、回文樹

5. 數學與數論

• 快速冪、擴展歐幾里得、中國剩餘定理、莫比烏斯反演、杜教篩、米勒拉賓/波拉德 Rho 分解、多項式乘法(NTT/FFT)

6. 進階技巧（加分項）

• 位運算優化、分塊/莫隊、CDQ 分治、線性基、隨機化算法、幾何模板（向量/叉積/凸包/旋轉卡殼）

訓練體系建議

1. 分專題刷題：按上述分類，每類精選 20-50 題（Luogu/Codeforces/AtCoder）
2. 虛擬比賽：每周 1-2 場 CF/AtCoder/洛谷月賽，復盤補漏
3. 總結模板庫：維護個人模板（快速冪、線段樹、Dinic、DP 優化等），考試直接調用
4. 讀題解/源碼：大神代碼風格、邊界處理、常數優化

刷題平台推薦

NOIP 不按大綱出題，核心在「建模能力」與「代碼實現力」。堅持「日刷一題、周賽一場、月總結一次」，厚積薄發。