國際大學生程序設計競賽中山大學內部選拔真題解（一）

目　錄

本書知識點分類及說明　1
第1章　2007年中山大學內部選拔賽第一試試題分析　4
1.1　計算生成樹(難度：★★☆☆☆)　4
1.1.1　問題描述　4
1.1.2　算法分析　5
1.1.3　參考程序　6
1.1.4　部分測試數(shù)據(jù)和輸出結果　7
1.2　三核苷酸(難度：★★★☆☆)　8
1.2.1　問題描述　8
1.2.2　算法分析　9
1.2.3　參考程序　10
1.2.4　部分測試數(shù)據(jù)和輸出結果　12
1.3　緊急逃離(難度：★★★☆☆)　12
1.3.1　問題描述　12
1.3.2　算法分析　14
1.3.3　參考程序　15
1.3.4　部分測試數(shù)據(jù)和輸出結果　18
1.4　簡單數(shù)謎(難度：★★★☆☆)　21
1.4.1　問題描述　21
1.4.2　算法分析　22
1.4.3　參考程序　23
1.4.4　部分測試數(shù)據(jù)和輸出結果　26
1.5　股票投資(難度：★★★★☆)　28
1.5.1　問題描述　28
1.5.2　算法分析　30
1.5.3　參考程序　31
1.5.4　部分測試數(shù)據(jù)和輸出結果　33
第2章　2007年中山大學內部選拔賽第二試試題分析　35
2.1　新年禮物(難度：★★☆☆☆)　35
2.1.1　問題描述　35
2.1.2　算法分析　36
2.1.3　參考程序　36
2.1.4　部分測試數(shù)據(jù)和輸出結果　37
2.2　遼哥游戲(難度：★★★★★)　37
2.2.1　問題描述　37
2.2.2　算法分析　39
2.2.3　參考程序　40
2.2.4　部分測試數(shù)據(jù)和輸出結果　41
2.3　壓縮后綴數(shù)組(難度：★★☆☆☆)　42
2.3.1　問題描述　42
2.3.2　算法分析　44
2.3.3　參考程序　44
2.3.4　部分測試數(shù)據(jù)和輸出結果　45
2.4　劃分方板(難度：★★★☆☆)　45
2.4.1　問題描述　45
2.4.2　算法分析　46
2.4.3　參考程序　47
2.4.4　部分測試數(shù)據(jù)和輸出結果　48
2.5　終極簡單問題(難度：★★★☆☆)　49
2.5.1　問題描述　49
2.5.2　算法分析　50
2.5.3　參考程序　50
2.5.4　部分測試數(shù)據(jù)和輸出結果　52
第3章　2007年中山大學內部選拔賽第三試試題分析　53
3.1　因子的因子(難度：★★★☆☆)　53
3.1.1　問題描述　53
3.1.2　算法分析　53
3.1.3　參考程序　54
3.1.4　部分測試數(shù)據(jù)和輸出結果　56
3.2　賭神(難度：★★★★★)　57
3.2.1　問題描述　57
3.2.2　算法分析　58
3.2.3　參考程序　59
3.2.4　部分測試數(shù)據(jù)和輸出結果　60
3.3　尋找中點(難度：★★★★☆)　61
3.3.1　問題描述　61
3.3.2　算法分析　62
3.3.3　參考程序　63
3.3.4　部分測試數(shù)據(jù)和輸出結果　66
3.4　德布魯因序列(難度：★★★☆☆)　68
3.4.1　問題描述　68
3.4.2　算法分析　68
3.4.3　參考程序　69
3.4.4　部分測試數(shù)據(jù)和輸出結果　70
3.5　賽馬(難度：★★☆☆☆)　70
3.5.1　問題描述　70
3.5.2　算法分析　71
3.5.3　參考程序　72
3.5.4　部分測試數(shù)據(jù)和輸出結果　73
第4章　2007年中山大學內部選拔賽第四試試題分析　74
4.1　螞蟻征途(難度：★★★★☆)　74
4.1.1　問題描述　74
4.1.2　算法分析　75
4.1.3　參考程序　76
4.1.4　部分測試數(shù)據(jù)和輸出結果　78
4.2　二次同余方程(難度：★★★★★)　79
4.2.1　問題描述　79
4.2.2　算法分析　79
4.2.3　參考程序　80
4.2.4　部分測試數(shù)據(jù)和輸出結果　83
4.3　聚會(難度：★★★☆☆)　83
4.3.1　問題描述　83
4.3.2　算法分析　84
4.3.3　參考程序　85
4.3.4　部分測試數(shù)據(jù)和輸出結果　87
4.4　質數(shù)和式(難度：★★☆☆☆)　87
4.4.1　問題描述　87
4.4.2　算法分析　88
4.4.3　參考程序　89
4.4.4　部分測試數(shù)據(jù)和輸出結果　90
4.5　樹(難度：★★★☆☆)　91
4.5.1　問題描述　91
4.5.2　算法分析　92
4.5.3　參考程序　92
4.5.4　部分測試數(shù)據(jù)和輸出結果　94
第5章　2007年中山大學內部選拔賽第五試試題分析　98
5.1　水池(難度：★★☆☆☆)　98
5.1.1　問題描述　98
5.1.2　算法分析　99
5.1.3　參考程序　99
5.1.4　部分測試數(shù)據(jù)和輸出結果　100
5.2　數(shù)字排序(難度：★★★☆☆)　101
5.2.1　問題描述　101
5.2.2　算法分析　102
5.2.3　參考程序　102
5.2.4　部分測試數(shù)據(jù)和輸出結果　104
5.3　移動(難度：★★★★★)　105
5.3.1　問題描述　105
5.3.2　算法分析　105
5.3.3　參考程序　106
5.3.4　部分測試數(shù)據(jù)和輸出結果　111
5.4　球星(難度：★★★☆☆)　112
5.4.1　問題描述　112
5.4.2　算法分析　113
5.4.3　參考程序　114
5.4.4　部分測試數(shù)據(jù)和輸出結果　117
5.5　不幸運數(shù)(難度：★★★☆☆)　118
5.5.1　問題描述　118
5.5.2　算法分析　119
5.5.3　參考程序　119
5.5.4　部分測試數(shù)據(jù)和輸出結果　122
第6章　2007年中山大學內部選拔賽第六試試題分析　124
6.1　樹的計數(shù)(難度：★★★★☆)　124
6.1.1　問題描述　124
6.1.2　算法分析　124
6.1.3　參考程序　126
6.1.4　部分測試數(shù)據(jù)和輸出結果　130
6.2　九數(shù)碼(難度：★★☆☆☆)　131
6.2.1　問題描述　131
6.2.2　算法分析　132
6.2.3　參考程序　132
6.2.4　部分測試數(shù)據(jù)和輸出結果　134
6.3　數(shù)列(難度：★★★☆☆)　135
6.3.1　問題描述　135
6.3.2　算法分析　136
6.3.3　參考程序　137
6.3.4　部分測試數(shù)據(jù)和輸出結果　141
6.4　國王(難度：★★★☆☆)　142
6.4.1　問題描述　142
6.4.2　算法分析　143
6.4.3　參考程序　143
6.4.4　部分測試數(shù)據(jù)和輸出結果　144
6.5　面積(難度：★★★☆☆)　145
6.5.1　問題描述　145
6.5.2　算法分析　146
6.5.3　參考程序　147
6.5.4　部分測試數(shù)據(jù)和輸出結果　150
第7章　2008年中山大學內部選拔賽第一試試題分析　151
7.1　PPMM(難度：★★★☆☆)　151
7.1.1　問題描述　151
7.1.2　算法分析　152
7.1.3　參考程序　153
7.1.4　部分測試數(shù)據(jù)和輸出結果　155
7.2　三角形計算(難度：★★★★☆)　156
7.2.1　問題描述　156
7.2.2　算法分析　157
7.2.3　參考程序　158
7.2.4　部分測試數(shù)據(jù)和輸出結果　161
7.3　生成字符串(難度：★★★☆☆)　161
7.3.1　問題描述　161
7.3.2　算法分析　162
7.3.3　參考程序　163
7.3.4　部分測試數(shù)據(jù)和輸出結果　164
7.4　翻硬幣(難度：★★★☆☆)　165
7.4.1　問題描述　165
7.4.2　算法分析　166
7.4.3　參考程序　167
7.4.4　部分測試數(shù)據(jù)和輸出結果　169
7.5　又是C(n, m)(難度：★★☆☆☆)　169
7.5.1　問題描述　169
7.5.2　算法分析　170
7.5.3　參考程序　170
7.5.4　部分測試數(shù)據(jù)和輸出結果　172
第8章　2008年中山大學內部選拔賽第二試試題分析　173
8.1　次小生成樹(難度：★★★★★)　173
8.1.1　問題描述　173
8.1.2　算法分析　174
8.1.3　參考程序　175
8.1.4　部分測試數(shù)據(jù)和輸出結果　180
8.2　分寶藏(難度：★★★☆☆)　181
8.2.1　問題描述　181
8.2.2　算法分析　182
8.2.3　參考程序　182
8.2.4　部分測試數(shù)據(jù)和輸出結果　184
8.3　探照燈(難度：★★☆☆☆)　185
8.3.1　問題描述　185
8.3.2　算法分析　185
8.3.3　參考程序　186
8.3.4　部分測試數(shù)據(jù)和輸出結果　188
8.4　數(shù)字識別系統(tǒng)(難度：★★★☆☆)　188
8.4.1　問題描述　188
8.4.2　算法分析　190
8.4.3　參考程序　191
8.4.4　部分測試數(shù)據(jù)和輸出結果　194
8.5　開燈(難度：★★☆☆☆)　194
8.5.1　問題描述　194
8.5.2　算法分析　195
8.5.3　參考程序　196
8.5.4　部分測試數(shù)據(jù)和輸出結果　196
第9章　2008年中山大學內部選拔賽第三試試題分析　197
9.1　最大對稱子數(shù)列(難度：★★★★★)　197
9.1.1　問題描述　197
9.1.2　算法分析　198
9.1.3　參考程序　199
9.1.4　部分測試數(shù)據(jù)和輸出結果　205
9.2　尋寶(難度：★★★★☆)　205
9.2.1　問題描述　205
9.2.2　算法分析　206
9.2.3　參考程序　207
9.2.4　部分測試數(shù)據(jù)和輸出結果　209
9.3　大明王朝(難度：★★☆☆☆)　210
9.3.1　問題描述　210
9.3.2　算法分析　212
9.3.3　參考程序　213
9.3.4　部分測試數(shù)據(jù)和輸出結果　215
9.4　重建長城(難度：★★★☆☆)　216
9.4.1　問題描述　216
9.4.2　算法分析　217
9.4.3　參考程序　217
9.4.4　部分測試數(shù)據(jù)和輸出結果　218
9.5　斯諾克(難度：★★★★★)　219
9.5.1　問題描述　219
9.5.2　算法分析　221
9.5.3　參考程序　222
9.5.4　部分測試數(shù)據(jù)和輸出結果　227
第10章　2008年中山大學內部選拔賽第四試試題分析　229
10.1　度限制生成樹(難度：★★★☆☆)　229
10.1.1　問題描述　229
10.1.2　算法分析　229
10.1.3　參考程序　230
10.1.4　部分測試數(shù)據(jù)和輸出結果　231
10.2　重新分工(難度：★★★★☆)　232
10.2.1　問題描述　232
10.2.2　算法分析　233
10.2.3　參考程序　233
10.2.4　部分測試數(shù)據(jù)和輸出結果　236
10.3　樁(難度：★★★★☆)　236
10.3.1　問題描述　236
10.3.2　算法分析　237
10.3.3　參考程序　238
10.3.4　部分測試數(shù)據(jù)和輸出結果　242
10.4　旅行方案(難度：★★★★☆)　242
10.4.1　問題描述　242
10.4.2　算法分析　243
10.4.3　參考程序　244
10.4.4　部分測試數(shù)據(jù)和輸出結果　248
10.5　最大最短距離(難度：★★★☆☆)　248
10.5.1　問題描述　248
10.5.2　算法分析　249
10.5.3　參考程序　250
10.5.4　部分測試數(shù)據(jù)和輸出結果　252
第11章　2008年中山大學內部選拔賽第五試試題分析　254
11.1　菱形(難度：★★★☆☆)　254
11.1.1　問題描述　254
11.1.2　算法分析　254
11.1.3　參考程序　256
11.1.4　部分測試數(shù)據(jù)和輸出結果　258
11.2　傻瓜式函數(shù)(難度：★★☆☆☆)　259
11.2.1　問題描述　259
11.2.2　算法分析　260
11.2.3　參考程序　260
11.2.4　部分測試數(shù)據(jù)和輸出結果　262
11.3　最大公約數(shù)(難度：★★★☆☆)　262
11.3.1　問題描述　262
11.3.2　算法分析　263
11.3.3　參考程序　264
11.3.4　部分測試數(shù)據(jù)和輸出結果　264
11.4　數(shù)列(難度：★★☆☆☆)　265
11.4.1　問題描述　265
11.4.2　算法分析　266
11.4.3　參考程序　266
11.4.4　部分測試數(shù)據(jù)和輸出結果　267
11.5　間距(難度：★★★☆☆)　268
11.5.1　問題描述　268
11.5.2　算法分析　269
11.5.3　參考程序　269
11.5.4　部分測試數(shù)據(jù)和輸出結果　273
第12章　2008年中山大學內部選拔賽第六試試題分析　274
12.1　猜答案(難度：★★★★☆)　274
12.1.1　問題描述　274
12.1.2　算法分析　275
12.1.3　參考程序　275
12.1.4　部分測試數(shù)據(jù)和輸出結果　278
12.2　A+B問題(難度：★★★☆☆)　278
12.2.1　問題描述　278
12.2.2　算法分析　279
12.2.3　參考程序　280
12.2.4　部分測試數(shù)據(jù)和輸出結果　282
12.3　時間流逝(難度：★★★☆☆)　283
12.3.1　問題描述　283
12.3.2　算法分析　284
12.3.3　參考程序　285
12.3.4　部分測試數(shù)據(jù)和輸出結果　286
12.4　裸題(難度：★★☆☆☆)　286
12.4.1　問題描述　286
12.4.2　算法分析　287
12.4.3　參考程序　288
12.4.4　部分測試數(shù)據(jù)和輸出結果　289
12.5　謎題(難度：★★★☆☆)　289
12.5.1　問題描述　289
12.5.2　算法分析　290
12.5.3　參考程序　291
12.5.4　部分測試數(shù)據(jù)和輸出結果　292
附錄1　中山大學集訓隊選拔流程圖　293
附錄2　中國內地高校參加ACM/ICPC全球總決賽的成績(1997～2012)　294
附錄3　中山大學隊2008～2011年在亞洲區(qū)成績　296
附錄4　中山大學隊1999～2012年在全球總決賽成績　297
作者簡介　298
參考文獻　300