《世界大學生程式設計競賽(ACM/ICPC)高級教程(第2冊):程式設計中常用的解題策略》面向參加世界大學生程式設計競賽（ACM/ICPC）的高等院校學生，也可以作為程式設計愛好者的參考用書。
基本介紹
- 作者：吳文虎 / 王建德
- ISBN：9787113146054
- 頁數：213
- 定價：48.00元
- 出版社：中國鐵道出版社
- 出版時間：2012-7
- 副標題：程式設計中常用的解題策略
內容介紹,作者簡介,目錄,文摘,
內容介紹
《世界大學生程式設計競賽(ACM/ICPC)高級教程(第2冊):程式設計中常用的解題策略》是針對世界大學生程式設計競賽（ACM/ICPC）而編寫的第二冊參考書。思維方式和解題策略是相互聯繫的。《世界大學生程式設計競賽(ACM/ICPC)高級教程(第2冊):程式設計中常用的解題策略》主要包括利用樹型結構解題的策略、利用圖形（網狀）結構解題的策略、數據關係上的構造策略、數據統計上的二分策略、動態規劃上的最佳化策略、計算幾何上的應對策略六個章節，旨在引導參賽學生學習並掌握正確的編程解題策略。
作者簡介
吳文虎教授1955年—1961年分別就讀於清華大學電機工程系及自動控制系，現為計算機系教授、博士生導師，主要研究方向包括語音識別及語言理解、語音合成、語音信號數字處理等。吳教授學術水平精湛、教學水平高超、教學經驗豐富，多年來用對學生無私的愛詮釋了最好的師恩師德。他於1997年獲清華大學優秀教學成果特等獎，1998年獲“全國優秀教師一等獎”，1999年獲國家科技部(原國家科委)授予的“全國科學普及先進個人獎”，1999年榮獲“首都勞動獎章”，2001年獲“全國師德先進個人獎”，2001年、2004年獲北京市高等教育教學優秀成果一等獎，2003年為本科生講授的“程式設計基礎”課程被列為教育部首批“國家級精品課”，2004年獲中國計算機學會頒發的“傑出貢獻獎”，2006年獲北京市高等教育教學名師獎；吳教授深受清華學子的愛戴，2003年獲清華大學教書育人獎，2005年獲清華大學第八屆“良師益友”榮譽稱號，2008年被清華大學學生會評為第一屆“我最喜愛的教師”。
從1989年至今，吳教授作為總教練和領隊，曾15次帶領中國隊參加國際信息學奧林匹克競賽，中國隊累計獲金牌51塊，屆屆名列前茅，2002年獲信息學奧林匹克國際委員會頒發的“特別貢獻獎”。1997年—2008年，吳教授連續13年指導清華大學的學生進入ACM世界大學生程式設計大賽總決賽，多次獲金牌、銀牌，並於2009年被大賽組委會授予“傑出教練獎”。
目錄
第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採用逼近最佳解的近似算法
小結
文摘
以上介紹了解決樹的最大一最小劃分問題的兩種解法，它們通過不同的方式思考問題，從而得到了不同的算法：解法1主要套用了問題轉化的思想，將原問題轉化為容易解決的問題，在給定下界時如何劃分最多子樹，如果可以解決這個問題，再通過二分查找下界求得原問題的解。這種算法的目光聚焦在結點的權值上，實現簡單，時間效率也不錯；而解法2則從另一個角度看問題，將目光集中在分割子樹的“割”上面，從而得到了一個複雜度不依賴於結點權值範圍的算法，其中起關鍵作用的是劃分問的“上方”關係，這種關係實際上是一種“序”的思想。利用“序”簡化問題、建立高效模型是程式設計中一種典型的最佳化方法。
雖然有了劃分樹的兩種解法，但我們並不滿足，還希望能夠將算法擴展一下，使它的適用範圍更加廣泛。
最佳化方法1：擴展權函式
首先來看一下權函式方面，由“每棵子樹的權被定義為子樹中所有結點的權之和”想到，對於一些其他的權函式，例如一棵子樹中結點權的最大值、子樹的直徑（子樹結點問路徑長度的最大值）等，這個算法是不是依然適用呢？我們發現，在解法2的證明過程中，只有②和③的證明用到了子樹的權函式，而通過更加深入觀察發現，證明中只是利用了權函式的一個性質：
權函式的性質：若T是T的任意一棵子樹，則必然有W（T）≥W（T），其中W（T）表示樹T中結點的權值和。
也就是說，只要權函式滿足這個條件，這個證明就是正確的，這個算法也就是可行的。於是，對於滿足特定條件的一類問題都找到了一種通用的解法，這也顯示出該算法很強的可擴展性。
有了對權函式的擴展，接下來便想到了對問題的擴展。例如，將樹劃分為k棵子樹，使得子樹的最大值最小，或是最大值與最小值的差最小等問題，我們是不是也可以用原算法求解呢？事實證明，單純地照搬是行不通的，因為算法有自身的特點，不可能適用於所有問題，但解決問題的思路卻是可以借鑑的。在解決與這一類型有關的問題時，或許可以改變移動的規則，或修改一下“上方”的定義，從而設計出符合題目特點的算法，這些問題可引起讀者思考。
最佳化方法2：用解法1最佳化解法2
在解法2中，初始狀態是將k—1個割放在與根相連的唯一一條邊上得到的，這樣做的好處是一定可以保證它在某個最優劃分的上方。可是由這個初始狀態移動到最優狀態往往需要很多步的移動，那么有沒有更好的初始狀態呢？我們想到了解法1，如果把下界設為樹中節點的權和/k—1，則劃分出來的子樹數一定不超過k—1，我們將剩餘的割都放在與根相連的那條邊上。可以證明，這個劃分狀態一定是在某個最優劃分的上方的，而由它達到最優狀態所需要移動的步數卻減少了。於是，只需要一個線性的預處理，便得到了一種更好的初始狀態。這樣，解法l和解法2便巧妙地結合在一起了。
