目　录

本书知识点分类及说明　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