noip復習資料(提高組c版)精品名師資料

1、NOIP復習資料 （C+版） 主編 完成日期 葫蘆島市一高中李思洋 2012年8月27日 、八 前言 有一天，我整理了 NOIP 的筆記，并收集了一些經典算法。不過我感覺到筆記比較凌亂，并且有很多需要 修改和補充的內容，于是我又搜集一些資料，包括一些經典習題，在幾個月的時間內編寫出了 NOIP 復習資 料。 由于急于在假期之前打印出來并分發(fā)給同校同學（ 我們學校既沒有競賽班，又沒有懂競賽的老師。我們大 家都是自學黨 ）， NOIP 復習資料有很多的錯誤，還有一些想收錄而未收錄的內容。 在“減負”的背景下，暑期放了四十多天的假。于是我又有機會認真地修訂 NOIP 復習資料。 我編寫資料的目的有兩

2、個：總結我學過（ 包括沒學會 ）的算法、數據結構等知識；與同學共享 NOIP 知識， 同時使我和大家的 RP+ 。 大家要清醒地認識到， NOIP 復習資料頁數多，是因為程序代碼占了很大篇幅。這里的內容只是信息 學的皮毛。對于我們來說，未來學習的路還很漫長。 基本假設 作為自學黨，大家應該具有以下知識和能力： 能夠熟練地運用 C+ 語言編寫程序（ 或熟練地把 C+ 語言“翻譯”成 Pascal 語言 ）； 能夠閱讀代碼，理解代碼含義，并嘗試運用； 對各種算法和數據結構有一定了解，熟悉相關的概念； 學習了高中數學的算法、數列、計數原理，對初等數論有一些了解； 有較強的自學能力。 代碼約定 N、M

3、、MAX、INF 是事先定義好的常數（ 不會在代碼中再次定義，除非代碼是完整的程序）。 N、M、MAX 針對數據規(guī)模而言，比實際最大數據規(guī)模大； INF 針對取值而言，是一個非常大，但又與 int 的最大值有一定 差距的數，如 100000000 。 對于不同程序，數組下標的下限也是不同的，有的程序是0 ，有的程序是 1 。閱讀程序時要注意。 閱讀順序和方法 沒聽說過NOIP，或對NOIP不甚了解的同學，應該先閱讀附錄E,以加強對競賽的了解。 如果不能順利通過初賽，你就應該先補習初賽知識。這本 NOIP 復習資料總結的是復賽知識。 如果沒有學過 C+語言，應該先選擇一本 C+語言教材。一般情況

4、下，看到“面向對象編程”一章的前一 頁就足夠了（ NOIP 不用“面向對象編程”，更不用擺弄窗口對話框 ）。 附錄 G 介紹了一些書籍和網站。你應該選擇一本書，認真地學習。再選擇一個網站，作為練習的題庫。 第一單元對競賽中常用的操作和簡單的算法分析進行了總結，算作對C+語言的鞏固。同時，閱讀這一單 元之后，你應該選擇一個合適的C+代碼編輯器。 第二到第六單元介紹了競賽常用的算法。閱讀每一章時，應該先閱讀“小結”名曰“小結”，實際上 是“導讀”。 這五個單元除了經典習題，還有某些思想和算法的具體實現(xiàn)方法。這些信息可能在明處，也可能在暗處， 閱讀時要注意挖掘和體會。如果有時間，應該在不看解析和代碼

5、的前提下獨立完成這些題。 第七單元是第六單元的一個部分，由于它的內容來自背包九講，所以單獨放在一個單元。 從第八單元開始，到第十三單元，基本上就沒有習題了。換句話說，該“背課文”了。 第八單元介紹了常用的排序算法。你可以有選擇地學習，但一定要掌握“STL 算法”和“快速排序”。 第九單元介紹了基本數據結構，你一定要掌握第九單元前五小節(jié)的內容（本單元也有應該優(yōu)先閱讀的“小 結” ）。有余力的話，第六小節(jié)的并查集也應該掌握。 第十單元介紹了與查找、檢索有關的數據結構和算法。你也可以有選擇地學習。 第十一單元與數學有關。數學對于信息學來說具有舉足輕重的地位。標有“！”的應該背下來，至于其他 內容，如

6、果出題，你應該能把它解決。 第十二單元仍與數學有關。 第十三單元是圖論。學習時要先閱讀“小結”，把概念弄清楚。之后要掌握圖的實現(xiàn)方法。接下來要掌握 一些經典圖論算法： Kruskal 算法、 Dijkstra算法、 SPFA、 Floyd 算法、拓撲排序。 附錄 F 總結了 2004 年以來 NOIP 考察的知識點，可以作為選擇性學習的參考。 在學習算法和數據結構的同時，應該閱讀和學習附錄 A。 如果你還有余力，你應該學習第十四單元。第十四單元的內容不是必須要掌握的，但是一旦學會，可以發(fā) 揮 C+ 語言的優(yōu)勢，降低編程復雜度。 臨近競賽時，應該閱讀附錄B和附錄C,以增加經驗，減少失誤。 面臨的

7、問題 1. 這是復賽復習資料需要有人能用心總結、整理初賽的知識，就像這份資料一樣。 2. 潛在的問題還是相當多的，只是時間不夠長，問題尚未暴露。 3. 部分代碼缺少解說，或解說混亂。 4. 個人語文水平較差，資料也是如此。 5. 沒有對應的 Pascal 語言版本。 如果有人能為P黨寫一個Pascal版的STL，他的RP 一定會爆增！ 6. 希望有人能用LteX整理資料，并以自由文檔形式發(fā)布。 最后，歡迎大家以交流、分享和提高為目的修改、復制、分發(fā)本資料，同時歡迎大家將資料翻譯 成 Pascal 語言版供更多 OIer 閱讀！ 謝謝大家的支持！ 葫蘆島市一高中 李思洋 2012 年 8 月 2

8、7 日 標題上的符號： 1. !:表示讀者應該熟練掌握這些內容，并且在競賽時能很快地寫出來。換句話說就是應該背下來。 2. * :表示內容在 NOIP中很少涉及，或者不完全適合 3. # :表示代碼存在未更正的錯誤，或算法本身存在缺陷。 刖言2 目錄I 第一單兀 C+語言基礎1 1.1 程序結構 1 1.2 數據類型 4 1.3 運算符 6 1.4 函數 8 1.5 輸入和輸出！ 9 1.6 其他常用操作！ 10 1.7 字符串操作！ 13 1.8 文件操作！ 13 1.9 簡單的算法分析和優(yōu)化 14 1.10 代碼編輯器 16 第二單元基礎算法17 2.1 經典枚舉問題 17 2.2 火柴棒

9、等式 18 2.3 梵塔問題 19 2.4 斐波那契數列 19 2.5 常見的遞推關系！ 20 2.6 選擇客棧 22 2.7 2k進制數 23 2.8 Healthy Holstei ns 24 2.9 小結 25 第三單元搜索27 3.1 N皇后問題 27 3.2 走迷宮 29 3.3 8數碼問題 31 3.4 埃及分數 34 3.5 Mayan 游戲 36 3.6 預處理和優(yōu)化 40 3.7 代碼模板 41 3.8 搜索題的一些調試技巧 43 3.9 小結 44 第四單元貪心算法46 4.1 裝載問題 46 4.2 區(qū)間問題 46 4.3 刪數問題 47 4.4 工序問題 47 4.5

10、種樹問題 47 4.6 馬的哈密爾頓鏈 47 4.7 三值的排序 49 4.8 田忌賽馬 50 4.9 小結 50 NOIP的難度。 第五單元分治算法51 5.1 一元三次方程求解 51 5.2 快速幕51 5.3 排序51 5.4 最長非降子序列53 5.5 循環(huán)賽日程表問題 53 5.6 棋盤覆蓋54 5.7 刪除多余括號55 5.8 聰明的質監(jiān)員 56 5.9 模板58 5.10 小結59 第六單元動態(tài)規(guī)劃60 6.1 導例：數字三角形 60 6.2 區(qū)間問題：石子合并 63 6.3 坐標問題65 6.4 背包問題67 6.5 編號問題67 6.6 遞歸結構問題 68 6.7 DAG上的

11、最短路徑 71 6.8 樹形動態(tài)規(guī)劃* 72 6.9 狀態(tài)壓縮類問題：過河 74 6.10 Bito nic旅行76 6.11 小結77 第七單元背包專題78 7.1 部分背包問題 78 7.2 0/1背包問題! 78 7.3 完全背包問題 79 7.4 多重背包問題 79 7.5 二維費用的背包問題 80 7.6 分組的背包問題81 7.7 有依賴的背包問題81 7.8 泛化物品81 7.9 混合背包問題 82 7.10 特殊要求82 7.11 背包問題的搜索解法 83 7.12 子集和問題84 第八單元排序算法85 8.1 常用排序算法 85 8.2 簡單排序算法 87 8.3 線性時間排

12、序 88 8.4 使用二叉樹的排序算法* 89 8.5 小結90 第九單元基本數據結構91 9.1 線性表（順序結構） 91 9.2 線性表（鏈式結構） 91 9.3 棧 93 9.4 隊列 94 9.5 二叉樹 95 9.6 并查集！ 99 9.7 小結 102 第十單元查找與檢索104 10.1 順序查找 104 10.2 二分查找！ 104 10.3 查找第k小元素！ 105 10.4 二叉排序樹 106 10.5 堆和優(yōu)先隊列* 108 10.6 哈夫曼（Huffman ）樹110 10.7 哈希（Hash ）表 111 第十一單元數學基礎116 11.1 組合數學 116 11.2

13、組合數的計算！ 117 11.3 排列和組合的產生（無重集元素） ！ 117 11.4 排列和組合的產生（有重集元素） .1 20 11.5 秦九韶算法 122 11.6 進制轉換（正整數） 123 11.7 高精度算法（壓位存儲）！ .123 11.8 快速幕! 128 11.9 表達式求值 129 11.10 解線性方程組* 133 第十二單元數論算法135 12.1 同余的性質！ 135 12.2 最大公約數、最小公倍數 ! .135 12.3 解不定方程 ax + by = c!* 1 35 12.4 同余問題* 136 12.5 素數和素數表 136 12.6 分解質因數 137 第

14、十三單元圖與圖論算法139 13.1 圖的實現(xiàn) 139 13.2 圖的遍歷 141 13.3 連通性問題 142 13.4 歐拉回路鄰接矩陣 146 13.5 最小生成樹（MST） 147 13.6 單源最短路問題（SSSP問題）.148 13.7 每兩點間最短路問題（APSP問題）!152 13.8 拓撲排序 152 13.9 關鍵路徑 155 13.10 二分圖初步 157 13.11 小結 160 第十四單元STL簡介 164 14.1 STL 概述 164 14.2 常用容器 164 14.3 容器適配器 170 14.4 常用算法 171 14.5 迭代器 175 14.6 示例：合

15、并果子 175 附錄A 思想和技巧. 177 A.1 時間/空間權衡. 177 A.2 試驗、猜想及歸納 177 A.3 模型化 .177 A.4 隨機化* .178 A.5 動態(tài)化靜態(tài) 178 A.6 前序和! .179 A.7 狀態(tài)壓縮* .180 A.8 抽樣測試法* 182 A.9 離散化* .183 A.10 Flood Fill* 184 附錄B 調試 185 B.1 常見錯誤類型. 185 B.2 調試過程 .185 B.3 調試功能 .185 B.4 符號DEBUG的應用 186 B.5 代碼審查表 186 B.6 故障檢查表 187 B.7 命令行和批處理* 188 附錄C

16、競賽經驗和教訓 192 C.1 賽前兩星期 192 C.2 賽前30分鐘 192 C.3 解題表 .193 C.4 測試數據 .195 C.5 父卷刖5分鐘. 196 C.6 避免偶然錯誤. 196 C.7 騙分 .197 附錄D 學習建議 198 D.1 學習方法 .198 D.2 學習能力 .198 D.3 關于清北學堂. 198 附錄E 競賽簡介 199 E.1 從 NOIP 到 101 . 199 E.2 NOIP簡介 .199 E.3 常用語 .201 E.4 第一次參加復賽 202 附錄F NOIP復賽知識點分布. 204 附錄G 資料推薦 205 G.1 書籍 .205 G.2

17、網站 .205 參考文獻 206 計算機專業(yè)是朝陽還是夕陽？. 207 杜子德在 CCF NOI2012 開幕式上的講話 209 多數奧賽金牌得主為何難成大器.210 第一單元 1.1 C+語言基礎 程序結構 （1）程序框架 注釋：注釋有兩種，一種是“ / ”，另一種是“ /*/ ”?！啊北仨殕为毞胖靡恍?，或代碼所在行 的后面；而“ /* ”、“ */ ”成對存在，可以插入到代碼的任意位置。 引用頭文件：在代碼開頭寫“ #inelude ”。如果想引用自己的頭文件，需要把尖括號（表 示只從系統(tǒng)目錄搜索頭文件 ）換成雙引號（表示先從epp所在文件夾搜索，然后再到系統(tǒng)文件夾搜索）。 命名空間：很多

18、 C+的東西都要引用 std命名空間，所以代碼中會有“ using namespace std;”。 mai n（）:所有程序都要從 mai n（）開始。 在所有的算法競賽中，main（）的返回值必須是0,否則視為程序異常結束，得分為 0分。 語句和語句塊： 1. 語句：一般情況下，一條語句要用一個分號“；”結束。為了美觀和可讀性，可以把一條語句擴展成 幾行，也可以把多個語句寫到同一行上。 2. 語句塊：用“ ”和“ ”包圍的代碼是語句塊。無論里面有多少代碼，在原則上，語句塊所在的整體 都視為一條語句。 （2）選擇結構 1. （語 if語句：if表示判斷。如果條件為真，就執(zhí)行接在if后的語句（

19、語句塊），否則執(zhí)行else后的語句 句塊）。如果沒有else，就直接跳過。if有以下幾種格式： if ( 條件） 語句或語句塊 / 如果條件成立，就執(zhí)行if 后面的語句或語句塊。 if ( 條件） 語句或語句塊 / 如果條件成立，就執(zhí)行if 后面的A，否則執(zhí)行B。 else 語句或語句塊 條件1） 語句或語句塊 else if （ 條件 2） 語句或語句塊B if ( / 實際上，這是if語句內的 if語句，即if的嵌套。所以else和if中間要有空格。 else 語句或語句塊N 2. switch 語句：switch表示選擇。它根據條件的不同取值來執(zhí)行不同的語句。格式如下: switch （

20、 表達式） case 值 1: 代碼段A break; case 值 2: 代碼段B break; default: 代碼段N break; ； 如果表達式的值是值 1，就執(zhí)行代碼段 A;如果表達式的值是值 2，就執(zhí)行代碼段B否則執(zhí)行代碼段N。 default一部分可以省略。 如果不使用break，那么緊隨其后的 case部分代碼也會被執(zhí)行，直到遇到break 或switch 語句 結束為止！ switch結尾要有一個分號。 3. if、switch都可以嵌套使用。 【問題描述】輸入一個日期，判斷它所在年份是否為閏年，并輸出所在月份的天數。閏年的判斷方法：四年一 閏，百年不閏，四百年又閏。 i

21、nt year,m on th,day; bool b=false; cin year mon thday; /判斷是否為閏年 if (n %400=0) b=true; else if (n %100!=0 if (b) couty是閏年。e ndl; else couty不是閏年。e ndl; /判斷所在月份的天數 switch (mon th) case 1: case 3: case 5: case 7: case 8: case 10: case 12: cout這個月有 31 天。endl; break; case 4: case 6: case 9: case 11: cout這

22、個月有 30 天。endl; break; case 2: cout 這個月有(b ? 29 : 28)天。endl; break; ; (3) 循環(huán)結構 1. while 語句：如果條件成立，就繼續(xù)循環(huán)，直到條件不成立為止。格式如下: while (條件) 循環(huán)體(語句或語句塊) 2. dowhile 語句：如果條件成立，就繼續(xù)循環(huán)，直到條件不成立為止。它與while 的最大區(qū)別在于，do while循環(huán)中的語句會被執(zhí)行至少一次，而while中的語句可能一次都沒有被執(zhí)行。格式如下： do 循環(huán)體 while ( 條件);II注意分號 4. for語句：for分四部分，有初始條件、繼續(xù)循環(huán)的條

23、件、狀態(tài)轉移的條件和循環(huán)體。格式如下： for (初始條件；繼續(xù)循環(huán)的條件；狀態(tài)轉移的條件) 循環(huán)體 轉換成while 循環(huán)，即： 初始條件 while ( 繼續(xù)循環(huán)的條件) 循環(huán)體 狀態(tài)轉移 for后三個條件不是必需的，可以省略不寫，但分號必須保留。 5. 在循環(huán)語句內部使用break，可以跳出循環(huán)；使用continue，可以忽略它后面的代碼，馬上進入下一輪 循環(huán)。 注意，這兩個語句只對它所在的一層循環(huán)有效。 6. 寫for循環(huán)時，一定要注意： 不要把計數器的字母打錯，尤其是在復制/粘貼一段代碼的時候。 根據算法要明確不等號是“”，還是“ =”。 逆序循環(huán)時，不要把自減“-”寫成自增“ +

24、”！ 【問題描述】輸入 n,輸出n! (n! = 1 x 2 x 3 x4 xx n)。結果保證小于long long的范圍。當輸入值 為負數時結束程序。 int n; long long r=1; cinn; while (n -1) r=1; for (in t i=1; i=n; i+) r*=i; cout n ! = re ndl; cinn; goto 語句 goto語句用于無條件跳轉。要想跳轉，首先要定義標簽(在代碼開頭的一段標識符，后面緊跟冒號) 然后才能goto那個標簽。 很多教程不提倡使用無條件跳轉，因為它破壞了程序結構，還容易給代碼閱讀者帶來麻煩。不過，這不代 表goto

25、沒有使用價值。goto的一個用途是跳出多層循環(huán)： for (int i=0; i9; i+) for (int j=0; j9; j+) for (int k=0; k9; k+) if (滿足某種條件)goto _exited; _exited: C 與C+的區(qū)別 C+語言是以C語言為基礎開發(fā)出來的，C語言的大多數內容被保留了下來。在信息學競賽領域，很多情 況下C和C+可以互相轉化，甚至不用對代碼進行任何修改。 下面是信息學競賽領域中C和C+的重要區(qū)別： C+支持用流輸入輸出，而 C只能用seanf和printf再見了， d! C+非常支持面向對象編程，而C已經“ out ”了。 資料中的“

26、高精度算法”就只能用C+完成，因為在struct內定義了成員函數。 C+可以用更強大的stri ng類處理字符串，而不必擔心發(fā)生某些低級錯誤。 C+有強大的STL，而C沒有(有一個小小的qsort 和bsearch算是補償了)。 STL是很多人從C轉到C+的重要原因。 C的頭文件名仍然可以用在C+中，不過可能會收到警報一一應該去掉“.h ”，前面再加一個“ c”。 如 應該改成 。 C程序運行速度稍優(yōu)于 C+。不過也沒快多少。 總之，C能做的一切事情，C+也能做；C+能做的一切事情，C不一定能做。 1.2 數據類型 (1) 基本數據類型 名稱 占用空間 別名 數據范圍 int 4 sig ne

27、d, sig ned int. Ion g, l ong int -2,147,483,6482,147,483,647 un sig ned int 4 un sig ned, un sig ned long,un sig ned long int 0 4,294,967,295 char 1 char -128 127 un sig ned char 1 un sig ned char 0 255 short 2 short int, sig ned short int -32,76832,767 un sig ned short 2 un sig ned short int 0 65,5

28、35 long long 8 sig ned long long 9,223,372,036,854,775,808 9,223,372,036,854,775,807 un sig nedlong long 8 0 18,446,744,073,709,551,615 bool 1 true 或 false char 1 -128 127 sig ned char 1 -128 127 一般都使用有符號整數，除非范圍不夠大，或者你確定你的減法運算不會岀現(xiàn)小數減大數”。 一般來說，使用int、long long更保險一些，除非內存不夠用。 不要使用“ _int64 ”！它是Visual C+特

29、有的關鍵字。 假如a是long long 類型，把超過231的值賦給它時要使用字面值LL ( ULL): a=123456789012345 LL un sig ned char 1 0 255 float 4 3.4E +/- 38 （7位有效數字） double 8 long double 1.7E +/- 308 （15位有效數字） （2）變量與常量 1. 定義變量：“變量類型標識符”，如“ int i; ”定義了一個名字為i的整型變量。 注意，此時i并未初始化，所以i的值是不確定的。 2. 定義常量：“ con st變量類型 標識符=初始值”，如：const int N=90; 3.

30、合法的標識符： 標識符不能和關鍵字（在IDE中會變色的詞語）相同。 標識符只能包括字母、數字和下劃線“_”，并且開頭只能是字母或下劃線。 標識符必須先定義后使用。 在同一作用域內，標識符不能重復定義（即使在不同作用域內也不應重復，否則容易產生歧義）。 C+區(qū)分大小寫。所以 A和a是兩個不同的標識符。 數組 1. 定義一個一維數組：int a10; 這個數組一共10個元素，下標分別為09。訪問某個元素時，直接用 a加方括號，如a5。 2. 定義一個二維數組：int b53; 這個數組一共 5 X 3 = 15 個元素，分別是 b00、b01、b02、b10b42。 訪問某個元素時要用兩個方括號，

31、如b21。 多維數組的定義和使用方法與此類似。 3. 數組名和元素的尋址：以上面的a、b為例 數組名是一個指針，指向整個數組第一個元素所在的地址。如a就是 定義多個指針時，每個字母的前面都要有“* ”。 注意，如果p沒有被初始化，它就會指向一個未知的內存空間，而錯誤地操作內存會導致程序崩潰! 4. 指針使用實例: *p； a = 0, b = 1; int c = 1,2,3,4,5,6,7,8,9,10; /定義一個指針 / 讓p指向a / 相當于a=3 / 相當于a=b，此時a等于1 /非法操作，左邊是int *，右邊是int，類型不匹配。 /讓p指向b，從此p和a沒關系了 /讓p指向c6

32、，p和b又沒關系了 /輸出p指向的變量的值，即c6 / 現(xiàn)在p指向了 c7; /表示p沒有指向任何變量 /由于NULL（ 0）是一段無意義的地址，所以程序極有可能崩潰。 為了不在競賽中把自己搞暈，請回避指針，對其敬而遠之。 引用 通俗地講，引用是某個變量的別名。下面定義了一個叫p的引用，它實際上是 f02。無論是改變p 的值，還是改變f02的值，結果都是一樣的。 int 使用引用的好處是，在函數的形參中定義引用類型，可以直接修改變量的值，而不用考慮“ ; 變量可以定義成上面的pack類型：pack p;/ 不必寫成struct pack p; 訪問pack的成員時，用“.”運算符（指針變量用“

33、 - ”）:p.value 、（ j = j + (+i);/ i先自增，變成1，然后再和j相加。執(zhí)行之后i=1 ，j=9。 k = k + (i+);/ i先和k相加，使k=6。然后i再自增。執(zhí)行之后i=2，k=6。 前綴運算符返回引用類型，后綴運算符返回數值類型。 為了避免錯誤，不要讓+、-和其他能夠改變變量的操作在同一行出現(xiàn)！ 7. 賦值運算符： 在C+中賦值是一種運算符。所以你會看到i=j=0 、dx=y 、return c=i+j之類的代碼。 +=、-=、*=、可以簡化書寫。例如 a*=2+3 相當于a=a*(2+3)。 (3) 真值表 p q p float c=6.4/(floa

34、t)i; / 把i的值變成float 類型。 兩個操作數進行四則運算，如果想保留小數位，那么兩個操作數應該都是浮點數。上面的代碼就是這樣。 1.4 函數 (1) 定義和使用函數 1. 定義和調用函數：下面定義了一個函數，返回值是double 類型的，其中有兩個參數i、j，分別是int 和float類型的。 double foo(i nt j, float j) 如果函數不需要返回任何值，可定義為void 類型。 函數的定義必須在函數調用的前面。只有在前面添加了函數定義，才能把具體實現(xiàn)放到調用的后面： double foo(i nt, float);/ 放到調用之前 2. 返回值：return

35、值； 函數是void類型的，那么return后面除了分號，什么都不跟。 調用之后，函數立刻結束。 不可以直接對函數名賦值(學過Pascal或Basic語言的同學要特別注意)。 3. 如果你的函數需要返回指針或引用，你必須注意：不要引用函數內部的變量！因為函數一結束，函數內部 的變量就煙消云散，不復存在了。正確做法是引用靜態(tài)變量(static )或全局變量。 4. 內聯(lián)函數(inline ):當一個函數內部只有寥寥幾句時，如“華氏度變攝氏度”，可以考慮將其定義成 內聯(lián)函數，通知編譯器省略函數入棧等操作，直接展開函數內容，以加快運行速度。 inline int FtoC(int f) return

36、 (f-32)/9*5; (2) 傳遞實參 1. 按值傳遞：例如int foo(int n)，在調用foo時，程序會把參數復制一份給n。這樣，對n的任何修 改都不會反映到調用foo的參數上面。 對于按值傳遞數組，一定要慎重。因為復制數組的元素要浪費很多時間。 2. 傳遞指針：例如int foo(int *n)。對n的修改會反映到調用foo的參數上面。 修改n的值時要注意，必須用取值運算符，否則改變的是n指向的內存空間。 此外，這種方法可以用于傳遞數組一一調用時只需把數組名作為參數。這時不需要取值運算符。 3. 傳遞引用：例如int foo(i nt fin、fout分別代表輸入文件和輸出文件。

37、把它們換成stdin 和 stdout，就是從屏幕輸入和從屏幕輸出?！?.5字符串操作”也使用了同樣的變量。 1. 輸出字符串或變量的值：printf(”格式字符串,); 或fprintf(fout,格式字符串,); 格式字符：“ 后連接一個字母。 字符 含義 字符 含義 d 整數 e, E 用科學記數法表示的浮點數 u 無符號整數 f 浮點數 o 八進制整數 c 字符 x, X 十六進制整數(小寫、大寫) s 字符串(字符數組) 常見的修飾符： %5d : 5位數，右對齊。不足5位用空格補齊，超過5位按實際位數輸出。 %-5d : 5位數，左對齊。不足 5位用空格補齊，超過 5位按實際位數輸

38、出。 %05d : 5位數，右對齊。不足 5位用0補齊，超過5位按實際位數輸出。 %+d:無論是正數還是負數，都要把符號輸出。 %.2f :保留2位小數。如果小數部分超過2位就四舍五入，否則用 0補全。 1. 輸入到變量 讀取不含空白的內容：scanf(”格式字符串, 或fscanf(fin,格式字符串, 格式字符和printf基本一致。 不要忘記“ 首先要判斷它是否為EOF (文件結束)。如果不是，就可以用強制類型轉換變成char。 使用const可防止n指向的內存空間發(fā)生改變：int foo( const int *n)。這時再寫n=5之類的語句會被報錯 在Windows下調試時，用“ l

39、64d ”輸出long long類型的值。交卷時，由于用Linux 測試，要改成“ %lld ; 讀取到行末時，要注意對換行符的處理。 Windows、Linux、Mac的回車字符是不同的。Linux 是n, Mac是r, Windows 下是兩個 字符 r 和 n。 (2) 使用流輸入 / 輸出 頭文件： 1. 輸入到變量 ： cinn; 2. 輸出到屏幕上 ： coutnm; couta,bendl; 3. 換行 ：coutendl; 4. 格式化輸出 ： 頭文件： 右對齊，長度為 n ，不足的部分用空格補齊 ： cout.width(n); cout.fill( );/ 如果想用“ 0”

40、補齊，就可以把空格換成“0 couta; 前兩行代碼，每次輸出之前都要調用。 輸出成其他進位制數 ： 8： coutocta; 16 ： couthexa; 其他進位制需要自己轉換。 5. 注意，數據規(guī)模很大時，流的輸入輸出速度會變得很慢，甚至數據還沒讀完就已經超時了。 在進行輸入輸出之前加入這樣一條語句： ios:sync_with_stdio(false); 調用之后，用 cin 、 cout 輸入輸出的速度就和 scanf 、 printf 的速度一樣了。 1.6 其他常用操作 ! 本資料常用的頭文件 ：、 、 、 以及 、 、 、 等。 C+的流、容器、算法等都需要引用std命名空間。

41、所以需要在#inelude后面、你的代碼前面加上一句: using namespace std; (1) 庫函數 1. 數組的整體操作: 頭文件: 將 a 初始化: memset(a, 0, sizeof(a); 第二個參數應該傳入0、 -1 或 0 x7F 。傳入 0 或-1 時， a 中每個元素的值都是 0 或-1 ；如果傳入 0 x7F 時，那么 a 中每個元素的值都是 0 x7F7F7F7F (不是 0 x7F ！)，可認為是“無窮大”。 將 a 整體復制到 b 中: memcpy(b, a, sizeof(a); 判斷 a 和 b 是否等價: memcmp(a, b, sizeof(

42、a);/ 返回 0 表示等價 2. 字符操作 : 頭文件: tolower(c) 、 toupper(c) :將 c 轉化為小寫或大寫。 isdight(c) 、 isalpha(c) 、 isupper(c) 、 islower(c) 、 isgraph(c) 、 isalnum(c) :分別 判斷 c 是否為十進制數字、英文字母、大寫英文字母、小寫英文字母、非空格、字母或數字。 3. 最大值 / 最小值 : 頭文件: max(a,b) 返回 a 和 b 中的最小值， min(a,b) 返回 a 和 b 中的最大值。 其實我們可以自己寫： 4. 交換變量的值 ： swap(a,b) 頭文件：

43、 其實我們可以自己寫： inline void swap(int a=b; b=t; 5. 執(zhí)行DOS命令或其他程序：system(” 命令行”)； 頭文件： 暫停屏幕： system(pause)； 競賽交卷或 OJ 提交代碼之前必須刪除 system ，否則會被視為作弊 ( 如果是 tyvj 甚至都無法提交 )。 如果使用輸入重定向，那么命令提示符不會接受任何鍵盤輸入直接用文件內容代替鍵盤了。 6. 立刻退出程序 ： exit(0)； 這種方法常用于深度優(yōu)先搜索。執(zhí)行后，程序立刻停止并返回0 ，所以在調用前應該輸出計算結果。 頭文件： 7. 計時 ： double a = (double)

44、clock() / (double)CLOCKS_PER_SEC； 上面的 a 對應一個時刻。而將兩個時刻相減，就是時間間隔。可用這種方法卡時。 頭文件： 8. 斷言 ： assert( 條件 ) 條件為假時，程序立刻崩潰。 頭文件： 如果定義了 NDEBUG符號，那么它將不會起任何作用。 斷言和錯誤處理不同：例如出現(xiàn)“人數為負數”的情況，如果責任在于用戶，那么應該提示錯誤并重 新輸入， 而不是用斷言； 如果發(fā)生在計算過程， 應該用斷言來使程序崩潰， 以幫助改正代碼中的錯誤。 換句話說，錯誤處理防的是用戶的錯誤，斷言防的是代碼的錯誤。 9. 快速排序 ： qsort( 首項的指針 , 待排序元

45、素個數 , 每個元素所占字節(jié) , 比較函數 ) 頭文件： 這是留給 C 黨的快速排序，它比 STL 的排序算法啰嗦一些。 比較函數返回 int 類型，用于對兩個元素的比較。原型如下： int compare(const void *i, const void *j)； 如果*i v *j，則應返回一個小于 0的數；如果*i=*j 則應返回0,否則返回一個大于 0的數。 10. 隨機數發(fā)生器 ： 頭文件： 產生隨機數： 032767 的隨機數： rand() 粗略地控制范圍： rand()% 范圍 注意,這種方法產生的隨機數的分布是不均勻的。 精確地控制范圍： (double)rand()/RA

46、ND_MAX*范圍 控制在 a, b)之間： a + (int) (double)rand()/RAND_MAX*(b-a) 初始化隨機數種子： srand( 數字 ) ：初始化隨機數種子。 注意,這條語句在程序開頭使用,并且最多用一次。同一程序、同一平臺,srand 中的參數相等, 用 rand() 產生的隨機數序列相同。 使隨機數更加隨機：引用 ,然后這樣初始化隨機數種子, srand(time(NULL) 。 不要在循環(huán)中使用這條語句(例如批量產生隨機數據),因為time 只精確到秒。 11. 數學函數 ： 頭文件： abs(x) ：求 x 的絕對值(該函數同時包含于 )。 sin 、c

47、os 、tan 、asin 、acos 、atan ：三角函數,角的單位為弧度。 可用atan(1)*4 表示n sinh 、cosh、tanh、asinh 、acosh、atanh :雙曲函數 sqrt :求平方根 ceil(x) 、floor(x):分別返回大于等于x的最小整數、小于等于x的最大整數。注意，參數和返 回值都是浮點數類型。 exp(x) 、log(x) 、Iog10 :分別求 ex、In x、lg x (順便提一句，指數可以把加法問題轉化為乘法問題，對數可以把乘法問題轉化為加法問題。) pow(a,b):計算ab由于精度問題，你仍然需要學會快速幕。 fmod(a,b):計算a

48、除以b的余數。當然，這是浮點數的版本。 宏定義 宏定義是C語言的產物。在 C+中，它真的out 了。 1. 第一種用法一一配合條件編譯：#define DEBUG 定義一個叫 DEBUG的標識符。它應該與 #ifdef或#ifndef配合使用。舉例如下： #defi ne DEBUG #ifdef DEBUG void prin t(i nt v) cout v en dl; #else void prin t(i nt) #en dif 如果符號DEBUG存在，那么編譯器會編譯上面的、能輸出數值的print，否則編譯器編譯下面的、什么 事情都不做的print 。 把上面的#ifdef 換成#

49、ifndef，那么編譯的代碼正好上面所說的相反。 2. 第二種用法一一表達式： #defi ne N5000 編譯時，編譯器會用類似于“查找和替換”的方法，把代碼中的N換成5000。如果需要換成表達式，應 該用括號把它們包圍。例如： #defi ne a1+2 #defi ne b(1+2) c=a*2; d=b*2; 編譯時上面一行會變成“ c=1+2*2; d=(1+2)*1;”，顯然它們的值是不同的。 所以，用en um和con st 代替它是明智之舉。 此外，要注意表達式末尾不能有分號(除非你需要)。 3. 第三種用法一一簡易“函數”： #defi ne FtoC(a) (a)-32)

50、/9*5) 這類似于一個函數。不過，由于編譯器只是進行簡單替換，所以為了安全，a、b應該用括號包圍，整個表 達式也應該用括號包圍。 這種“函數”用法和普通函數一樣，且速度更快。然而，它很容易出現(xiàn)難以查出的錯誤。所以，請用內聯(lián) 函數(inline)代替宏定義。 注意，不要在“參數”中改變變量的值！ 4. 第四種用法一一簡化一段代碼： #define move(dx, dy) if (isfull(dir) return; if (map(x+dx, y+dy)=0) push(dir,x+dx,y+dy,headdir, dep); check(dir); 不要忘記每行后面的“”，它相當于換行符

51、。這次move簡化了一大段代碼。同樣，內聯(lián)函數也可以。 1.7 字符串操作! 頭文件：。printf 和 scanf 在 中，cin 和 cout 在頭文件 中且位于 std命名空間內。 下面假設待處理的字符串為str和str2 ，即：char strMAX, str2MAX; 牢記，字符串的最后一個字符一定是0。如果字符串內沒有0，進行以下操作(輸入除外)時可能 會造成意外事故。 1. 輸出字符串str : cout str; 以上兩種方法在輸入時會忽略空格、回車、TAB等字符，并且在一個或多個非空格字符后面輸入空格 時，會終止輸入。 fgets(str, MAX, fin); 每調用一次，

52、就會讀取一行的內容(即不斷讀取，直到遇到回車停止)。 3. 求字符串str的長度：strlen(str)/這個長度不包括末尾的0。 4. 把字符串str2連接到字符串str 的末尾：strcat(str, str2) str的空間必須足夠大，能夠容納連接之后的結果。 連接的結果直接保存到str里。函數返回值為如果str=str2 ，返回0;如果str v str2 ，返回-1 。 7. 在str 中尋找一個字符 c: strchr(str, c) 返回值是一個指針，表示 c在str中的位置。用strchr 的返回值減str ，就是具體的索引位置。 8. 在 str 中尋找 str2 : str

53、str(str, str2) 返回值是一個指針，表示str2 在str中的位置。用strstr的返回值減str ,就是具體的索引位置。 此問題可以用KMP算法解決。KMP算法很復雜，在 NOIP范圍內用途不大。 9. 從 str 中獲取數據：sscanf(str, %d, 格式化字符串:sprintf(str, %d, i); 它們和fscanf 、fprintf非常像，用法也類似。可以通過這兩個函數進行數值與字符串之間的轉換。 1.8 文件操作! 正式競賽時，數據都從擴展名為“in ”的文件讀入，并且需要你把結果輸出到擴展名為“out ”的文件中; 在OJ (OnlineJudge，在線測評

54、器)中則不需要文件操作。具體情況要仔細查看題目說明，以免發(fā)生悲劇。 (1) 輸入/輸出重定向 頭文件： 或 方法：只需在操作文件之前添加以下兩行代碼。 freope n( XXXXX.i n,r,stdi n); freope n( XXXXX.out,w,stdout); 調用兩次freopen 后，scanf、printf 、cin、cout的用法完全不變，只是操作對象由屏幕變成了指 定的文件。 使用輸入重定向之后，“命令提示符”窗口將不再接受任何鍵盤輸入(調用system 時也是如此)，直到 暫停屏幕。 程序退出。這時不能再用system(pause) 文件流 頭文件： 流的速度比較慢，

55、在輸入/輸出大量數據的時候，要使用其他文件操作方法。 方法：定義兩個全局變量。 ifstream fin(” XXXXX.i n); ofstream fout(XXXXX.out); fin 、fout 和 cin、cout 一樣，也用 ”運算符輸入 / 輸出，如：fina; foutb; 當然，也可以通過 #define 把fin、fout 變成cin、cout : #define cin fin #defi ne cout fout FILE 指針 頭文件：或 方法：定義兩個指針。 FILE *fin, *fout; int mai n() fin = fopen( XXXXX.i n,

56、 r); fout = fope n(” XXXXX.out, w); fclose(fi n); fclose(fout);/在某些情況下，忘記關閉文件會被認為是沒有產生文件。 return 0; 進行輸入/輸出操作時，要注意 函數名的前面有f，即fprintf 、fscanf 、fgets ，并且這些函數的第 一個參數不是格式字符串，而是 fin 或fout ，女口 fprintf( fout , %d, ans) 。 想改成從屏幕上輸入/輸出時，不用對代碼動手術，只需把含 fopen和fclose的代碼注釋掉，并改成: fin=stdi n; fout=stdout; 1.9 簡單的算法

57、分析和優(yōu)化 (1) 復雜度 為了描述一個算法的優(yōu)劣，我們引入算法時間復雜度和空間復雜度的概念。 時間復雜度：一個算法主要運算的次數，用大o表示。通常表示時間復雜度時，我們只保留數量級最大的 項，并忽略該項的系數。 例如某算法，賦值做了 3n3+n2+8次，則認為它的時間復雜度為0( n3);另一算法的主要運算是比較，做 了 4 X 2n+2 n4+700次，則認為它的時間復雜度為O(2 n)。 當然，如果有多個字母對算法的運行時間產生很大影響，就把它們都寫進表達式。如對mxn的數組遍歷 的時間復雜度可以寫作 O(mn)。 空間復雜度：一個算法主要占用的內存空間，也用大 O表示。 在實際應用時，

58、空間的占用是需要特別注意的問題。太大的數組經常是開不出來的，即使開出來了，遍歷 的時間消耗也是驚人的。 (2) 常用算法的時空復雜度 1s運算次數約為5,000,000。也就是說，如果把n代入復雜度的表達式，得數接近或大于5,000,000 那么會有超時的危險。 常見的數量級大小:0(1) v O(log n) v 0( n) v 0( nlog n) v O( n2) O( n3) v O(2 n) v 0( n!) 數量級 能承受的大致規(guī)模 常見算法 0(1) 任意 直接輸出結果 0(log n) 任意 二分查找、快速幕 0( n) 以百萬計(五六百萬) 貪心算法、掃描和遍歷 0( nlo

59、g n) P以十萬計(三四十萬): 帶有分治思想的算法，如二分法 0( n2) 以千計數(兩千) 枚舉、動態(tài)規(guī)劃 0( n3) 不到兩百 動態(tài)規(guī)劃 0(2 n) 24 搜索 0( n!) 10 產生全排列 0( n ) 8 暴力法破解密碼 0(1)叫常數時間；0( n)、0( n2)、0( n3)、0( n4)叫做多項式時間；0(2 n)、0(3 n)叫做指數時間。 (3) 簡單的優(yōu)化方法 1. 時間的簡單優(yōu)化方法 時間上的優(yōu)化在于少做運算、做耗時短的運算等。有幾個規(guī)律需要注意： 整型運算耗時遠低于實型運算耗時。 位運算速度極快。 邏輯運算比四則運算快。 +、-、*運算都比較快 (-、*比+慢

60、一點點，可以忽略不計)。 /運算比+、-、*慢得多(甚至慢幾十倍)。 取余和除法運算速度相當。 調用函數要比直接計算慢(因為要入棧和出棧)。 這些規(guī)律我們可以從宏觀上把握。事實上，究竟做了幾步運算、幾次賦值、變量在內存還是緩存等多數由 編譯器、系統(tǒng)決定。但是，少做運算(尤其在循環(huán)體、遞歸體中)一定能很大程度節(jié)省時間。 2. 空間的簡單優(yōu)化方法 空間上的優(yōu)化主要在于減小數組大小、降低數組維數等。常用的節(jié)省內存的方法有： 壓縮儲存一一見180頁“ A.7 狀態(tài)壓縮* ”。 覆蓋舊數據一一例如滾動數組(見62頁“ (5)使用滾動數組”)。 要注意的是，對空間的優(yōu)化即使不改變復雜度，只是改變n的系數也