程序設計解題策略:大學程序設計課程與競賽訓練教材 程序设计解题策略:大学程序设计课程与竞赛训练教材

<內容簡介>

《程序設計解題策略:大學程序設計課程與競賽訓練教材》在數據結構和算法設計的基礎上，從樹型數據關系、圖型數據關系、數據關系的構造策略、數據統計的二分策略、動態規劃的優化策略、計算幾何的應對策略及博弈問題的應對策略七個方面，具體介紹了49種解題策略和重要算法。全書結合國內外多年程序設計競賽的經典例題，精選出100道實驗範例，每道實驗範例均註明瞭試題來源和在線測試網址，幫助讀者更加深入地瞭解和掌握編程解題策略。另外，所有試題的原版描述和大部分試題的測試數據可登錄華章網站下載。

<章節目錄>

前言
第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在組合遊戲上的應用
本章小結