程序設計解題策略

前言
第1章 利用樹型數據關系的解題策略
1.1 利用划分樹求解整數區間內第k大的值
1.1.1 離線構建整個查詢區間的划分樹
1.1.2 在划分樹上查詢子區間［l，r］中第k大的數
1.1.3 應用划分樹解題
1.2 利用最小生成樹及其擴展形式解題
1.2.1 最小生成樹的思想和應用
1.2.2 最優比率生成樹的思想和應用
1.2.3 最小k度限制生成樹的思想和應用
1.2.4 次小生成樹的思想和應用
1.3 利用線段樹解決區間計算問題
1.3.1 線段樹的基本概念
1.3.2 線段樹的基本操作和拓展
1.3.3 應用線段樹解題
1.4 利用改進型的二叉查找樹優化動態集合的操作
1.4.1 改進型1：伸展樹
1.4.2 改進型2：紅黑樹
1.4.3 應用改進型的二叉查找樹解題
1.5 利用動態樹維護森林的連通性
1.5.1 動態樹的問題背景
1.5.2 Link-Cut Tree的定義
1.5.3 Link-Cut Tree的基本操作和時間復雜度分析
1.5.4 應用動態樹解題
1.6 利用左偏樹實現優先隊列的合並
1.6.1 左偏樹的定義和性質
1.6.2 左偏樹的操作
1.6.3 應用左偏樹解題
1.7 利用跳躍表替代樹結構
1.7.1 跳躍表的基本概念
1.7.2 跳躍表的基本操作
1.7.3 跳躍表的效率分析
1.7.4 應用跳躍表解題
本章小結
第2章 利用圖型數據關系的解題策略
2.1 利用網絡流算法解題
2.1.1 網絡、流與割的概念
2.1.2 利用Dinic算法計算最大流
2.1.3 求容量有上下界的最大流問題
2.1.4 計算最小費用最大流
2.2 利用圖的匹配算法解題
2.2.1 匹配的基本概念
2.2.2 計算二分圖的最大匹配
2.2.3 計算二分圖最佳匹配的KM算法
2.2.4 利用一一對應的匹配性質轉化問題的實驗范例
2.3 利用分層圖思想解題
2.3.1 利用分層圖思想化未知為已知
2.3.2 利用分層圖思想優化算法的實驗范例
2.4 利用平面圖性質解題
2.4.1 平面圖的基本概念
2.4.2 平面圖的實驗范例
2.4.3 偏序集的基本概念
2.4.4 偏序集的實驗范例
2.5 在充分挖掘和利用圖論模型性質的基礎上優化算法
2.5.1 優化圖論模型的三種方法
2.5.2 三種優化方法的實驗范例
本章小結
第3章 數據關系上的構造策略
3.1 選擇數據邏輯結構的基本原則
3.1.1 充分利用可直接使用的信息
3.1.2 不記錄無用的信息
3.2 選擇數據存儲結構的基本方法
3.2.1 合理采用順序存儲結構
3.2.2 必要時采用鏈式存儲結構
3.3 科學組合多種數據結構
3.3.1 數據結構的並聯
3.3.2 數據結構的嵌套
本章小結
第4章 數據統計上的二分策略
4.1 利用線段樹統計數據
4.1.1 利用線段樹解決一維數據序列的統計問題
4.1.2 利用線段樹解決二維數據區的統計問題
4.2 基於數組統計方法
4.2.1 利用樹狀數組解決動態統計子序列和問題
4.2.2 采用倍增算法求解RMQ問題
4.3 在靜態二叉排序樹上統計數據
4.3.1 建立靜態二叉排序樹
4.3.2 在靜態二叉排序樹上進行統計
4.3.3 靜態二叉排序樹的應用
4.4 在虛二叉樹上統計數據
本章小結
第5章 動態規划上的優化策略
5.1 減少狀態總數的基本策略
5.1.1 改進狀態表示
5.1.2 選擇適當的DP方向
5.2 減少每個狀態決策數的基本策略
5.2.1 利用最優決策的單調性
5.2.2 剪枝優化
5.2.3 合理組織狀態
5.2.4 細化狀態轉移
5.3 減少狀態轉移時間的基本策略
5.3.1 減少決策時間
5.3.2 減少計算遞推式的時間
5.4 應對連通性問題的DP策略——基於狀態壓縮的插頭DP
5.4.1 插頭DP的一般模式
5.4.2 用於簡單路徑問題上的插頭DP
5.4.3 用於棋盤染色問題上的插頭DP
5.4.4 插頭DP中的剪枝優化
本章小結
第6章 計算幾何上的應對策略
6.1 用於求解距離問題的模擬退火算法
6.1.1 模擬退火算法的由來
6.1.2 模擬退火算法的實現
6.1.3 模擬退火算法的應用范例
6.2 用於求解凸性函數極值問題的三分法
6.2.1 三分法的基本思想
6.2.2 三分法的應用范例
6.3 使用剖分優化應對復合屬性的幾何圖形
6.3.1 圓重合其他幾何圖形時的剖分策略
6.3.2 使用三角剖分思想計算幾何圖形面積
6.3.3 使用梯形剖分計算多邊形面積
6.3.4 利用矩形切割思想進行幾何計算和數據統計
6.4 利用極大化思想解決最大子矩形問題
6.4.1 與極大化思想有關的概念
6.4.2 尋找最大子矩形的兩種常用算法
6.4.3 最大子矩形問題的推廣
6.4.4 利用極大化思想解決最大子矩形問題的范例
6.5 在求解綜合性、擴展性幾何問題中合理組合基本幾何運算
6.5.1 在復雜的綜合性試題中合理組合基本幾何運算
6.5.2 在空間幾何計算中合理組合基本幾何運算
本章小結
第7章 博弈類問題的應對策略
7.1 利用動態博弈思想判斷輸贏
7.2 基礎性博弈中的對抗策略
7.2.1 巴什博弈
7.2.2 威佐夫博弈
7.2.3 尼姆博弈
7.3 基礎性博弈擴展形式中的對抗策略
7.3.1 巴什博弈的擴展——k倍動態減法游戲
7.3.2 尼姆博弈的四種擴展形式
7.4 使用SG函數應對一類組合游戲
7.4.1 SG-組合游戲問題的特殊性質
7.4.2 翻硬幣游戲
7.4.3 多圖游戲
7.5 使用數學工具surreal number應對不平等的組合游戲
7.5.1 數學工具surreal number
7.5.2 surreal number在組合游戲上的應用
本章小結