ACM/ICPC算法訓(xùn)練教程

第1章　基礎(chǔ)算法
1.1 枚舉法
1.2 遞歸法
1.3 分治法
1.4 貪心法
1.4.1 擬陣
1.4.2 關(guān)于帶權(quán)擬陣的貪心算法
1.4.3 任務(wù)時(shí)間表問題
1.5 模擬法
第2章　數(shù)據(jù)結(jié)構(gòu)
2.1 基本數(shù)據(jù)結(jié)構(gòu)
2.1.1 堆棧
2.1.2 隊(duì)列
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章　動(dòng)態(tài)規(guī)劃
3.1 動(dòng)態(tài)規(guī)劃簡(jiǎn)介
3.1.1 動(dòng)態(tài)規(guī)劃的基本思想
3.1.2 動(dòng)態(tài)規(guī)劃法的步驟
3.1.3 動(dòng)態(tài)規(guī)劃問題的特征
3.1.4 適用動(dòng)態(tài)規(guī)劃解題的條件
3.2 線性動(dòng)態(tài)規(guī)劃
3.3 樹形動(dòng)態(tài)規(guī)劃
3.4 概率動(dòng)態(tài)規(guī)劃
3.5 動(dòng)態(tài)規(guī)劃中的狀態(tài)壓縮
第4章　數(shù)學(xué)問題
4.1 乘方取模和矩陣快速冪
4.1.1 乘方取模問題
4.1.2 矩陣快速冪
4.2 歐幾里得算法
4.2.1 最大公約數(shù)與歐幾里得算法
4.2.2 二元一次不定方程和擴(kuò)展歐幾里得算法
4.3 進(jìn)位制轉(zhuǎn)換
4.3.1 整數(shù)的進(jìn)位制轉(zhuǎn)換
4.3.2 小數(shù)的進(jìn)位制轉(zhuǎn)換
4.3.3 負(fù)進(jìn)位制
4.4 歐拉函數(shù)
4.4.1 剩余類、完全剩余系、簡(jiǎn)化剩余系的概念
4.4.2 歐拉函數(shù)
4.5 素?cái)?shù)判定和大數(shù)分解
4.5.1 素?cái)?shù)判定
4.5.2 大整數(shù)分解
4.6 中國(guó)剩余定理
4.7 polya原理
第5章　計(jì)算幾何
5.1 矢量
5.2 確定任意一對(duì)線段是否相交
5.3 線段合并
5.4 凸包
5.5 尋找最近點(diǎn)對(duì)
5.6 半平面交
5.7 旋轉(zhuǎn)卡殼
5.8 掃描線
5.9 計(jì)算幾何基本算法代碼集錦
第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)化）求最短路及判定負(fù)環(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 無(wú)向圖
7.4.2 有向圖
7.4.3 連通性問題示例
7.5 網(wǎng)絡(luò)流問題
7.5.1 網(wǎng)絡(luò)流概述
7.5.2 最大流
7.5.3 模型的建立
7.5.4 最大流應(yīng)用
7.5.5 費(fèi)用流
7.6 二分圖匹配
7.6.1 定義
7.6.2 二分圖的匹配
7.6.3 二分圖的最大匹配
7.6.4 與最大匹配相關(guān)的幾個(gè)問題
7.6.5 用最大流解決二分匹配
7.6.6 二分圖最優(yōu)匹配
7.6.7 用費(fèi)用流解決最優(yōu)匹配
第8章　字符串算法
8.1 kmp算法
8.2 字典樹
8.3 ac自動(dòng)機(jī)
8.4 后綴數(shù)組
參考文獻(xiàn)