目錄

第1章競(jìng)賽預(yù)備知識(shí)1
1.1C語(yǔ)言常用函數(shù)1
1.1.1字符串?dāng)?shù)值轉(zhuǎn)換函數(shù)1
1.1.2字符串函數(shù)1
1.2STL標(biāo)準(zhǔn)模板庫(kù)3
1.2.1STL算法函數(shù)3
1.2.2STL容器11
第2章基礎(chǔ)題21
2.1窮舉法真題21
【例2��1】（第7屆）抽簽21
【例2��2】（第4屆）買(mǎi)不到的數(shù)目22
【例2��3】（第7屆）四平方和23
【例2��4】（第5屆）拼接平方數(shù)23
【例2��5】（第4屆）帶分?jǐn)?shù)25
2.2中等數(shù)學(xué)真題26
【例2��6】（第13屆）因數(shù)平方和26
【例2��7】（第12屆）和與乘積28
【例2��8】（第12屆）楊輝三角形31
2.3取余真題35
【例2��9】（第8屆）K倍區(qū)間35
【例2��10】（第13屆）取模36
【例2��11】（第13屆）近似GCD37
2.4最大公約數(shù)40
【例2��12】（第11屆）循環(huán)小數(shù)40
【例2��13】（第10屆）等差數(shù)列41
2.5排序真題42
【例2��14】（第13屆）重新排序42
【例2��15】（第14屆）平均45
2.6其他基本類(lèi)型真題47【例2��16】（第6屆）奇怪的數(shù)列47
【例2��17】（第13屆）X進(jìn)制減法49
【例2��18】（第13屆）數(shù)的拆分51
【例2��19】（第14屆）公因數(shù)匹配55
【例2��20】（第14屆）棋盤(pán)58
【例2��21】（第13屆）積木畫(huà)59
【例2��22】（第8屆）小計(jì)算器61
第3章時(shí)間65
【例3��1】（第9屆）航班時(shí)間65
【例3��2】（第11屆）回文日期67
【例3��3】（第8屆）日期問(wèn)題69
第4章字符串71
【例4��1】（第10屆）最長(zhǎng)子序列71
【例4��2】（第6屆）密文搜索72
【例4��3】（第5屆）排列序數(shù)73
【例4��4】（第9屆）等腰三角形74
【例4��5】（第11屆）重復(fù)字符串76
【例4��6】（第11屆）字符串編碼77
【例4��7】（第13屆）內(nèi)存空間79
【例4��8】（第14屆）子串簡(jiǎn)寫(xiě)82
第5章規(guī)律題85
【例5��1】（第9屆）約瑟夫環(huán)85
【例5��2】（第5屆）生物芯片87
【例5��3】（第10屆）數(shù)正方形88
【例5��4】（第14屆）平方差90
【例5��5】（第10屆）后綴表達(dá)式91
第6章二分法95
【例6��1】（第9屆）遞增三元組95
【例6��2】（第14屆）買(mǎi)二贈(zèng)一96
【例6��3】（第8屆二分法）分巧克力98
【例6��4】（第13屆）第K小的和100
【例6��5】（第13屆國(guó)賽）卡牌101
【例6��6】（第11屆）整數(shù)拼接103
【例6��7】（第13屆）統(tǒng)計(jì)子矩陣105
第7章優(yōu)先隊(duì)列與堆棧109
【例7��1】(第15屆)爬山109
【例7��2】（第13屆）砍竹子111
【例7��3】(第14屆)最大開(kāi)支114
【例7��4】(第14屆)整數(shù)刪除117
【例7��5】（第13屆）掃描游戲120
【例7��6】（第8屆）正則問(wèn)題124
第8章基本遞歸127
8.1遞歸引入127
8.2基本例題130
8.3遞歸真題135
【例8��1】（第13屆）最大數(shù)字135
【例8��2】（第4屆國(guó)賽）橫向打印二叉樹(shù)137
第9章圖論141
9.1深度優(yōu)先搜索141
9.2真題分析146
【例9��1】（第4屆）剪格子146
【例9��2】（第7屆）路徑之謎148
【例9��3】（第5屆求割點(diǎn)）危險(xiǎn)系數(shù)150
【例9��4】（第9屆）版本分支152
【例9��5】（第13屆）掃雷155
【例9��6】（第8屆）發(fā)現(xiàn)環(huán)160
9.3寬度優(yōu)先搜索162
9.4真題分析165
【例9��7】（第6屆BFS）穿越雷區(qū)165
【例9��8】（第9屆）變暖167
【例9��9】（第10屆）大胖子走迷宮169
9.5并查集172
9.6真題分析176
【例9��10】（第8屆）合根植物176
【例9��11】（第10屆）修改數(shù)組178
【例9��12】（第13屆）推導(dǎo)部分和180
【例9��13】（第11屆）網(wǎng)絡(luò)分析183
9.7單源最短路徑186
9.7.1Dijkstra算法186
9.7.2SPFA算法188
9.8真題分析191
【例9��14】（第13屆）出差191
【例9��15】（第11屆）限高桿193
9.9最小生成樹(shù)與最近公共祖先197
9.10真題分析203
【例9��16】（第14屆）網(wǎng)絡(luò)穩(wěn)定性203
第10章動(dòng)態(tài)規(guī)劃208
10.1線(xiàn)性動(dòng)態(tài)規(guī)劃208
10.2真題分析208
【例10��1】（第7屆）密碼脫落208
【例10��2】（第12屆）砝碼稱(chēng)重210
【例10��3】（第8屆）包子湊數(shù)211
【例10��4】（第13屆）李白打酒加強(qiáng)版213
【例10��5】（第10屆）包含216
【例10��6】（第14屆）接龍數(shù)列218
10.3區(qū)間動(dòng)態(tài)規(guī)劃219
10.4真題分析224
【例10��7】（第9屆）搭積木224
【例10��8】（第14屆）更小的數(shù)227
【例10��9】（第14屆）合并石子229
10.5樹(shù)形動(dòng)態(tài)規(guī)劃232
10.6真題分析233
【例10��10】（第12屆）左孩子右兄弟233
【例10��11】（第6屆）生命之樹(shù)234
10.7數(shù)位動(dòng)態(tài)規(guī)劃237
10.8真題分析243
【例10��12】（第12屆）二進(jìn)制問(wèn)題243
第11章區(qū)間運(yùn)算算法246
11.1樹(shù)狀數(shù)組246
11.1.1引入246
11.1.2原理246
11.1.3示例分析249
11.2線(xiàn)段樹(shù)254
11.2.1引入254
11.2.2基本操作255
11.2.3示例分析259
11.3ST表269
11.4真題分析271
【例11��1】（第13屆）最大公約數(shù)271
【例11��2】（第5屆）小朋友排隊(duì)274
【例11��3】（第8屆）油漆面積276
第12章數(shù)論281
12.1快速冪取模281
12.1.1遞歸快速冪281
12.1.2遞推快速冪281
12.2矩陣快速冪282
12.3歐拉函數(shù)283
12.4歐拉定理283
12.5擴(kuò)展歐幾里得284
12.6中國(guó)剩余定理285
12.7典型例題286
【例12��1】（第14屆）互素?cái)?shù)的個(gè)數(shù)286
【例12��2】（第5屆）斐波那契288
【例12��3】（第9屆）倍數(shù)問(wèn)題291
第13章計(jì)算幾何294
13.1基礎(chǔ)知識(shí)294
13.2進(jìn)階知識(shí)295
13.2.1求任意多邊形面積295
13.2.2皮克定理296
13.2.3辛普森積分297
【例13��1】（第11屆）平面切分298
【例13��2】（第4屆）車(chē)輪軸跡300
第14章游戲題305
14.1巴什博弈305
14.2尼姆博弈306
14.3真題分析308
【例14��1】（第5屆）矩陣翻硬幣308
【例14��2】（第8屆）填字母游戲309
參考文獻(xiàn)312