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

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

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

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

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

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

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

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

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

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

10、種樹問題 47 4.6 馬的哈密爾頓鏈 47 4.7 三值的排序 49 4.8 田忌賽馬 50 4.9 小結(jié) 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 聰明的質(zhì)監(jiān)員 56 5.9 模板58 5.10 小結(jié)59 第六單元動態(tài)規(guī)劃60 6.1 導(dǎo)例：數(shù)字三角形 60 6.2 區(qū)間問題：石子合并 63 6.3 坐標(biāo)問題65 6.4 背包問題67 6.5 編號問題67 6.6 遞歸結(jié)構(gòu)問題 68 6.7 DAG上的

11、最短路徑 71 6.8 樹形動態(tài)規(guī)劃* 72 6.9 狀態(tài)壓縮類問題：過河 74 6.10 Bito nic旅行76 6.11 小結(jié)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 小結(jié)90 第九單元基本數(shù)據(jù)結(jié)構(gòu)91 9.1 線性表（順序結(jié)構(gòu)） 91 9.2 線性表（鏈?zhǔn)浇Y(jié)構(gòu)） 91 9.3 棧 93 9.4 隊列 94 9.5 二叉樹 95 9.6 并查集！ 99 9.7 小結(jié) 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 第十一單元數(shù)學(xué)基礎(chǔ)116 11.1 組合數(shù)學(xué) 116 11.2

13、組合數(shù)的計算！ 117 11.3 排列和組合的產(chǎn)生（無重集元素） ！ 117 11.4 排列和組合的產(chǎn)生（有重集元素） .1 20 11.5 秦九韶算法 122 11.6 進制轉(zhuǎn)換（正整數(shù)） 123 11.7 高精度算法（壓位存儲）！ .123 11.8 快速幕! 128 11.9 表達(dá)式求值 129 11.10 解線性方程組* 133 第十二單元數(shù)論算法135 12.1 同余的性質(zhì)！ 135 12.2 最大公約數(shù)、最小公倍數(shù) ! .135 12.3 解不定方程 ax + by = c!* 1 35 12.4 同余問題* 136 12.5 素數(shù)和素數(shù)表 136 12.6 分解質(zhì)因數(shù) 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 拓?fù)渑判?152 13.9 關(guān)鍵路徑 155 13.10 二分圖初步 157 13.11 小結(jié) 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 時間/空間權(quán)衡. 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 調(diào)試 185 B.1 常見錯誤類型. 185 B.2 調(diào)試過程 .185 B.3 調(diào)試功能 .185 B.4 符號DEBUG的應(yīng)用 186 B.5 代碼審查表 186 B.6 故障檢查表 187 B.7 命令行和批處理* 188 附錄C

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

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

18、 C+的東西都要引用 std命名空間，所以代碼中會有“ using namespace std;”。 mai n（）:所有程序都要從 mai n（）開始。 在所有的算法競賽中，main（）的返回值必須是0,否則視為程序異常結(jié)束，得分為 0分。 語句和語句塊： 1. 語句：一般情況下，一條語句要用一個分號“；”結(jié)束。為了美觀和可讀性，可以把一條語句擴展成 幾行，也可以把多個語句寫到同一行上。 2. 語句塊：用“ ”和“ ”包圍的代碼是語句塊。無論里面有多少代碼，在原則上，語句塊所在的整體 都視為一條語句。 （2）選擇結(jié)構(gòu) 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語句內(nèi)的 if語句，即if的嵌套。所以else和if中間要有空格。 else 語句或語句塊N 2. switch 語句：switch表示選擇。它根據(jù)條件的不同取值來執(zhí)行不同的語句。格式如下: switch （

20、 表達(dá)式） case 值 1: 代碼段A break; case 值 2: 代碼段B break; default: 代碼段N break; ； 如果表達(dá)式的值是值 1，就執(zhí)行代碼段 A;如果表達(dá)式的值是值 2，就執(zhí)行代碼段B否則執(zhí)行代碼段N。 default一部分可以省略。 如果不使用break，那么緊隨其后的 case部分代碼也會被執(zhí)行，直到遇到break 或switch 語句 結(jié)束為止！ switch結(jié)尾要有一個分號。 3. if、switch都可以嵌套使用。 【問題描述】輸入一個日期，判斷它所在年份是否為閏年，并輸出所在月份的天數(shù)。閏年的判斷方法：四年一 閏，百年不閏，四百年又閏。 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; /判斷所在月份的天數(shù) 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)結(jié)構(gòu) 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)轉(zhuǎn)移的條件和循環(huán)體。格式如下： for (初始條件；繼續(xù)循環(huán)的條件；狀態(tài)轉(zhuǎn)移的條件) 循環(huán)體 轉(zhuǎn)換成while 循環(huán)，即： 初始條件 while ( 繼續(xù)循環(huán)的條件) 循環(huán)體 狀態(tài)轉(zhuǎn)移 for后三個條件不是必需的，可以省略不寫，但分號必須保留。 5. 在循環(huán)語句內(nèi)部使用break，可以跳出循環(huán)；使用continue，可以忽略它后面的代碼，馬上進入下一輪 循環(huán)。 注意，這兩個語句只對它所在的一層循環(huán)有效。 6. 寫for循環(huán)時，一定要注意： 不要把計數(shù)器的字母打錯，尤其是在復(fù)制/粘貼一段代碼的時候。 根據(jù)算法要明確不等號是“”，還是“ =”。 逆序循環(huán)時，不要把自減“-”寫成自增“ +

24、”！ 【問題描述】輸入 n,輸出n! (n! = 1 x 2 x 3 x4 xx n)。結(jié)果保證小于long long的范圍。當(dāng)輸入值 為負(fù)數(shù)時結(jié)束程序。 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語句用于無條件跳轉(zhuǎn)。要想跳轉(zhuǎn)，首先要定義標(biāo)簽(在代碼開頭的一段標(biāo)識符，后面緊跟冒號) 然后才能goto那個標(biāo)簽。 很多教程不提倡使用無條件跳轉(zhuǎn)，因為它破壞了程序結(jié)構(gòu)，還容易給代碼閱讀者帶來麻煩。不過，這不代 表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語言為基礎(chǔ)開發(fā)出來的，C語言的大多數(shù)內(nèi)容被保留了下來。在信息學(xué)競賽領(lǐng)域，很多情 況下C和C+可以互相轉(zhuǎn)化，甚至不用對代碼進行任何修改。 下面是信息學(xué)競賽領(lǐng)域中C和C+的重要區(qū)別： C+支持用流輸入輸出，而 C只能用seanf和printf再見了， d! C+非常支持面向?qū)ο缶幊?，而C已經(jīng)“ out ”了。 資料中的“

26、高精度算法”就只能用C+完成，因為在struct內(nèi)定義了成員函數(shù)。 C+可以用更強大的stri ng類處理字符串，而不必?fù)?dān)心發(fā)生某些低級錯誤。 C+有強大的STL，而C沒有(有一個小小的qsort 和bsearch算是補償了)。 STL是很多人從C轉(zhuǎn)到C+的重要原因。 C的頭文件名仍然可以用在C+中，不過可能會收到警報一一應(yīng)該去掉“.h ”，前面再加一個“ c”。 如 應(yīng)該改成 。 C程序運行速度稍優(yōu)于 C+。不過也沒快多少。 總之，C能做的一切事情，C+也能做；C+能做的一切事情，C不一定能做。 1.2 數(shù)據(jù)類型 (1) 基本數(shù)據(jù)類型 名稱 占用空間 別名 數(shù)據(jù)范圍 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 一般都使用有符號整數(shù)，除非范圍不夠大，或者你確定你的減法運算不會岀現(xiàn)小數(shù)減大數(shù)”。 一般來說，使用int、long long更保險一些，除非內(nèi)存不夠用。 不要使用“ _int64 ”！它是Visual C+特

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

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

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

32、，p和b又沒關(guān)系了 /輸出p指向的變量的值，即c6 / 現(xiàn)在p指向了 c7; /表示p沒有指向任何變量 /由于NULL（ 0）是一段無意義的地址，所以程序極有可能崩潰。 為了不在競賽中把自己搞暈，請回避指針，對其敬而遠(yuǎn)之。 引用 通俗地講，引用是某個變量的別名。下面定義了一個叫p的引用，它實際上是 f02。無論是改變p 的值，還是改變f02的值，結(jié)果都是一樣的。 int 使用引用的好處是，在函數(shù)的形參中定義引用類型，可以直接修改變量的值，而不用考慮“ ; 變量可以定義成上面的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。 前綴運算符返回引用類型，后綴運算符返回數(shù)值類型。 為了避免錯誤，不要讓+、-和其他能夠改變變量的操作在同一行出現(xiàn)！ 7. 賦值運算符： 在C+中賦值是一種運算符。所以你會看到i=j=0 、dx=y 、return c=i+j之類的代碼。 +=、-=、*=、可以簡化書寫。例如 a*=2+3 相當(dāng)于a=a*(2+3)。 (3) 真值表 p q p float c=6.4/(floa

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

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

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

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

38、出。 %05d : 5位數(shù)，右對齊。不足 5位用0補齊，超過5位按實際位數(shù)輸出。 %+d:無論是正數(shù)還是負(fù)數(shù)，都要把符號輸出。 %.2f :保留2位小數(shù)。如果小數(shù)部分超過2位就四舍五入，否則用 0補全。 1. 輸入到變量 讀取不含空白的內(nèi)容：scanf(”格式字符串, 或fscanf(fin,格式字符串, 格式字符和printf基本一致。 不要忘記“ 首先要判斷它是否為EOF (文件結(jié)束)。如果不是，就可以用強制類型轉(zhuǎn)換變成char。 使用const可防止n指向的內(nèi)存空間發(fā)生改變：int foo( const int *n)。這時再寫n=5之類的語句會被報錯 在Windows下調(diào)試時，用“ 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; 前兩行代碼，每次輸出之前都要調(diào)用。 輸出成其他進位制數(shù) ： 8： coutocta; 16 ： couthexa; 其他進位制需要自己轉(zhuǎn)換。 5. 注意，數(shù)據(jù)規(guī)模很大時，流的輸入輸出速度會變得很慢，甚至數(shù)據(jù)還沒讀完就已經(jīng)超時了。 在進行輸入輸出之前加入這樣一條語句： ios:sync_with_stdio(false); 調(diào)用之后，用 cin 、 cout 輸入輸出的速度就和 scanf 、 printf 的速度一樣了。 1.6 其他常用操作 ! 本資料常用的頭文件 ：、 、 、 以及 、 、 、 等。 C+的流、容器、算法等都需要引用std命名空間。

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

42、a);/ 返回 0 表示等價 2. 字符操作 : 頭文件: tolower(c) 、 toupper(c) :將 c 轉(zhuǎn)化為小寫或大寫。 isdight(c) 、 isalpha(c) 、 isupper(c) 、 islower(c) 、 isgraph(c) 、 isalnum(c) :分別 判斷 c 是否為十進制數(shù)字、英文字母、大寫英文字母、小寫英文字母、非空格、字母或數(shù)字。 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 甚至都無法提交 )。 如果使用輸入重定向，那么命令提示符不會接受任何鍵盤輸入直接用文件內(nèi)容代替鍵盤了。 6. 立刻退出程序 ： exit(0)； 這種方法常用于深度優(yōu)先搜索。執(zhí)行后，程序立刻停止并返回0 ，所以在調(diào)用前應(yīng)該輸出計算結(jié)果。 頭文件： 7. 計時 ： double a = (double)

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

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

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

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

48、除以b的余數(shù)。當(dāng)然，這是浮點數(shù)的版本。 宏定義 宏定義是C語言的產(chǎn)物。在 C+中，它真的out 了。 1. 第一種用法一一配合條件編譯：#define DEBUG 定義一個叫 DEBUG的標(biāo)識符。它應(yīng)該與 #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存在，那么編譯器會編譯上面的、能輸出數(shù)值的print，否則編譯器編譯下面的、什么 事情都不做的print 。 把上面的#ifdef 換成#

49、ifndef，那么編譯的代碼正好上面所說的相反。 2. 第二種用法一一表達(dá)式： #defi ne N5000 編譯時，編譯器會用類似于“查找和替換”的方法，把代碼中的N換成5000。如果需要換成表達(dá)式，應(yīng) 該用括號把它們包圍。例如： #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 代替它是明智之舉。 此外，要注意表達(dá)式末尾不能有分號(除非你需要)。 3. 第三種用法一一簡易“函數(shù)”： #defi ne FtoC(a) (a)-32)

50、/9*5) 這類似于一個函數(shù)。不過，由于編譯器只是進行簡單替換，所以為了安全，a、b應(yīng)該用括號包圍，整個表 達(dá)式也應(yīng)該用括號包圍。 這種“函數(shù)”用法和普通函數(shù)一樣，且速度更快。然而，它很容易出現(xiàn)難以查出的錯誤。所以，請用內(nèi)聯(lián) 函數(shù)(inline)代替宏定義。 注意，不要在“參數(shù)”中改變變量的值！ 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); 不要忘記每行后面的“”，它相當(dāng)于換行符

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

52、就會讀取一行的內(nèi)容(即不斷讀取，直到遇到回車停止)。 3. 求字符串str的長度：strlen(str)/這個長度不包括末尾的0。 4. 把字符串str2連接到字符串str 的末尾：strcat(str, str2) str的空間必須足夠大，能夠容納連接之后的結(jié)果。 連接的結(jié)果直接保存到str里。函數(shù)返回值為如果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算法很復(fù)雜，在 NOIP范圍內(nèi)用途不大。 9. 從 str 中獲取數(shù)據(jù)：sscanf(str, %d, 格式化字符串:sprintf(str, %d, i); 它們和fscanf 、fprintf非常像，用法也類似?？梢酝ㄟ^這兩個函數(shù)進行數(shù)值與字符串之間的轉(zhuǎn)換。 1.8 文件操作! 正式競賽時，數(shù)據(jù)都從擴展名為“in ”的文件讀入，并且需要你把結(jié)果輸出到擴展名為“out ”的文件中; 在OJ (OnlineJudge，在線測評

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

55、在輸入/輸出大量數(shù)據(jù)的時候，要使用其他文件操作方法。 方法：定義兩個全局變量。 ifstream fin(” XXXXX.i n); ofstream fout(XXXXX.out); fin 、fout 和 cin、cout 一樣，也用 ”運算符輸入 / 輸出，如：fina; foutb; 當(dāng)然，也可以通過 #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);/在某些情況下，忘記關(guān)閉文件會被認(rèn)為是沒有產(chǎn)生文件。 return 0; 進行輸入/輸出操作時，要注意 函數(shù)名的前面有f，即fprintf 、fscanf 、fgets ，并且這些函數(shù)的第 一個參數(shù)不是格式字符串，而是 fin 或fout ，女口 fprintf( fout , %d, ans) 。 想改成從屏幕上輸入/輸出時，不用對代碼動手術(shù)，只需把含 fopen和fclose的代碼注釋掉，并改成: fin=stdi n; fout=stdout; 1.9 簡單的算法

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

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

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

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