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

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

3、N、M、MAX針對數據規模而言，比實際最大數據規模大；INF針對取值而言，是一個非常大，但又與int的最大值有一定差距的數，如100000000。對于不同程序，數組下標的下限也是不同的，有的程序是0，有的程序是1。閱讀程序時要注意。閱讀順序和方法沒聽說過NOIP，或對NOIP不甚了解的同學，應該先閱讀附錄E，以加強對競賽的了解。如果不能順利通過初賽，你就應該先補習初賽知識。這本NOIP復習資料總結的是復賽知識。如果沒有學過C+語言，應該先選擇一本C+語言教材。一般情況下，看到“面向對象編程”一章的前一頁就足夠了（NOIP不用“面向對象編程”，更不用擺弄窗口對話框）。附錄G介紹了一些書籍和網站。

4、你應該選擇一本書，認真地學習。再選擇一個網站，作為練習的題庫。第一單元對競賽中常用的操作和簡單的算法分析進行了總結，算作對C+語言的鞏固。同時，閱讀這一單元之后，你應該選擇一個合適的C+代碼編輯器。第二到第六單元介紹了競賽常用的算法。閱讀每一章時，應該先閱讀“小結”名曰“小結”，實際上是“導讀”。這五個單元除了經典習題，還有某些思想和算法的具體實現方法。這些信息可能在明處，也可能在暗處，閱讀時要注意挖掘和體會。如果有時間，應該在不看解析和代碼的前提下獨立完成這些題。第七單元是第六單元的一個部分，由于它的內容來自背包九講，所以單獨放在一個單元。從第八單元開始，到第十三單元，基本上就沒有習題了。換

5、句話說，該“背課文”了。第八單元介紹了常用的排序算法。你可以有選擇地學習，但一定要掌握“STL算法”和“快速排序”。第九單元介紹了基本數據結構，你一定要掌握第九單元前五小節的內容（本單元也有應該優先閱讀的“小結”）。有余力的話，第六小節的并查集也應該掌握。第十單元介紹了與查找、檢索有關的數據結構和算法。你也可以有選擇地學習。第十一單元與數學有關。數學對于信息學來說具有舉足輕重的地位。標有“！”的應該背下來，至于其他內容，如果出題，你應該能把它解決。第十二單元仍與數學有關。第十三單元是圖論。學習時要先閱讀“小結”，把概念弄清楚。之后要掌握圖的實現方法。接下來要掌握一些經典圖論算法：Kruskal

6、算法、Dijkstra算法、SPFA、Floyd算法、拓撲排序。附錄F總結了2004年以來NOIP考察的知識點，可以作為選擇性學習的參考。在學習算法和數據結構的同時，應該閱讀和學習附錄A。如果你還有余力，你應該學習第十四單元。第十四單元的內容不是必須要掌握的，但是一旦學會，可以發揮C+語言的優勢，降低編程復雜度。臨近競賽時，應該閱讀附錄B和附錄C，以增加經驗，減少失誤。面臨的問題1. 這是復賽復習資料需要有人能用心總結、整理初賽的知識，就像這份資料一樣。2. 潛在的問題還是相當多的，只是時間不夠長，問題尚未暴露。3. 部分代碼缺少解說，或解說混亂。4. 個人語文水平較差，資料也是如此。5. 沒

7、有對應的Pascal語言版本。如果有人能為P黨寫一個Pascal版的STL，他的RP一定會爆增！6. 希望有人能用整理資料，并以自由文檔形式發布。最后，歡迎大家以交流、分享和提高為目的修改、復制、分發本資料，同時歡迎大家將資料翻譯成Pascal語言版供更多OIer閱讀！謝謝大家的支持！葫蘆島市一高中 李思洋2012年8月27日 1 目 錄 目 錄標題上的符號：1. !：表示讀者應該熟練掌握這些內容，并且在競賽時能很快地寫出來。換句話說就是應該背下來。2. *：表示內容在NOIP中很少涉及，或者不完全適合NOIP的難度。3. #：表示代碼存在未更正的錯誤，或算法本身存在缺陷。I 前 言1目 錄I

8、第一單元C+語言基礎11.1程序結構11.2數據類型41.3運算符61.4函數81.5輸入和輸出!91.6其他常用操作!101.7字符串操作!131.8文件操作!131.9簡單的算法分析和優化141.10代碼編輯器16第二單元基礎算法172.1經典枚舉問題172.2火柴棒等式182.3梵塔問題192.4斐波那契數列192.5常見的遞推關系!202.6選擇客棧222.72k進制數232.8Healthy Holsteins242.9小結25第三單元搜索273.1N皇后問題273.2走迷宮293.38數碼問題313.4埃及分數343.5Mayan游戲363.6預處理和優化403.7代碼模板413.

9、8搜索題的一些調試技巧433.9小結44第四單元貪心算法464.1裝載問題464.2區間問題464.3刪數問題474.4工序問題474.5種樹問題474.6馬的哈密爾頓鏈474.7三值的排序494.8田忌賽馬504.9小結50第五單元分治算法515.1一元三次方程求解515.2快速冪515.3排序515.4最長非降子序列535.5循環賽日程表問題535.6棋盤覆蓋545.7刪除多余括號555.8聰明的質監員565.9模板585.10小結59第六單元動態規劃606.1導例：數字三角形606.2區間問題：石子合并636.3坐標問題656.4背包問題676.5編號問題676.6遞歸結構問題686.7

10、DAG上的最短路徑716.8樹形動態規劃*726.9狀態壓縮類問題：過河746.10Bitonic旅行766.11小結77第七單元背包專題787.1部分背包問題787.20/1背包問題!787.3完全背包問題797.4多重背包問題797.5二維費用的背包問題807.6分組的背包問題817.7有依賴的背包問題817.8泛化物品817.9混合背包問題827.10特殊要求827.11背包問題的搜索解法837.12子集和問題84第八單元排序算法858.1常用排序算法858.2簡單排序算法878.3線性時間排序888.4使用二叉樹的排序算法*898.5小結90第九單元基本數據結構919.1線性表（順序結

11、構）919.2線性表（鏈式結構）919.3棧939.4隊列949.5二叉樹959.6并查集!999.7小結102第十單元查找與檢索10410.1順序查找10410.2二分查找!10410.3查找第k小元素!10510.4二叉排序樹10610.5堆和優先隊列*10810.6哈夫曼（Huffman）樹11010.7哈希（Hash）表111第十一單元數學基礎11611.1組合數學11611.2組合數的計算!11711.3排列和組合的產生（無重集元素）!11711.4排列和組合的產生（有重集元素）12011.5秦九韶算法12211.6進制轉換（正整數）12311.7高精度算法（壓位存儲）!12311.

12、8快速冪!12811.9表達式求值12911.10解線性方程組*133第十二單元數論算法13512.1同余的性質!13512.2最大公約數、最小公倍數!13512.3解不定方程axbyc!*13512.4同余問題*13612.5素數和素數表13612.6分解質因數137第十三單元圖與圖論算法13913.1圖的實現13913.2圖的遍歷14113.3連通性問題14213.4歐拉回路 鄰接矩陣14613.5最小生成樹（MST）14713.6單源最短路問題（SSSP問題）14813.7每兩點間最短路問題（APSP問題）!15213.8拓撲排序15213.9關鍵路徑15513.10二分圖初步15713

13、.11小結160第十四單元 STL簡介16414.1STL概述16414.2常用容器16414.3容器適配器17014.4常用算法17114.5迭代器17514.6示例：合并果子175附錄A思想和技巧177A.1時間/空間權衡177A.2試驗、猜想及歸納177A.3模型化177A.4隨機化*178A.5動態化靜態178A.6前序和!179A.7狀態壓縮*180A.8抽樣測試法*182A.9離散化*183A.10Flood Fill*184附錄B調試185B.1常見錯誤類型185B.2調試過程185B.3調試功能185B.4符號DEBUG的應用186B.5代碼審查表186B.6故障檢查表187B

14、.7命令行和批處理*188附錄C競賽經驗和教訓192C.1賽前兩星期192C.2賽前30分鐘192C.3解題表193C.4測試數據195C.5交卷前5分鐘196C.6避免偶然錯誤196C.7騙分197附錄D學習建議198D.1學習方法198D.2學習能力198D.3關于清北學堂198附錄E競賽簡介199E.1從NOIP到IOI199E.2NOIP簡介199E.3常用語201E.4第一次參加復賽202附錄FNOIP復賽知識點分布204附錄G資料推薦205G.1書籍205G.2網站205參考文獻206計算機專業是朝陽還是夕陽？207杜子德在CCF NOI2012開幕式上的講話209多數奧賽金牌得主

15、為何難成大器210第單元C+語言基礎第單元C+語言基礎1.1程序結構(1) 程序框架 注釋：注釋有兩種，一種是“/”，另一種是“/* */”。“/”必須單獨放置一行，或代碼所在行的后面；而“/*”、“*/”成對存在，可以插入到代碼的任意位置。 引用頭文件：在代碼開頭寫“#include <頭文件名>”。如果想引用自己的頭文件，需要把尖括號（表示只從系統目錄搜索頭文件）換成雙引號（表示先從cpp所在文件夾搜索，然后再到系統文件夾搜索）。 命名空間：很多C+的東西都要引用std命名空間，所以代碼中會有“using namespace std;”。 main()：所有程序都要從main(

16、)開始。在所有的算法競賽中，main()的返回值必須是0，否則視為程序異常結束，得分為0分。 語句和語句塊：1. 語句：一般情況下，一條語句要用一個分號“;”結束。為了美觀和可讀性，可以把一條語句擴展成幾行，也可以把多個語句寫到同一行上。2. 語句塊：用“”和“”包圍的代碼是語句塊。無論里面有多少代碼，在原則上，語句塊所在的整體都視為一條語句。(2) 選擇結構1. if語句：if表示判斷。如果條件為真，就執行接在if后的語句（語句塊），否則執行else后的語句（語句塊）。如果沒有else，就直接跳過。if有以下幾種格式：if (條件)/ 如果條件成立，就執行if后面的語句或語句塊。語句或語句塊

17、if (條件)/ 如果條件成立，就執行if后面的A，否則執行B。語句或語句塊Aelse語句或語句塊Bif (條件1)/ 實際上，這是if語句內的if語句，即if的嵌套。所以else和if中間要有空格。語句或語句塊Aelse if (條件2)語句或語句塊Belse語句或語句塊N2. switch語句：switch表示選擇。它根據條件的不同取值來執行不同的語句。格式如下：switch (表達式)case 值1:代碼段Abreak;case 值2:代碼段Bbreak;default:代碼段Nbreak;如果表達式的值是值1，就執行代碼段A；如果表達式的值是值2，就執行代碼段B否則執行代碼段N。注意：

18、 default一部分可以省略。 如果不使用break，那么緊隨其后的case部分代碼也會被執行，直到遇到break或switch語句結束為止！ switch結尾要有一個分號。3. if、switch都可以嵌套使用。【問題描述】輸入一個日期，判斷它所在年份是否為閏年，并輸出所在月份的天數。閏年的判斷方法：四年一閏，百年不閏，四百年又閏。int year,month,day;bool b=false;cin>>year>>month>>day;/ 判斷是否為閏年if (n%400=0)b=true;else if (n%100!=0 && n%

19、4=0)b=true;if (b)cout<<y<<"是閏年。"<<endl;elsecout<<y<<"不是閏年。"<<endl;/ 判斷所在月份的天數switch (month)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<<&

20、quot;這個月有30天。"<<endl;break;case 2:cout<<"這個月有"<<(b ? 29 : 28)<<"天。"<<endl;break;(3) 循環結構1. while語句：如果條件成立，就繼續循環，直到條件不成立為止。格式如下：while (條件)循環體（語句或語句塊）2. dowhile語句：如果條件成立，就繼續循環，直到條件不成立為止。它與while的最大區別在于，dowhile循環中的語句會被執行至少一次，而while中的語句可能一次都沒有被執行。格式如

21、下：do循環體while (條件);/ 注意分號4. for語句：for分四部分，有初始條件、繼續循環的條件、狀態轉移的條件和循環體。格式如下：for (初始條件; 繼續循環的條件; 狀態轉移的條件)循環體轉換成while循環，即：初始條件while (繼續循環的條件)循環體狀態轉移for后三個條件不是必需的，可以省略不寫，但分號必須保留。5. 在循環語句內部使用break，可以跳出循環；使用continue，可以忽略它后面的代碼，馬上進入下一輪循環。注意，這兩個語句只對它所在的一層循環有效。6. 寫for循環時，一定要注意： 不要把計數器的字母打錯，尤其是在復制/粘貼一段代碼的時候。 根據算

22、法要明確不等號是“<”、“>”，還是“<=”、“>=”。 逆序循環時，不要把自減“-”寫成自增“+”！【問題描述】輸入n，輸出n!（n!1×2×3×4××n）。結果保證小于long long的范圍。當輸入值為負數時結束程序。int n;long long r=1;cin>>n;while (n>-1)r=1;for (int i=1; i<=n; i+)r*=i;cout<<n<<"! = "<<r<<endl;cin>&g

23、t;n;(4) goto語句goto語句用于無條件跳轉。要想跳轉，首先要定義標簽（在代碼開頭的一段標識符，后面緊跟冒號），然后才能goto那個標簽。很多教程不提倡使用無條件跳轉，因為它破壞了程序結構，還容易給代碼閱讀者帶來麻煩。不過，這不代表goto沒有使用價值。goto的一個用途是跳出多層循環：for (int i=0; i<9; i+)for (int j=0; j<9; j+)for (int k=0; k<9; k+)if (滿足某種條件) goto _exited;_exited:(5) C與C+的區別C+語言是以C語言為基礎開發出來的，C語言的大多數內容被保留了下

24、來。在信息學競賽領域，很多情況下C和C+可以互相轉化，甚至不用對代碼進行任何修改。下面是信息學競賽領域中C和C+的重要區別： C+支持用流輸入輸出，而C只能用scanf和printf再見了，%d！ C+非常支持面向對象編程，而C已經“out”了。資料中的“高精度算法”就只能用C+完成，因為在struct內定義了成員函數。C+可以用更強大的string類處理字符串，而不必擔心發生某些低級錯誤。 C+有強大的STL，而C沒有（有一個小小的qsort和bsearch算是補償了）。STL是很多人從C轉到C+的重要原因。 C的頭文件名仍然可以用在C+中，不過可能會收到警報應該去掉“.h”，前面再加一個“

25、c”。如<stdio.h>應該改成<cstdio>。 C程序運行速度稍優于C+。不過也沒快多少。總之，C能做的一切事情，C+也能做；C+能做的一切事情，C不一定能做。1.2數據類型(1) 基本數據類型名稱占用空間別名數據范圍int4signed, signed int,long, long int2,147,483,6482,147,483,647unsigned int 一般都使用有符號整數，除非范圍不夠大，或者你確定你的減法運算不會出現“小數減大數”。4unsigned, unsignedlong,unsigned long int04,294,967,295cha

26、r1char128127unsigned char1unsigned char0255short 一般來說，使用int、long long更保險一些，除非內存不夠用。2short int,signed short int32,76832,767unsigned short2unsigned short int065,535long long 不要使用“_int64”！它是Visual C+特有的關鍵字。8signed long long9,223,372,036,854,775,8089,223,372,036,854,775,807 假如a是long long類型，把超過231的值賦給它時要

27、使用字面值LL（ULL）：a=123456789012345LL。unsigned long long8018,446,744,073,709,551,615bool1true或falsechar1128127signed char1128127unsigned char10255float43.4E +/- 38 (7位有效數字)double8long double1.7E +/- 308 (15位有效數字)(2) 變量與常量1. 定義變量：“變量類型 標識符”，如“int i;”定義了一個名字為i的整型變量。注意，此時i并未初始化，所以i的值是不確定的。2. 定義常量：“const 變量類

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

29、2、b10b42。訪問某個元素時要用兩個方括號，如b21。多維數組的定義和使用方法與此類似。3. 數組名和元素的尋址：以上面的a、b為例 數組名是一個指針，指向整個數組第一個元素所在的地址。如a就是&a0、b就是&b00。 多維數組的本質是數組的數組，所以b0實際上是b00、b01的數組名，b0就是&b00。 在內存中，數組中每個元素都是緊挨著的，所以可以直接進行指針的運算。如a+3就是&a3，*(b+1)就是b10，*(*(b+3)+2)就是b32。 在競賽中要盡可能回避這些功能。4. 字符串： 字符串實際上是char的數組。 字符串最后一位必須是'0

30、'，否則會在進行輸出、使用字符串函數時發生意外。 數組，包括字符串，不可以整體地賦值和比較。如果需要，應使用memcpy和memcmp（字符串是strcpy和strcmp）。5. C+中數組的下標只能從0開始（當然可以閑置不用），并且int a10中a的最后一個元素是a9，不是a10！6. C+不檢查數組下標是否越界！如果下標越界，程序很有可能會崩潰！(4) 指針1. 取地址運算符和取值運算符： 取地址運算符“&”：返回變量所在的地址。一般用于變量。（而數組名本身就是指針，無需“&”） 取值運算符“*”：返回地址對應的值，或用于改變指針所指內存空間的值。只能用于指針。2

31、. 指針的意義：保存另一個變量的內存地址。3. 定義指針：int *p;定義多個指針時，每個字母的前面都要有“*”。注意，如果p沒有被初始化，它就會指向一個未知的內存空間，而錯誤地操作內存會導致程序崩潰！4. 指針使用實例：int a = 0, b = 1; int c = 1,2,3,4,5,6,7,8,9,10;int *p;/ 定義一個指針p=&a;/ 讓p指向a(*p)=3;/ 相當于a=3(*p)=b;/ 相當于a=b，此時a等于1/ p=b;/ 非法操作，左邊是int *，右邊是int，類型不匹配。p=&b;/ 讓p指向b，從此p和a沒關系了p=c+6;/ 讓p指向

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

33、，如果頻繁調用f02，也可以用引用節省篇幅，提高代碼可讀性。引用與指針不同。引用被創建的同時也必須被初始化，并且必須與合法的存儲單元關聯。一旦引用被初始化，就不能改變引用的關系。而指針可以不立刻初始化，也可以改變所指向的內存空間。(6) 結構體 結構體用struct定義。例如下面代碼定義了一個叫pack的結構體，它有兩個成員，一個叫value，另一個叫weight。struct packint value, weight; 變量可以定義成上面的pack類型：pack p;/ 不必寫成struct pack p; 訪問pack的成員時，用“.”運算符（指針變量用“->”）：p.value、

34、(&p)->value C+中結構體可以像類一樣建立自己的構造函數、成員函數，也可以重載運算符。 對于pack這個結構體，它的內部不允許再有pack類型的成員，但是可以有pack類型的指針。1.3運算符(1) 運算符的優先級運算符結合方式:無.（對象成員） ->（指針） （數組下標） ()（函數調用）從左向右+ - (typecast)（強制類型轉換） sizeof ! +（一元） -（一元）*（取值運算符） &（取地址運算符） new delete從右向左.* ->*從左向右* / %（取余數）從左向右+ -從左向右<<（左移） >>

35、（右移）從左向右< <= > >=從左向右=（判斷相等） !=（判斷不等）從左向右&（按位與）從左向右（異或）從左向右|（按位或）從左向右&&（條件與）從左向右|（條件或）從左向右?:（條件運算符）從右向左= *= /= %= += -= &= = >>= <<=從右向左,從左向右(2) 常用運算符的作用1. 算術運算符：+、-、*、/、%分別表示加、減、乘、除、取余。兩個整數做除法時，如果除不開，程序將把小數部分直接截斷（不是四舍五入）。即：整數/整數整數，浮點數/浮點數浮點數。學習過其他語言的同學要注意，C+中

36、沒有乘方運算符，“”也不是乘方運算符。2. 比較運算符： >、>=、<、<=、=（相等）、!=（不等）用來判斷不等關系，返回值是true或false。小心，千萬不要把“=”寫成“=”！ 永遠不要對浮點數使用=和!=運算符！正確的做法是：const double eps = 0.000001;/ 自己控制精度if (d>=2-eps && d<=2+eps) / 相當于if (d=2) 不應該判斷一個變量的值是否等于true。安全的做法是判斷它是否不等于false。3. 位運算： &、|、分別表示按位與、按位或、按位異或，即兩個操作數上

37、每一個二進制位都要進行運算。 表示按位求反。 <<、>>表示二進制位的移動。當某一位數字移動到二進制位的外面之后，它就直接“消失”了。a<<n相當于a×2n，a>>n相當于a÷2n。4. 邏輯運算符： &&、|、分別表示與、或、異或。!表示非。 ?:是條件運算，它是C+唯一一個三目運算符。它的格式如下：A ? B : C。如果A不為false，那么返回B，否則返回C。可以將這個運算符理解為一個簡化版的if。 |、&&、?:是短路運算符 例如計算“a && b”，如果a為false

38、，那么實際上結果就是false不管b是什么，程序都不再計算了。不要在這三種運算符內調用函數或賦值，以免發生難以查出的錯誤！5. 比較運算符、位移運算符、邏輯運算符、條件運算符的優先級較低，所以使用時要多加括號，以防出錯。6. 自增（+）、自減（-）運算符： 增量分別是1和-1。 這兩種運算符只能用于數值類型的變量，不能用于非數值類型變量、常量、表達式和函數調用上。 前綴+、-和后綴+、-的作用效果不同：int i=0, j=8, k=5;j = j + (+i);/ i先自增，變成1，然后再和j相加。執行之后i=1，j=9。k = k + (i+);/ i先和k相加，使k=6。然后i再自增。執

39、行之后i=2，k=6。 前綴運算符返回引用類型，后綴運算符返回數值類型。 為了避免錯誤，不要讓+、-和其他能夠改變變量的操作在同一行出現！7. 賦值運算符： 在C+中賦值是一種運算符。所以你會看到i=j=0、dx=y、return c=i+j之類的代碼。 +=、-=、*=、可以簡化書寫。例如a*=2+3相當于a=a*(2+3)。(3) 真值表pqp && q (p & q)p | q (p | q)p q!p (p)true (1)true (1)true (1)true (1)false (0)false (0)true (1)false (0)false (0)tr

40、ue (1)true (1)false (0)false (0)true (1)false (0)true (1)true (1)true (1)false (0)false (0)false (0)false (0)false (0)true (1)(4) 類型強制轉換用一對小括號把數據類型包上，則它右側的變量或常量的值（變量本身不變）就變成了對應的類型。如：int i=2;float c=6.4/(float)i;/ 把i的值變成float類型。兩個操作數進行四則運算，如果想保留小數位，那么兩個操作數應該都是浮點數。上面的代碼就是這樣。1.4函數(1) 定義和使用函數1. 定義和調用函數：

41、下面定義了一個函數，返回值是double類型的，其中有兩個參數i、j，分別是int和float類型的。double foo(int j, float j) 如果函數不需要返回任何值，可定義為void類型。 函數的定義必須在函數調用的前面。只有在前面添加了函數定義，才能把具體實現放到調用的后面：double foo(int, float);/ 放到調用之前2. 返回值：return 值; 函數是void類型的，那么return后面除了分號，什么都不跟。 調用之后，函數立刻結束。 不可以直接對函數名賦值（學過Pascal或Basic語言的同學要特別注意）。3. 如果你的函數需要返回指針或引用，你必

42、須注意：不要引用函數內部的變量！因為函數一結束，函數內部的變量就煙消云散，不復存在了。正確做法是引用靜態變量（static）或全局變量。4. 內聯函數（inline）：當一個函數內部只有寥寥幾句時，如“華氏度變攝氏度”，可以考慮將其定義成內聯函數，通知編譯器省略函數入棧等操作，直接展開函數內容，以加快運行速度。inline int FtoC(int f) return (f-32)/9*5; (2) 傳遞實參1. 按值傳遞：例如int foo(int n)，在調用foo時，程序會把參數復制一份給n。這樣，對n的任何修改都不會反映到調用foo的參數上面。對于按值傳遞數組，一定要慎重。因為復制數組

43、的元素要浪費很多時間。2. 傳遞指針：例如int foo(int *n)。對n的修改會反映到調用foo的參數上面。 修改n的值時要注意，必須用取值運算符，否則改變的是n指向的內存空間 使用const可防止n指向的內存空間發生改變：int foo(const int *n)。這時再寫n=5之類的語句會被報錯。 此外，這種方法可以用于傳遞數組調用時只需把數組名作為參數。這時不需要取值運算符。3. 傳遞引用：例如int foo(int &n)。優點是既可以直接修改調用foo的參數，又不會帶來指針的麻煩（無需取值運算符）。缺點是不能傳入常數或表達式。1.5輸入和輸出!(1) 使用標準輸入/輸出

44、頭文件：<cstdio>變量約定：FILE *fin, *fout;fin、fout分別代表輸入文件和輸出文件。把它們換成stdin和stdout，就是從屏幕輸入和從屏幕輸出。“1.5 字符串操作”也使用了同樣的變量。1. 輸出字符串或變量的值：printf("格式字符串", );或fprintf(fout, "格式字符串", );格式字符：“%”后連接一個字母。字符含義字符含義d整數 在Windows下調試時，用“%I64d”輸出long long類型的值。交卷時，由于用Linux測試，要改成“%lld”。e, E用科學記數法表示的浮點數u

45、無符號整數f浮點數o八進制整數c字符x, X十六進制整數（小寫、大寫）s字符串（字符數組）常見的修飾符： %5d：5位數，右對齊。不足5位用空格補齊，超過5位按實際位數輸出。 %-5d：5位數，左對齊。不足5位用空格補齊，超過5位按實際位數輸出。 %05d：5位數，右對齊。不足5位用'0'補齊，超過5位按實際位數輸出。 %+d：無論是正數還是負數，都要把符號輸出。 %.2f：保留2位小數。如果小數部分超過2位就四舍五入，否則用0補全。1. 輸入到變量 讀取不含空白的內容：scanf("格式字符串", &);或fscanf(fin, "格式字

46、符串", &); 格式字符和printf基本一致。 不要忘記“&”！printf傳的是值，scanf傳的是地址！ scanf和fscanf的返回值是：成功輸入的變量個數。fscanf返回EOF，表示文件結束。 scanf和fscanf忽略TAB、空格、回車。遇到這些字符它們就停止讀取。 讀取單個字符：fgetc(fin); 首先要判斷它是否為EOF（文件結束）。如果不是，就可以用強制類型轉換變成char。讀取到行末時，要注意對換行符的處理。 Windows、Linux、Mac的回車字符是不同的。Linux是'n'，Mac是'r'，Win

47、dows下是兩個字符'r'和'n'。(2) 使用流輸入/輸出頭文件：<iostream>1. 輸入到變量：cin>>n;2. 輸出到屏幕上：cout<<a;可以連續輸入、輸出，如cin>>n>>m; cout<<a<<','<<b<<endl;3. 換行：cout<<endl;4. 格式化輸出：頭文件：<iomanip> 右對齊，長度為n，不足的部分用空格補齊：cout.width(n);cout.fill('

48、; ');/ 如果想用“0”補齊，就可以把空格換成“0”cout<<a;前兩行代碼，每次輸出之前都要調用。 輸出成其他進位制數：8： cout<<oct<<a;16： cout<<hex<<a;其他進位制需要自己轉換。5. 注意，數據規模很大時，流的輸入輸出速度會變得很慢，甚至數據還沒讀完就已經超時了。在進行輸入輸出之前加入這樣一條語句：ios:sync_with_stdio(false);調用之后，用cin、cout輸入輸出的速度就和scanf、printf的速度一樣了。1.6其他常用操作!本資料常用的頭文件：<ios

49、tream>、<cstdlib>、<cstring>、<fstream>以及<algorithm>、<stack>、<queue>、<vector>等。C+的流、容器、算法等都需要引用std命名空間。所以需要在#include后面、你的代碼前面加上一句：using namespace std;(1) 庫函數1. 數組的整體操作：頭文件：<cstring> 將a初始化：memset(a, 0, sizeof(a);第二個參數應該傳入0、-1或0x7F。傳入0或-1時，a中每個元素的值都是0或-1

50、；如果傳入0x7F時，那么a中每個元素的值都是0x7F7F7F7F（不是0x7F！），可認為是“無窮大”。 將a整體復制到b中：memcpy(b, a, sizeof(a); 判斷a和b是否等價：memcmp(a, b, sizeof(a);/ 返回0表示等價2. 字符操作：頭文件：<cctype> tolower(c)、toupper(c)：將c轉化為小寫或大寫。 isdight(c)、isalpha(c)、isupper(c)、islower(c)、isgraph(c)、isalnum(c)：分別判斷c是否為十進制數字、英文字母、大寫英文字母、小寫英文字母、非空格、字母或數字。

51、3. 最大值/最小值：頭文件：<algorithm>max(a,b)返回a和b中的最小值，min(a,b)返回a和b中的最大值。其實我們可以自己寫：4. 交換變量的值：swap(a,b)頭文件：<algorithm>其實我們可以自己寫：inline void swap(int &a, int &b) int t=a; a=b; b=t; 5. 執行DOS命令或其他程序：system("命令行"); 頭文件：<cstdlib> 暫停屏幕：system("pause"); 競賽交卷或OJ提交代碼之前必須刪除

52、system，否則會被視為作弊（如果是tyvj甚至都無法提交）。 如果使用輸入重定向，那么命令提示符不會接受任何鍵盤輸入直接用文件內容代替鍵盤了。6. 立刻退出程序：exit(0);這種方法常用于深度優先搜索。執行后，程序立刻停止并返回0，所以在調用前應該輸出計算結果。頭文件：<cstdlib>7. 計時：double a = (double)clock() / (double)CLOCKS_PER_SEC;上面的a對應一個時刻。而將兩個時刻相減，就是時間間隔。可用這種方法卡時。頭文件：<ctime>8. 斷言：assert(條件) 條件為假時，程序立刻崩潰。 頭文件：

53、<cassert> 如果定義了NDEBUG符號，那么它將不會起任何作用。 斷言和錯誤處理不同：例如出現“人數為負數”的情況，如果責任在于用戶，那么應該提示錯誤并重新輸入，而不是用斷言；如果發生在計算過程，應該用斷言來使程序崩潰，以幫助改正代碼中的錯誤。換句話說，錯誤處理防的是用戶的錯誤，斷言防的是代碼的錯誤。9. 快速排序：qsort(首項的指針, 待排序元素個數, 每個元素所占字節, 比較函數) 頭文件：<cstdlib> 這是留給C黨的快速排序，它比STL的排序算法啰嗦一些。 比較函數返回int類型，用于對兩個元素的比較。原型如下：int compare(const

54、 void *i, const void *j);如果*i*j，則應返回一個小于0的數；如果*i=*j則應返回0，否則返回一個大于0的數。10. 隨機數發生器： 頭文件：<cstdlib> 產生隨機數： 032767的隨機數：rand() 粗略地控制范圍：rand()%范圍 注意，這種方法產生的隨機數的分布是不均勻的。 精確地控制范圍：(double)rand()/RAND_MAX*范圍 控制在a, b)之間：a + (int) (double)rand()/RAND_MAX*(b-a) 初始化隨機數種子： srand(數字)：初始化隨機數種子。 注意，這條語句在程序開頭使用，并且最多用一次。同一程序、同一平臺，srand中的參數相等，用rand()產生的隨機數序列相同。