ACM/ICPC算法訓練教程

第1章　基礎算法
1.1 枚舉法
1.2 遞歸法
1.3 分治法
1.4 貪心法
1.4.1 擬陣
1.4.2 關于帶權擬陣的貪心算法
1.4.3 任務時間表問題
1.5 模擬法
第2章　數(shù)據(jù)結構
2.1 基本數(shù)據(jù)結構
2.1.1 堆棧
2.1.2 隊列
2.1.3 堆
2.1.4 并查集
2.2 線段樹
2.3 樹狀數(shù)組
2.4 搜索樹
2.4.1 二叉搜索樹
2.4.2 avl 搜索樹
2.4.3 紅黑樹
2.4.4 伸展樹
2.4.5 treap 樹堆
2.4.6 sbt
2.4.7 跳躍表
2.5 hash 表
2.6 左偏樹
第3章　動態(tài)規(guī)劃
3.1 動態(tài)規(guī)劃簡介
3.1.1 動態(tài)規(guī)劃的基本思想
3.1.2 動態(tài)規(guī)劃法的步驟
3.1.3 動態(tài)規(guī)劃問題的特征
3.1.4 適用動態(tài)規(guī)劃解題的條件
3.2 線性動態(tài)規(guī)劃
3.3 樹形動態(tài)規(guī)劃
3.4 概率動態(tài)規(guī)劃
3.5 動態(tài)規(guī)劃中的狀態(tài)壓縮
第4章　數(shù)學問題
4.1 乘方取模和矩陣快速冪
4.1.1 乘方取模問題
4.1.2 矩陣快速冪
4.2 歐幾里得算法
4.2.1 最大公約數(shù)與歐幾里得算法
4.2.2 二元一次不定方程和擴展歐幾里得算法
4.3 進位制轉換
4.3.1 整數(shù)的進位制轉換
4.3.2 小數(shù)的進位制轉換
4.3.3 負進位制
4.4 歐拉函數(shù)
4.4.1 剩余類、完全剩余系、簡化剩余系的概念
4.4.2 歐拉函數(shù)
4.5 素數(shù)判定和大數(shù)分解
4.5.1 素數(shù)判定
4.5.2 大整數(shù)分解
4.6 中國剩余定理
4.7 polya原理
第5章　計算幾何
5.1 矢量
5.2 確定任意一對線段是否相交
5.3 線段合并
5.4 凸包
5.5 尋找最近點對
5.6 半平面交
5.7 旋轉卡殼
5.8 掃描線
5.9 計算幾何基本算法代碼集錦
第6章　搜索算法
6.1 深度優(yōu)先搜索
6.2 廣度優(yōu)先搜索
6.3 啟發(fā)式搜索
第7章　圖算法
7.1 圖的表示方式
7.2 最短路算法
7.2.1 dijkstra算法求最短路
7.2.2 spfa（bellman-ford算法優(yōu)化）求最短路及判定負環(huán)
7.2.3 floyd求最短路
7.2.4 第k短路（a*算法）
7.2.5 差分約束系統(tǒng)
7.3 生成樹算法
7.3.1 prim算法求最小生成樹
7.3.2 kruskal求最小生成樹
7.3.3 次小生成樹
7.3.4 最優(yōu)比率生成樹
7.3.5 最小度限制生成樹
7.4 圖的連通性問題
7.4.1 無向圖
7.4.2 有向圖
7.4.3 連通性問題示例
7.5 網絡流問題
7.5.1 網絡流概述
7.5.2 最大流
7.5.3 模型的建立
7.5.4 最大流應用
7.5.5 費用流
7.6 二分圖匹配
7.6.1 定義
7.6.2 二分圖的匹配
7.6.3 二分圖的最大匹配
7.6.4 與最大匹配相關的幾個問題
7.6.5 用最大流解決二分匹配
7.6.6 二分圖最優(yōu)匹配
7.6.7 用費用流解決最優(yōu)匹配
第8章　字符串算法
8.1 kmp算法
8.2 字典樹
8.3 ac自動機
8.4 后綴數(shù)組
參考文獻