【正文】 計算機(jī)科學(xué)與技術(shù)系 修訂版 ICPC培訓(xùn)講義 算法與程序設(shè)計 I C P C 培訓(xùn)講義 算法與程序設(shè)計 ? 計算機(jī)科學(xué)與技術(shù)系 合肥工業(yè)大學(xué) 2020 年 3 月 修訂版 ii 前 言 ACM／ ICPC 是由國際計算機(jī)學(xué)界著名的 ACM 學(xué)會主辦，世界上公認(rèn)的規(guī)模最大、水平最高的國際大學(xué)生程序設(shè)計競賽，它充分地展示了大學(xué)生分析問題和解決問題的能力，這項比賽，歷來為國際知名大學(xué)所重視，競賽分區(qū)域預(yù)賽和國際決賽兩個階段進(jìn)行，各賽區(qū)預(yù)賽的第一名獲參加決賽的資格 （ 第二名 視情況而定） 。 中國的上海賽區(qū)于 1995 年度試舉辦，我校未參賽 ，從 1996 年正式舉辦起，我校每年都參加，并多次取得了較好的成績，為了更好的組織今后的比賽，我們于 2020 年開始著手編寫了這本講義，并希望作為資料保存下去，每年都得以增加更多更新的內(nèi)容。 本書是由徐本柱主持，其中 初始 由 李曉泉 、 萬郁香 、 許嵩罡 、 周晉 、 龐博 、 曹力 和沈揚(yáng)參與編寫的， 李曉泉 寫了 圖論及搜索 部分， 萬郁香 寫了 模擬類 部分， 許嵩罡 寫了 畫法幾何 部分， 周晉 寫了 密碼 部分，龐博 寫了 字符串處理 部分， 曹力 寫了 組合數(shù)學(xué) 部分， STL 簡介部分有許松罡和沈揚(yáng)合寫。現(xiàn)在大家使用的 后由 許嵩罡 負(fù)責(zé)整理并增加了動態(tài)規(guī)劃部分。 本次修訂版有 阮政、王洪剛和陳昊參與修訂，重寫了STL 和組合數(shù)學(xué)部分，并增加了算法優(yōu)化專題。 全書由徐本柱審校，由于時間匆忙，加上作者水平有限，錯誤難免，希望廣大同學(xué)批評指正。 徐本柱 2020 年 3 月 iii 目 錄 前 言 .......................................................................................................................................................... II 目 錄 ................................................................................................................................................. iii 第一章 STL 簡介 ........................................................................................................................................1 一、引 言 ..............................................................................................................................................1 二、 STL 組成結(jié)構(gòu) .....................................................................................................................................2 三、 STL 的應(yīng)用 ..........................................................................................................................................3 第二章 搜 索 ...................................................................................................................................... 28 一、 寬度優(yōu)先搜索 BFS ......................................................................................................................... 28 二、最小生成樹的形成和求解 (PRIM AND KRUSKAL) ......................................................................... 34 1. 最小生成樹的形成 .............................................................................................................................. 34 2． Kruskal 算法和 Prim 算法 ............................................................................................................. 37 三、深度優(yōu)先搜索 DFS ......................................................................................................................... 44 ..................................................................................................................................................... 44 ........................................................................................................................ 48 3. 邊的分類 ........................................................................................................................................... 50 第三章 計算幾何學(xué) .................................................................................................................................... 53 一、引 言 .............................................................................................................................................. 53 二、線段的性質(zhì)（ LINESEGMENT PROPERITIES） ................................................................................ 54 （ Cross Product） .................................................................................................................... 54 （ Determining Intersections） ................................................................................ 55 三、點(diǎn)集的性質(zhì) （ POINTSET PROPERITIES） ....................................................................................... 57 （ Finding the convex hull） ............................................................................................. 57 第四章 動態(tài)規(guī)劃 ........................................................................................................................................ 63 一、引言 —— 由一個問題引出的算法 ................................................................................................. 63 二、動態(tài)規(guī)劃的基本概念 ...................................................................................................................... 65 動態(tài)規(guī)劃的發(fā)展及研究內(nèi)容 ........................................................................................................ 65 多階段決策問題 ............................................................................................................................. 65 決策過程的分類 ............................................................................................................................. 66 三、動態(tài)規(guī)劃模型的基本要素 .............................................................................................................. 66 四、動態(tài)規(guī)劃的基本定理和基本方程 ................................................................................................. 68 五、動態(tài)規(guī)劃的適用條件 ...................................................................................................................... 69 最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)） ................................................................................................ 69 無后向性 ......................................................................................................................................... 70 子問題的重疊性 ............................................................................................................................. 70 六、動態(tài)規(guī)劃的基本思想 ...................................................................................................................... 71 七、動態(tài)規(guī)劃算法的基本步驟 .............................................................................................................. 72 八、 動態(tài)規(guī)劃的實(shí)例分析 ......................................