本书试题涉及知识点的说明 1
第1章 2005年中山大学内部选拔赛第一试试题分析 3
1.1 原子核研究（难度：★★★☆☆） 3
1.1.1 试题 3
1.1.2 题目分析与算法实现 4
1.1.3 参考程序与程序分析 6
1.1.4 部分测试数据与输出结果 8
1.2 脑力游戏（难度：★★★★☆） 9
1.2.1 试题 9
1.2.2 题目分析与算法实现 10
1.2.3 参考程序与程序分析 11
1.2.4 部分测试数据与输出结果 13
1.3 循环序列（难度：★★☆☆☆） 14
1.3.1 试题 14
1.3.2 题目分析与算法实现 15
1.3.3 参考程序与程序分析 16
1.3.4 部分测试数据与输出结果 17
1.4 舞王之王（难度：★★★★★） 18
1.4.1 试题 18
1.4.2 题目分析与算法实现 19
1.4.3 参考程序与程序分析 21
1.4.4 部分测试数据与输出结果 28
1.5 Torus大逃亡（难度：★★☆☆☆） 29
1.5.1 试题 29
1.5.2 题目分析与算法实现 30
1.5.3 参考程序与程序分析 31
1.5.4 部分测试数据与输出结果 32
第2章 2005年中山大学内部选拔赛第二试试题分析 33
2.1 主题医院（难度：★★★☆☆） 33
2.1.1 试题 33
2.1.2 题目分析与算法实现 34
2.1.3 参考程序与程序分析 35
2.1.4 部分测试数据与输出结果 37
2.2 带分数问题（难度：★★★☆☆） 38
2.2.1 试题 38
2.2.2 题目分析与算法实现 39
2.2.3 参考程序与程序分析 39
2.2.4 部分测试数据与输出结果 42
2.3 三角形（难度：★★☆☆☆） 43
2.3.1 试题 43
2.3.2 题目分析与算法实现 44
2.3.3 参考程序与程序分析 44
2.3.4 部分测试数据与输出结果 45
2.4 布料相交（难度：★★★★★） 46
2.4.1 试题 46
2.4.2 题目分析与算法实现 48
2.4.3 参考程序与程序分析 48
2.4.4 部分测试数据与输出结果 54
2.5 掘金（难度：★★★★☆） 56
2.5.1 试题 56
2.5.2 题目分析与算法实现 57
2.5.3 参考程序与程序分析 57
2.5.4 部分测试数据与输出结果 61
第3章 2005年中山大学内部选拔赛第三试试题分析 63
3.1 最小差值生成树（难度：★★★☆☆） 63
3.1.1 试题 63
3.1.2 题目分析与算法实现 64
3.1.3 参考程序与程序分析 64
3.1.4 部分测试数据与输出结果 67
3.2 Alice和Bob的几何游戏（难度：★★★☆☆） 67
3.2.1 试题 67
3.2.2 题目分析与算法实现 69
3.2.3 参考程序与程序分析 70
3.2.4 部分测试数据与输出结果 70
3.3 Collatz难题（难度：★★★☆☆） 71
3.3.1 试题 71
3.3.2 题目分析与算法实现 72
3.3.3 参考程序与程序分析 73
3.3.4 部分测试数据与输出结果 76
3.4 直接做吧（难度：★★☆☆☆） 77
3.4.1 试题 77
3.4.2 题目分析与算法实现 78
3.4.3 参考程序与程序分析 78
3.4.4 部分测试数据与输出结果 79
3.5 又是欧几里德（难度：★★★☆☆） 80
3.5.1 试题 80
3.5.2 题目分析与算法实现 81
3.5.3 参考程序与程序分析 81
3.5.4 部分测试数据与输出结果 82
3.6 未来的火车网络建设（难度：★★★★☆） 83
3.6.1 试题 83
3.6.2 题目分析与算法实现 84
3.6.3 参考程序与程序分析 85
3.6.4 部分测试数据与输出结果 88
第4章 2005年中山大学内部选拔赛第四试试题分析 89
4.1 Max的岛屿（难度：★★★☆☆） 89
4.1.1 试题 89
4.1.2 题目分析与算法实现 90
4.1.3 参考程序与程序分析 92
4.1.4 部分测试数据与输出结果 94
4.2 再次是球（难度：★★★☆☆） 96
4.2.1 试题 96
4.2.2 题目分析与算法实现 97
4.2.3 参考程序与程序分析 97
4.2.4 部分测试数据与输出结果 100
4.3 Max的游戏（难度：★★☆☆☆） 100
4.3.1 试题 100
4.3.2 题目分析与算法实现 101
4.3.3 参考程序与程序分析 102
4.3.4 部分测试数据与输出结果 104
4.4 Max的王国（难度：★☆☆☆☆） 105
4.4.1 试题 105
4.4.2 题目分析与算法实现 106
4.4.3 参考程序与程序分析 106
4.4.4 部分测试数据与输出结果 107
4.5 Max的点（难度：★★☆☆☆） 108
4.5.1 试题 108
4.5.2 题目分析与算法实现 109
4.5.3 参考程序与程序分析 110
4.5.4 部分测试数据与输出结果 111
4.6 盗墓者（难度：★★★★☆） 112
4.6.1 试题 112
4.6.2 题目分析与算法实现 115
4.6.3 参考程序与程序分析 116
4.6.4 部分测试数据与输出结果 118
第5章 2006年中山大学内部选拔赛第一试试题分析 119
5.1 数组（难度：★★☆☆☆） 119
5.1.1 试题 119
5.1.2 题目分析与算法实现 120
5.1.3 参考程序与程序分析 120
5.1.4 部分测试数据与输出结果 121
5.2 有趣的游戏（难度：★★☆☆☆） 121
5.2.1 试题 121
5.2.2 题目分析与算法实现 122
5.2.3 参考程序与程序分析 123
5.2.4 部分测试数据与输出结果 123
5.3 乡村公路（难度：★★★☆☆） 124
5.3.1 试题 124
5.3.2 题目分析与算法实现 125
5.3.3 参考程序与程序分析 126
5.3.4 部分测试数据与输出结果 128
5.4 调试（难度：★★★☆☆） 128
5.4.1 试题 128
5.4.2 题目分析与算法实现 129
5.4.3 参考程序与程序分析 131
5.4.4 部分测试数据与输出结果 132
5.5 世界杯2006（难度：★★★☆☆） 133
5.5.1 试题 133
5.5.2 题目分析与算法实现 134
5.5.3 参考程序与程序分析 135
5.5.4 部分测试数据与输出结果 136
第6章 2006年中山大学内部选拔赛第二试试题分析 137
6.1 车（象棋）（难度：★★★☆☆） 137
6.1.1 试题 137
6.1.2 题目分析与算法实现 138
6.1.3 参考程序与程序分析 139
6.1.4 部分测试数据与输出结果 141
6.2 序列（难度：★★☆☆☆） 142
6.2.1 试题 142
6.2.2 题目分析与算法实现 143
6.2.3 参考程序与程序分析 143
6.2.4 部分测试数据与输出结果 145
6.3 树（难度：★★★☆☆） 145
6.3.1 试题 145
6.3.2 题目分析与算法实现 146
6.3.3 参考程序与程序分析 147
6.3.4 部分测试数据与输出结果 148
6.4 虎胆龙威4（难度：★★☆☆☆） 150
6.4.1 试题 150
6.4.2 题目分析与算法实现 151
6.4.3 参考程序与程序分析 151
6.4.4 部分测试数据与输出结果 152
6.5 Alice和Bob（难度：★☆☆☆☆） 153
6.5.1 试题 153
6.5.2 题目分析与算法实现 153
6.5.3 参考程序与程序分析 154
6.5.4 部分测试数据与输出结果 155
第7章 2006年中山大学内部选拔赛第三试试题分析 156
7.1 幻灯片（难度：★★☆☆☆） 156
7.1.1 试题 156
7.1.2 题目分析与算法实现 157
7.1.3 参考程序与程序分析 158
7.1.4 部分测试数据与输出结果 160
7.2 医院规划（难度：★★★★★） 161
7.2.1 试题 161
7.2.2 题目分析与算法实现 162
7.2.3 参考程序与程序分析 163
7.2.4 部分测试数据与输出结果 165
7.3 讨厌转弯的机器人（难度：★★★☆☆） 166
7.3.1 试题 166
7.3.2 题目分析与算法实现 168
7.3.3 参考程序与程序分析 169
7.3.4 部分测试数据与输出结果 171
7.4 导弹发射（难度：★★★★☆） 173
7.4.1 试题 173
7.4.2 题目分析与算法实现 174
7.4.3 参考程序与程序分析 175
7.4.4 部分测试数据与输出结果 177
7.5 最大公约数与最小公倍数（难度：★★★☆☆） 178
7.5.1 试题 178
7.5.2 题目分析与算法实现 179
7.5.3 参考程序与程序分析 180
7.5.4 部分测试数据与输出结果 181
第8章 2006年中山大学内部选拔赛第四试试题分析 183
8.1 两直线的距离（难度：★★★☆☆） 183
8.1.1 试题 183
8.1.2 题目分析与算法实现 184
8.1.3 参考程序与程序分析 186
8.1.4 部分测试数据与输出结果 188
8.2 一次同余方程（难度：★★★☆☆） 189
8.2.1 试题 189
8.2.2 题目分析与算法实现 190
8.2.3 参考程序与程序分析 190
8.2.4 部分测试数据与输出结果 191
8.3 游泳（难度：★☆☆☆☆） 193
8.3.1 试题 193
8.3.2 题目分析与算法实现 194
8.3.3 参考程序与程序分析 195
8.3.4 部分测试数据与输出结果 195
8.4 城市漫步（难度：★★★★☆） 198
8.4.1 试题 198
8.4.2 题目分析与算法实现 199
8.4.3 参考程序与程序分析 200
8.4.4 部分测试数据与输出结果 202
8.5 先序遍历（难度：★★☆☆☆） 204
8.5.1 试题 204
8.5.2 题目分析与算法实现 205
8.5.3 参考程序与程序分析 207
8.5.4 部分测试数据与输出结果 209
第9章 2006年中山大学内部选拔赛第五试试题分析 211
9.1 又是主题医院（难度：★★★★☆） 211
9.1.1 试题 211
9.1.2 题目分析与算法实现 212
9.1.3 参考程序与程序分析 214
9.1.4 部分测试数据与输出结果 215
9.2 卖票（难度：★★☆☆☆） 218
9.2.1 试题 218
9.2.2 题目分析与算法实现 219
9.2.3 参考程序与程序分析 219
9.2.4 部分测试数据与输出结果 220
9.3 碰碰球（难度：★★★☆☆） 222
9.3.1 试题 222
9.3.2 题目分析与算法实现 223
9.3.3 参考程序与程序分析 224
9.3.4 部分测试数据与输出结果 226
9.4 灌水VS抽水（难度：★★☆☆☆） 230
9.4.1 试题 230
9.4.2 题目分析与算法实现 230
9.4.3 参考程序与程序分析 231
9.4.4 部分测试数据与输出结果 233
9.5 下载（难度：★★★☆☆） 235
9.5.1 试题 235
9.5.2 题目分析与算法实现 236
9.5.3 参考程序与程序分析 237
9.5.4 部分测试数据与输出结果 239
第10章 2006年中山大学内部选拔赛第六试试题分析 241
10.1 黑白树（难度：★★★★☆） 241
10.1.1 试题 241
10.1.2 题目分析与算法实现 242
10.1.3 参考程序与程序分析 242
10.1.4 部分测试数据与输出结果 245
10.2 括号表达式（难度：★★★★★） 246
10.2.1 试题 246
10.2.2 题目分析与算法实现 247
10.2.3 参考程序与程序分析 249
10.2.4 部分测试数据与输出结果 250
10.3 跳格游戏（难度：★★★☆☆） 252
10.3.1 试题 252
10.3.2 题目分析与算法实现 253
10.3.3 参考程序与程序分析 254
10.3.4 部分测试数据与输出结果 256
10.4 达·芬奇密码（难度：★★★☆☆） 257
10.4.1 试题 257
10.4.2 题目分析与算法实现 258
10.4.3 参考程序与程序分析 259
10.4.4 部分测试数据与输出结果 262
10.5 城堡（难度：★★★★★） 264
10.5.1 试题 264
10.5.2 题目分析与算法实现 265
10.5.3 参考程序与程序分析 266
10.5.4 部分测试数据与输出结果 272
附录A 中国内地高校参加ACM/ICPC全球总决赛成绩（1997—2010年） 274
附录B 中山大学ACM/ICPC集训队选拔流程图 275
参考文献 276
作者简介 277