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