【他人整理】NOIP知識點彙總

轉載自大佬部落格，整理的很好，贊一個。

轉載過來，自己打鈎檢查NOIP複習情況。（實際懶得打勾）

如果……如果我還有資格參加省選的話（或者要在聯賽前準備省選），再把省選的知識點彙總轉載過來吧。（咕咕咕）

基礎算法

貪心√、枚舉√、分治√、二分√、倍增√、*構造√、高精√、模拟√

圖論

圖

最短路（dijkstra、spfa、floyd），差分限制

最小生成樹（kruskal、prim）

并查集（擴充域）

拓撲排序

二分圖染色，*二分圖比對

tarjan找scc、橋、割點，縮點

*分數規劃

樹

樹上倍增（LCA）

樹的直徑、樹的重心

dfs序

*樹鍊剖分

數論

gcd、lcm√

埃氏篩法√

exgcd，求解同餘方程、逆元√

快速幂√

*組合數學√

矩陣√

資料結構

連結清單、隊列（單調隊列）、棧（單調棧）√

堆、st表、hash表

線段樹、樹狀數組√

字典樹

*分塊√

動态規劃

背包DP、樹形DP、記憶化搜尋、遞推

區間DP、序列DP

*DP優化（不涉及斜率優化、四邊形不等式等等）

搜尋

暴搜（dfs、bfs）

搜尋的剪枝

啟發式搜尋（A*）

疊代加深搜尋、* IDA*

*随機化搜尋

其他算法

STL的基本使用方法√

腦洞的正确使用方法

*KMP

*狀态壓縮