ACM程序設計競賽基礎教程

第1章 基礎算法
1.1 分治
1.2 遞歸
1.3 枚舉
1.4 貪心
第2章 排序、查找算法
2.1 基本排序算法
2.1.1 插入排序
2.1.2 冒泡排序
2.1.3 快速排序
2.1.4 其他排序
2.2 基本查找算法
2.2.1 順序查找
2.2.2 折半查找
2.3 實例分析
2.4 小結(jié)
第3章 數(shù)據(jù)結(jié)構(gòu)基礎
3.1 常用數(shù)據(jù)結(jié)構(gòu)簡介
3.1.1 線段樹簡介
3.1.2 并查集簡介
3.1.3 樹狀數(shù)組簡介
3.2 實例分析
第4章 字符串
4.1 字符串匹配
4.1.1 樸素的字符串匹配算法
4.1.2 KMP算法
4.1.3 其他匹配算法
4.2 實例分析
4.3 小結(jié)
第5章 搜索算法
5.1 基本搜索算法
5.1.1 遞歸與迭代
5.1.2 深度優(yōu)先搜索與廣度優(yōu)先搜索
5.1.3 回溯
5.2 搜索算法的一些優(yōu)化
5.2.1 剪枝函數(shù)
5.2.2 雙向廣度搜索
5.3 實例分析
5.4 小結(jié)
第6章 圖論算法
6.1 最短路徑
6.1.1 Dijkstra算法
6.1.2 Floyd算法
6.1.3 Bellman—Ford算法
6.2 最小生成樹
6.2.1 Kruskal算法
6.2.2 Prim算法
6.3 最大匹配——匈牙利算法
6.4 最優(yōu)權(quán)匹配問題
6.4.1 理論基礎
6.4.2 基本思想
6.4.3 樣例代碼
6.5 割點、割邊以及連通分量
6.5.1 理論基礎
6.5.2 求割點
6.5.3 求強連通分量
6.6 網(wǎng)絡流
6.6.1 理論基礎
6.6.2 最大流問題
6.6.3 最小費用最大流問題
6.7 實例分析
6.8 小結(jié)
第7章 動態(tài)規(guī)劃算法
7.1 基本思想
7.2 基本概念
7.3 基本原理
7.3.1 最優(yōu)化原理
7.3.2 無后效性
7.4 基本步驟
7.5 經(jīng)典例子
7.6 實例分析
7.7 小結(jié)
第8章 計算幾何基礎
8.1 矢量
8.1.1 矢量的概念
8.1.2 矢量加減法
8.1.3 矢量叉積
8.1.4 矢量叉積的應用
8.2 包含關(guān)系
8.2.1 判斷圖形是否包含在矩形中
8.2.2 判斷圖形是否包含在多邊形中
8.2.3 判斷圖形是否包含在圓中
8.3 凸包
8.3.1 凸包的概念
8.3.2 凸包的求法
8.4 實例分析
第9章 數(shù)論
9.1 基本數(shù)學算法
9.1.1 素數(shù)篩選
9.1.2 最大公約數(shù)
9.1.3 快速乘方
9.2 實例分析
附錄A 綜合訓練題
A.1 LuckyBird
A.2 Josephus’problem
A.3 Counter Strike
A.4 Gauss Elimination
A.5 The Math Problem
A.6 Mobile phones
A.7 Japan
A.8 骨灰級玩家考證篇
A.9 括號匹配
A.10 食物鏈