藍橋杯算法考點:
基礎算法。壹星:打表,枚舉,倍增,離散化,差分。二星:分治法,貪心(Huffman編碼), 尺取法, 二分法,三分法,整體二分,ST算法。
搜索。壹星:基本DFS,基本BFS。二星:DFS記憶化搜索,IDA* BFS擴展(雙向廣搜,優先隊列,雙端隊列),剪枝,爬山算法,隨機增量法,模擬退火。三星:A*。
高級數據結構。壹星:並查集(帶權),分塊。二星:莫隊算法(樹上莫隊) 樹狀數組,線段樹 可持久化線段樹,二叉搜索樹,treap樹,替罪羊樹,塊狀鏈表。三星:splay樹,LCT,樹套樹,貓樹,CDQ分治,舞蹈鏈,左偏樹,後綴平衡樹,KDtree。
動態規劃:DP問題的性質(重疊子問題,最優子結構,無後效性),編碼方法(記憶化遞歸,遞推),滾動數組,常見線性DP(0/1問題,分組背包,多重背包,最長公***子序列(LCS),最長遞增子序列(LIS),編輯距離,最小化分,行走問題,矩陣最長遞增路徑,子集和問題,矩陣鏈乘法,布爾括號問題)。
區間DP,狀態壓縮DP,樹形DP,數位DP,計數類DP,概率DP。插頭DP,基環樹DP,DP優化(數據結構優化,單調隊列優化,斜率優化,分治優化,四邊形不等式優化)。