国际大学生程序设计竞赛例题解7：中山大学ICPC集训队内部选拔赛试题（2005-2006年）（附CD光盘1张）

　　本书试题涉及知识点的说明 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

　　    《国际大学生程序设计竞赛例题解（7）：中山大学ICPC集训队内部选拔赛试题（2005-2006年）》收录了2005-2006年中山大学ICPC集训队内部选拔赛的全部试题、完整的测试数据和答案。为了方便读者学习，《国际大学生程序设计竞赛例题解（7）：中山大学ICPC集训队内部选拔赛试题（2005-2006年）》对每个题目做了详尽的题目分析并详细地讲解其算法实现的原理，同时提供了完善的标准程序及其程序分析。书中提供了基本测试数据，便于读者测试自行完成上述题目的结果。随书附带的光盘存放所有例题完整的测试数据，便于有更多需求的同学利用规模更大的测试数据进行训练和学习。
　　    《国际大学生程序设计竞赛例题解（7）：中山大学ICPC集训队内部选拔赛试题（2005-2006年）》所提供的题目都是原创题，题目构思新颖，内容有趣。所涉及的算法知识面广，基本上覆盖大学计算机类本科专业的所学到的基本算法。
　　    《国际大学生程序设计竞赛例题解（7）：中山大学ICPC集训队内部选拔赛试题（2005-2006年）》可以作为高等院校大学生和研究生准备参加各级国际大学生程序设计竞赛活动的辅导教材和训练题集，也可以作为高等院校研究生和本科高年级学生学习相关课程的参考书，同时还可以作为中学省级及以上信息学奥林匹克优秀选手备战高层次程序设计竞赛的参考用书。