【正文】 輸 出應(yīng)當為： 0 1 2 3 4 5 6 7 8 9 0 9 0 1 2 4 5 6 7 8 9 0 1 6 7 8 9 0 1 2 3 4 8 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 請按任意鍵繼續(xù) . . . 讀者對照輸出可體會各函數(shù)的用法 【 list 類】 lsit 順序容器提供在容器中任意位置進行插入與刪除操作的有效實現(xiàn)方法。j++) couttw[i][j] 。 for(i=0。i5。 for(i=0。 ((),())。 for(i=0。i()。i++) coutsz[i] 。i10。 7 typedef vectorvectorint Array2D。 Vector 類常用的接口如下： 函數(shù)名 返回值 參數(shù) 功能 at 元素的引用 要取元素的位置 (int pos) 如果該位置元素存在則返回它的引用，否則進行一場處理 back 元素的引用 無 返回容器最后一個元素的引用，如果容器為空則出錯 begin 迭代器 無 取得元素的首迭代器 end 迭代器 無 取得元素的尾迭代器 clear 無 無 將容器清空 empty bool值 無 如果容器為空則 為真，否則為假 erase 迭代器 要刪除元素的迭代器 要刪除容器段的首尾迭代器 第一個版本刪除指定的元素 第二個版本刪除指定的容器段 不存在則出錯 front 元素的引用 無 返回首元素的引用，為空則出錯 insert 無 iterator it, const Tamp。例如要分別建立坐標的一維和二維數(shù)組： 6 include utility include vector using namespace std。 Vector 類元素最多一般可以為 1073741823 個。 C++標準模板庫提供三種順序容器： vector、 list 和 deque。 return 0。 int main() { POINT p1,p2。 這樣在下邊的代碼中我們就可以使用 POINT 這個結(jié)構(gòu)了。 pr)。 pair(const Tamp。 請看下面 STL 中的一段代碼： templateclass T, class U struct pair { typedef T first_type。pit!=()。i10。例如： include iostream include vector using namespace std。例如一個數(shù)組 int array[N]的迭代器可以為 int *p＝ array，現(xiàn)在 p 指向的是數(shù)組的首地址，我們可以對 p 進行加減操作來改變它所指的元素，如： p++是將指針 p 的值直接加上整形的字長而指向數(shù)組的下一個元素。此外，新舊文件的文件名不盡相同，例如 cmath，一般情況下名字不同時在原文件名前加 c 即可。 現(xiàn)在大多數(shù)編譯器都包含新舊兩個版本的頭文件，舊版本的頭文件是以 .h 為擴展名的，新版本的頭文件則不帶擴展名，兩者都可以用記事本打開來查看。 STL都是以源碼的形式給出 的，各個編譯器有不同的版本。 ? 容器 (container)－用來儲存其他物件 ? 迭代器 (iterator)－好比傳統(tǒng) C 語言的指針，可藉之來處理容器對象 ? 算法 (algorithm)－算法通過迭代器來操作容器對象 ? 適配器 (adaptor)－利用基礎(chǔ)容器對象，加以包裝，改變其接口，以適應(yīng)另一種需求 ? 函數(shù)對象 (function object)－為 STL 中較低階的對象，用來代替?zhèn)鹘y(tǒng)的 函數(shù)指針(function pointer) STL 的簡單結(jié)構(gòu)可用下圖表示：其中容器類表示通常意義上的數(shù) 據(jù)結(jié)構(gòu)，和算法通過迭代器連接起來，做到上面的兩點。 “The Art of Computer Programming”書中強調(diào) 算法 + 數(shù)據(jù)結(jié)構(gòu) = 程序 在過去，一般來說程序皆由算法加數(shù)據(jù)結(jié)構(gòu)，互相配合、一起工作，完成程序的功能。 STL 的一個重大成就在于，它提供了相當多的有用算法。 ) Linux Redhat : g++ 。 C++ Builder 。 在設(shè)計算法和編寫程序的過程中，我們要經(jīng)常用到鏈表、堆棧、隊列、優(yōu)先隊列、集合等基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，如果每次我們都自己手動建立這些數(shù)據(jù)結(jié)構(gòu)的類，那將使我們的效率大打折扣， STL 中包含了一個標準化的模板化對象容器庫，有了它我們能很方便的實現(xiàn)上述數(shù)據(jù)結(jié)構(gòu)，并且能得到更高質(zhì)量的程序。 這里我們只是簡單的向大家介紹 STL 庫中的各種資源的使用，通過一些短小的程序，希望能達到讓大家在一定程度上掌握 STL的基本知識，并能通過使用 STL 庫開發(fā)出簡潔高效的 C++代碼，這是我們編寫這一參考資料的主要目的。它最初是惠普實驗室（ HewlettPackard Labs）開發(fā)成功的。 本次修訂版有 阮政、王洪剛和陳昊參與修訂，重寫了STL 和組合數(shù)學(xué)部分，并增加了算法優(yōu)化專題。 計算機科學(xué)與技術(shù)系 修訂版 ICPC培訓(xùn)講義 算法與程序設(shè)計 I C P C 培訓(xùn)講義 算法與程序設(shè)計 ? 計算機科學(xué)與技術(shù)系 合肥工業(yè)大學(xué) 2020 年 3 月 修訂版 ii 前 言 ACM／ ICPC 是由國際計算機學(xué)界著名的 ACM 學(xué)會主辦，世界上公認的規(guī)模最大、水平最高的國際大學(xué)生程序設(shè)計競賽，它充分地展示了大學(xué)生分析問題和解決問題的能力，這項比賽，歷來為國際知名大學(xué)所重視，競賽分區(qū)域預(yù)賽和國際決賽兩個階段進行，各賽區(qū)預(yù)賽的第一名獲參加決賽的資格 （ 第二名 視情況而定） ?，F(xiàn)在大家使用的 后由 許嵩罡 負責(zé)整理并增加了動態(tài)規(guī)劃部分。LYA 原理及其應(yīng)用 ...................................................................................................................... 86 第六章 專題解析 ........................................................................................................................................ 93 一、模 擬 ................................................................................................................................................ 93 1. 模擬游戲類 ...................................................................................................................................... 93 2. 模擬編碼類 ...................................................................................................................................... 97 二、 密 碼 ........................................................................................................................................... 102 1. Problem A ........................................................................................................................................ 102 2. Problem B ........................................................................................................................................ 106 3. Problem C ........................................................................................................................................ 109 三、字符串處理 ..................................................................................................................................... 113 1. PROBLEM A.................................................................................................................................... 113 2. PROBLEM B.................................................................................................................................... 114 3. 字符串處理的應(yīng)用實例 ................................................................................................................ 115 四、算法的優(yōu) 化 ..................................................................................................................................... 121 （一）算法優(yōu)化的基本思想 ............................................................................................................ 121 （二）搜索的優(yōu)化 ............................................................................................................................. 125 （三）動態(tài)規(guī)劃的優(yōu)化 ..................................................................................................................... 129 （四）一些特殊的數(shù)據(jù)結(jié)構(gòu) ............................................................................................................ 134 附錄 課程實驗 .......................................................................................................................................... 141 實驗一 STL的熟悉與使用 ................................................................................................................ 141 實驗二 搜索算法的實現(xiàn) ................................................................................................................... 142 實驗三 計算幾何算法的實現(xiàn) .......................................................................................................... 142 實驗四