世界大學生程序設計競賽<ACM\ICPC>高級教程(第2冊程序設計中常用的解題策略)(精) 世界大学生程序设计竞赛(ACM/ICPC)高级教程(第2册):程序设计中常用的解题策略

<內容簡介>

    吳文虎、王建德編著的《世界大學生程序設計競賽高級教程(第2冊程序設計中常用的解題策略)》是針對世界大學生程序設計競賽(ACM?ICPC)而編寫的第二本參考書。
    ACM?ICPC是大學生智力與計算機解題能力的競賽，是世界公認的最具影響力的、規模最大的國際頂級賽事，被稱為大學生的信息學奧林匹克。
    第一冊主要介紹程序設計中解題的常用思維方式。《世界大學生程序設計競賽高級教程(第2冊程序設計中常用的解題策略)》是第一冊的繼續，只是換了一個角度，分4方面介紹解題策略：數據關繫上的構造策略；數據統計上的二分策略；動態規劃中的優化策略；計算幾何題的應對策略。
    本書面向參加世界大學生程序設計競賽(ACM?ICPC)的高等院校學生，也可作為程序設計愛好者的參考用書。

<目錄>

第7章  利用樹狀結構解題的策略
7.1  解決樹的最大一最小劃分問題的一般方法
7.2  利用最小生成樹及其擴展形式解題
7.2.1  利用最小生成樹解題
7.2.2  最小k度限制生成樹的思想和應用
7.2.3  次小生成樹的思想和應用
7.3  利用線段樹解決區間計算問題
7.3.1  線段樹的基本概念
7.3.2  線段樹的基本操作
7.3.3  應用線段樹解題
7.4  利用伸展樹優化動態集合的操作
7.4.1  伸展樹的基本操作
7.4.2  伸展樹的效率分析
7.4.3  應用伸展樹解題
7.5  利用左偏樹實現優先隊列的合並
7.5.1  左偏樹的定義和性質
7.5.2  左偏樹的操作
7.5.3  應用左偏樹解題
7.6  利用“跳躍表”替代樹結構
7.6.1  跳躍表的概況
7.6.2  跳躍表的基本操作
7.6.3  跳躍表的效率分析
7.6.4  應用跳躍表解題
小結
第8章  利用圖形(網狀)結構解題的策略
8.1  利用網絡流算法解題
8.1.1  網絡與流的概念
8.1.2  最大流算法的核心──增廣路徑
8.1.3  通過求最大流計算最小割切
8.1.4  求容量有上下界的最大流問題
8.1.5  網絡流的應用
8.2  利用圖的匹配算法解題
8.2.1  匹配的基本概念
8.2.2  計算二分圖匹配的方法
8.2.3  利用一一對應的匹配性質轉化問題
8.2.4  優化匹配算法
8.3  利用“分層圖思想”解題
8.3.1  利用“分層圖思想”構建圖論模型
8.3.2  利用“分層圖思想”優化算法
8.4  利用平面圖性質解題
8.4.1  平面圖的概念
8.4.2  平面圖的應用實例
8.5  正確選擇圖論模型，優化圖的運算
8.5.1  正確選擇圖論模型
8.5.2  在充分挖掘和利用圖論模型性質的基礎上優化算法
小結
第9章  數據關繫上的構造策略
9.1  選擇數據邏輯結構的基本原則
9.1.1  充分利用“可直接使用”的信息
9.1.2  不記錄“無用”信息
9.2  選擇數據存儲結構的基本方法
9.2.1  合理採用順序存儲結構
9.2.2  必要時採用鏈式存儲結構
9.3  科學組合多種數據結構
小結
第10章  數據統計上的二分策略
10.1  利用線段樹統計數據
10.2  一種解決動態統計的靜態方法
10.2.1  討論一維序列的求和問題
10.2.2  將一維序列的求和問題推廣至二維
10.3  在靜態二叉排序樹上統計數據
10.3.1  建立靜態二叉排序樹
10.3.2  在靜態二叉排序樹上進行統計
10.3.3  靜態二叉排序樹的應用
10.4  在虛二叉樹上統計數據
小結
第11章  動態規劃上的優化策略
11.1  減少狀態總數的基本策略
11.1.1  改進狀態表示
11.1.2  選擇適當的規劃方向
11.2  減少每個狀態決策數的基本策略
11.2.1  利用最優決策的單調性
11.2.2  優化決策量
11.2.3  合理組織狀態
11.2.4  細化狀態轉移
11.3  減少狀態轉移時間的基本策略
11.3.1  減少決策時間
11.3.2  減少計算遞推式的時間
小結
第12章  計算幾何上的應對策略
12.1  應對純粹計算題的策略探討
12.1.1  利用二重二叉樹計算長方體的體積並
12.1.2  利用多維線段樹和矩形切割思想解決平面統計或空間統計問題
12.1.3  利用極大化思想解決最大子矩形問題
12.1.4  利用半平面交的算法計算凸多邊形
12.2  應對存在性問題的策略探討
12.2.1  直接通過幾何計算求解
12.2.2  轉換幾何模型求解
12.3  應對最佳值問題的策略探討
12.3.1  採用高效的幾何模型
12.3.2  採用極限法
12.3.3  採用逼近最佳解的近似算法
小結