常用/常考算法總結

轉自tangjz的部落格... 基礎算法 模拟 搜尋 廣度優先搜尋(BFS) 優化：雙向BFS 深度優先搜尋(DFS) 優化：折半DFS 疊代加深搜尋(IDS) 啟發式搜尋(Astar) 優化：IDAstar 優化：剪枝、位運算 排序 冒泡排序/選擇排序 基數排序/桶排序 計數排序 插入排序/希爾排序 快速排序 歸并排序/求逆序對數 堆排序 貪心 分治 二分/三分/n分 cdq分治 倍增/ST 離散化 二分答案 快速幂/十進制快速幂 基礎數學 數列求和 泰勒展開 矩陣 矩陣乘法 高斯消元 判斷線性相關 Catalan數 組合數學 加法原理/乘法原理 組合數遞推/楊輝三角 二項式定理 抽屜原理/鴿籠原理 Lucas定理 容斥原理 數論 質數判定/Miller-Rabin檢驗 分解質因數/求約數 歐幾裡得算法/輾轉相除法 擴充歐幾裡得算法/乘法逆元/二進制一次同餘方程 線性預處理1-n乘法逆元 素數篩 埃拉托斯特尼篩 歐拉篩 歐拉函數 莫比烏斯函數 費馬小定理 威爾遜定理 中國剩餘定理/孫子定理 二次剩餘/Cipolla's Algorithm 原根 離散對數/Baby-Step Giant-Step 群論 置換 Burnside引理 Polya定理 動态規劃 背包dp 01背包 完全背包 多重背包 混合背包 二維背包 分組背包 樹形背包 泛型背包 按次元 線性dp 區間dp 高維dp 按類型 劃分dp 最長上升子序列(LIS) 最長公共子序列(LCS) 有向無環圖(DAG)上dp (基于聯通性的)狀态壓縮dp 優化 滾動數組 字首和 四邊形不等式 斜率優化 位運算 資料結構 cdq分治 技巧 記憶化搜尋 順推/逆推 最小表示法 圖論 連通性 圖的周遊 拓撲排序 強聯通分量 割點、橋、雙聯通分量/tarjan算法 樹 最近公共祖先(LCA)/tarjan算法 樹的中心/直徑 樹的重心 樹的同構 最短路 多源最短路徑(APSP)/floyd 最小環 傳遞閉包 單源最短路徑(SSSP)/queue+bellman-ford/heap+dijkstra 生成樹 最小生成樹 最小比例生成樹 最小瓶頸樹 二分圖 二分圖驗證 二分圖染色 最大比對/匈牙利算法 最優比對/KM算法 網絡流 dinic算法 isap算法 預流推進算法 技巧：拆點 優化：合點/合邊 優化：線段樹 資料結構 高精度 高精度對低精度加減乘除取餘 高精度對高精度加減乘除取餘 優化：快速傅裡葉變換 連結清單 單雙向連結清單 塊狀連結清單 鄰接表/邊表 棧 隊列 循環隊列 優先隊列/最小二叉堆 左偏樹 Fibonacci堆 樹 二叉查找樹 堆(同上) 笛卡爾樹 樹狀數組 線段樹 拓展：動态線段樹、四分樹 重量平衡樹 伸展樹 并查集 哈希表(Hash) 自動機 字元串 Trie樹 KMP Manacher AC自動機(Aho-Corasick Automaton) 字尾數組/字尾樹/字尾自動機/字尾平衡樹等 動态樹 樹鍊剖分/樹塊剖分 Link-Cut Tree/Euler-Tour tree 計算幾何 平面幾何/立體幾何/解析幾何/參數方程 判斷點與多邊形關系(轉角法/掃描線法) 多邊形面積交/面積并 極角排序 凸包/旋轉卡殼 半平面交 三角剖分/Voronoi圖 博弈論 SG組合遊戲/SG函數 Bash遊戲/Wythoff遊戲/NIM遊戲 對抗搜尋 機率論 完全機率 Bayes定理 Markov過程 Chebyshev定理 雜項 分塊 随機調整/模拟退火/随機爬山 單純形法

轉載于:https://www.cnblogs.com/lowsfish/p/4297895.html