本書知識點分類及說明　1

第1章　2009年中山大學內部選拔賽第一試試題分析　4
1.1　斐波那契裝箱問題(難度：★☆☆☆☆)　4
1.1.1　問題描述　4
1.1.2　算法分析　5
1.1.3　參考程序　5
1.1.4　部分測試數據和輸出結果　7
1.2　箭頭識別(難度：★★★☆☆)　8
1.2.1　問題描述　8
1.2.2　算法分析　9
1.2.3　參考程序　10
1.2.4　部分測試數據和輸出結果　13
1.3　選數問題(難度：★★☆☆☆)　14
1.3.1　問題描述　14
1.3.2　算法分析　15
1.3.3　參考程序　15
1.3.4　部分測試數據和輸出結果　17
1.4　下樓問題(難度：★★☆☆☆)　18
1.4.1　問題描述　18
1.4.2　算法分析　19
1.4.3　參考程序　20
1.4.4　部分測試數據及輸出結果　21
1.5　最大空立方體問題(難度：★★★★☆)　22
1.5.1　問題描述　22
1.5.2　算法分析　23
1.5.3　參考程序　24
1.5.4　部分測試數據及輸出結果　31

第2章　2009年中山大學內部選拔賽第二試試題分析　32
2.1　金屬收集(難度：★★★☆☆)　32
2.1.1　問題描述　32
2.1.2　算法分析　33
2.1.3　參考程序　34
2.1.4　部分測試數據及輸出結果　37
2.2　樹的修改(難度：★★★★★)　38
2.2.1　問題描述　38
2.2.2　算法分析　39
2.2.3　參考程序及程序實現　40
2.2.4　部分測試數據及輸出結果　50
2.3　防水綠壩(難度：★★☆☆☆)　52
2.3.1　問題描述　52
2.3.2　算法分析　53
2.3.3　參考程序　54
2.3.4　部分測試數據及輸出結果　55
2.4　救火問題(難度：★★★★☆)　56
2.4.1　問題描述　56
2.4.2　算法分析　57
2.4.3　參考程序　59
2.5　樹的度數序列(難度：★★☆☆☆)　62
2.5.1　問題描述　62
2.5.2　算法分析　63
2.5.3　參考程序　64

第3章　2009年中山大學內部選拔賽第三試試題分析　66
3.1　前K個排列問題(難度：★★☆☆☆)　66
3.1.1　問題描述　66
3.1.2　算法分析　67
3.1.3　參考程序　68
3.2　統計矩形內點數(難度：★★★★☆)　70
3.2.1　問題描述　70
3.2.2　算法分析　71
3.2.3　參考程序　72
3.3　工程分配問題(難度：★★★★☆)　79
3.3.1　問題描述　79
3.3.2　算法分析　80
3.3.3　參考程序　82
3.4　《工程分配問題》評測程序的設計(難度：★★☆☆☆)　92
3.4.1　問題描述　92
3.4.2　算法分析　94
3.4.3　參考程序　94
3.5　向量分解問題(難度：★★★★☆)　96
3.5.1　問題描述　96
3.5.2　算法分析　97
3.5.3　參考程序　98

第4章　2009年中山大學內部選拔賽第四試試題分析　102
4.1　矩形擺放問題(難度：★★★☆☆)　102
4.1.1　問題描述　102
4.1.2　算法分析　103
4.1.3　參考程序及算法實現　105
4.2　簡單數論問題(難度：★★☆☆☆)　110
4.2.1　問題描述　110
4.2.2　算法分析　111
4.2.3　參考程序　111
4.3　護士工作安排問題(難度：★★★☆☆)　114
4.3.1　問題描述　114
4.3.2　算法分析　115
4.3.3　參考程序　116
4.4　“卡蛋島”問題(難度：★★★★☆)　119
4.4.1　問題描述　119
4.4.2　算法分析　120
4.4.3　參考程序　122
4.5　宿舍搬運問題(難度：★★★★☆)　127
4.5.1　問題描述　127
4.5.2　算法分析　129
4.5.3　參考程序　130

第5章　2009年中山大學內部選拔賽第五試試題分析　135
5.1　加邊(難度：★★★☆☆)　135
5.1.1　試題　135
5.1.2　題目分析和算法實現　136
5.1.3　參考程序及程序分析　136
5.1.4　部分測試數據和輸出結果　140
5.2　比特(難度：★★★☆☆)　141
5.2.1　試題　141
5.2.2　題目分析和算法實現　142
5.2.3　參考程序及程序分析　143
5.2.4　部分測試數據和輸出結果　146
5.3　循環小數(難度：★★☆☆☆)　146
5.3.1　試題　146
5.3.2　題目分析和算法實現　147
5.3.3　參考程序及程序分析　147
5.3.4　部分測試數據和輸出結果　148
5.4　星(難度：★★★☆☆)　149
5.4.1　試題　149
5.4.2　題目分析和算法實現　150
5.4.3　參考程序及程序分析　150
5.4.4　部分測試數據和輸出結果　154
5.5　插入(難度：★★★☆☆)　155
5.5.1　試題　155
5.5.2　題目分析和算法實現　156
5.5.3　參考程序及程序分析　156
5.5.4　部分測試數據和輸出結果　161

第6章　2009年中山大學內部選拔賽第六試試題分析　162
6.1　計算機程序設計競賽藝術(難度：★★☆☆☆)　162
6.1.1　試題　162
6.1.2　題目分析和算法實現　164
6.1.3　參考程序及程序分析　164
6.1.4　部分測試數據和輸出結果　166
6.2　ICTOP問題(難度：★★☆☆☆)　168
6.2.1　試題　168
6.2.2　題目分析和算法實現　168
6.2.3　參考程序及程序分析　169
6.2.4　部分測試數據和輸出結果　170
6.3　航道(難度：★★★☆☆)　171
6.3.1　試題　171
6.3.2　題目分析和算法實現　172
6.3.3　參考程序及程序分析　173
6.3.4　部分測試數據和輸出結果　174
6.4　貧窮的Z(難度：★★★★★)　175
6.4.1　試題　175
6.4.2　題目分析和算法實現　176
6.4.3　參考程序及程序分析　177
6.4.4　部分測試數據和輸出結果　178
6.5　笨蛋Z(難度：★★★★☆)　179
6.5.1　試題　179
6.5.2　題目分析和算法實現　181
6.5.3　參考程序及程序分析　181
6.5.4　部分測試數據和輸出結果　183

第7章　2010年中山大學內部選拔賽第一試試題分析　185
7.1　小喬(難度：★★★☆☆)　185
7.1.1　題目描述　185
7.1.2　算法分析　186
7.1.3　參考程序　187
7.1.4　部分測試數據和輸出結果　191
7.2　諸葛亮(難度：★★★★★)　192
7.2.1　題目描述　192
7.2.2　算法分析　193
7.2.3　參考程序　194
7.2.4　部分測試數據和輸出結果　201
7.3　陸遜(難度：★★★☆☆)　202
7.3.1　題目描述　202
7.3.2　算法分析　204
7.3.3　參考程序　205
7.3.4　部分測試數據和輸出結果　209
7.4　呂布(難度：★★★★☆)　209
7.4.1　題目描述　209
7.4.2　算法分析　211
7.4.3　參考程序　211
7.4.4　部分測試數據和輸出結果　219
7.5　于吉(難度：★☆☆☆☆)　220
7.5.1　題目描述　220
7.5.2　算法分析　221
7.5.3　參考程序　221
7.5.4　部分測試數據和輸出結果　222

第8章　2010年中山大學內部選拔賽第二試試題分析　223
8.1　異或樹(難度：★★☆☆☆)　223
8.1.1　題目描述　223
8.1.2　算法分析　224
8.1.3　參考程序　224
8.1.4　部分測試數據和輸出結果　226
8.2　異或樹II(難度：★★★☆☆)　227
8.2.1　題目描述　227
8.2.2　算法分析　228
8.2.3　參考程序　228
8.2.4　部分測試數據和輸出結果　232
8.3　找出第K遠節點(難度：★★★★☆)　233
8.3.1　題目描述　233
8.3.2　算法分析　233
8.3.3　參考程序　234
8.3.4　部分測試數據和輸出結果　238
8.4　K圓(難度：★★☆☆☆)　239
8.4.1　題目描述　239
8.4.2　算法分析　240
8.4.3　參考程序　240
8.4.4　部分測試數據和輸出結果　243
8.5　廣告船(難度：★★★☆☆)　244
8.5.1　題目描述　244
8.5.2　算法分析　245
8.5.3　參考程序　246
8.5.4　部分測試數據和輸出結果　249

第9章　2010年中山大學內部選拔賽第三試試題分析　251
9.1　魔法(難度：★★★☆☆)　251
9.1.1　題目描述　251
9.1.2　算法分析　251
9.1.3　參考程序　252
9.1.4　部分測試數據和輸出結果　253
9.2　優美(難度：★★★★☆)　254
9.2.1　題目描述　254
9.2.2　算法分析　255
9.2.3　參考程序　255
9.2.4　部分測試數據和輸出結果　258
9.3　正確(難度：★★★★★)　260
9.3.1　題目描述　260
9.3.2　算法分析　260
9.3.3　參考程序　261
9.3.4　部分測試數據和輸出結果　262
9.4　不平衡(難度：★★☆☆☆)　263
9.4.1　題目描述　263
9.4.2　算法分析　264
9.4.3　參考程序　265
9.4.4　部分測試數據和輸出結果　266
9.5　格雷的疑惑(難度：★★★☆☆)　267
9.5.1　題目描述　267
9.5.2　算法分析　268
9.5.3　參考程序　268
9.5.4　部分測試數據和輸出結果　271

第10章　2010年中山大學內部選拔賽第四試試題分析　272
10.1　X之謎(難度：★★★★☆)　272
10.1.1　題目描述　272
10.1.2　算法分析　273
10.1.3　參考程序　273
10.1.4　部分測試數據和輸出結果　275
10.2　卡片(難度：★★★★☆)　276
10.2.1　題目描述　276
10.2.2　算法分析　277
10.2.3　參考程序　278
10.2.4　部分測試數據和輸出結果　283
10.3　RP路徑(難度：★★★☆☆)　283
10.3.1　題目描述　283
10.3.2　算法分析　284
10.3.3　參考程序　285
10.3.4　部分測試數據和輸出結果　286
10.4　切棍子(難度：★★☆☆☆)　287
10.4.1　題目描述　287
10.4.2　算法分析　288
10.4.3　參考程序　288
10.4.4　部分測試數據和輸出結果　289
10.5　線性尼姆游戲(難度：★★☆☆☆)　290
10.5.1　題目描述　290
10.5.2　算法分析　291
10.5.3　參考程序　291
10.5.4　部分測試數據和輸出結果　292

第11章　2010年中山大學內部選拔賽第五試試題分析　293
11.1　冒泡排序(難度：★★☆☆☆)　293
11.1.1　試題　293
11.1.2　題目分析和算法實現　294
11.1.3　參考程序及程序分析　295
11.1.4　部分測試數據和輸出結果　296
11.2　植物大戰僵尸(難度：★★★★☆)　298
11.2.1　試題　298
11.2.2　題目分析和算法實現　299
11.2.3　參考程序及程序分析　300
11.2.4　部分測試數據和輸出結果　306
11.3　點的匹配(難度：★★★★★)　307
11.3.1　試題　307
11.3.2　題目分析和算法實現　308
11.3.3　參考程序及程序分析　309
11.3.4　部分測試數據和輸出結果　315
11.4　黃昏公主(難度：★★★☆☆)　317
11.4.1　試題　317
11.4.2　題目分析和算法實現　319
11.4.3　參考程序及程序分析　320
11.4.4　部分測試數據和輸出結果　324
11.5　追逐(難度：★★★☆☆)　325
11.5.1　試題　325
11.5.2　題目分析和算法實現　325
11.5.3　參考程序及程序分析　326
11.5.4　部分測試數據和輸出結果　327

第12章　2010年中山大學內部選拔賽第六試試題分析　329
12.1　最長子串(難度：★★☆☆☆)　329
12.1.1　試題　329
12.1.2　題目分析和算法實現　330
12.1.3　參考程序及程序分析　330
12.1.4　部分測試數據和輸出結果　331
12.2　完美數字(難度：★★☆☆☆)　332
12.2.1　試題　332
12.2.2　題目分析和算法實現　333
12.2.3　參考程序及程序分析　334
12.2.4　部分測試數據和輸出結果　337
12.3　求和(難度：★★☆☆☆)　337
12.3.1　試題　337
12.3.2　題目分析和算法實現　338
12.3.3　參考程序及程序分析　339
12.3.4　部分測試數據和輸出結果　344
12.4　精神球(難度：★★★☆☆)　344
12.4.1　試題　344
12.4.2　題目分析和算法實現　345
12.4.3　參考程序及程序分析　346
12.4.4　部分測試數據和輸出結果　348
12.5　瞬移(難度：★★☆☆☆)　348
12.5.1　試題　348
12.5.2　題目分析和算法實現　349
12.5.3　參考程序及程序分析　350
12.5.4　部分測試數據和輸出結果　351

作者簡介　352
參考文獻　354