为了帮助高等院校的大学生们备战国际大学生程序设计竞赛，帮助他们提高程序设计水平和培养更强的分析问题与解决问题的能力，编写了这套《国际大学生程序设计竞赛例题解》。本书是这套《国际大学生程序设计竞赛例题解》的第七册，编程所用的语言版本是Microsoft Visual C++6.0。全书共分10章，本书收录了2005—2006年中山大学ICPC集训队内部选拔赛的全部试题、完整的测试数据和答案。为了方便读者学习，本书对每个题目作了详尽的题目分析，并详细地讲解其算法实现的原理，同时提供了完善的参考程序及其程序分析，供读者参考。书中提供了基本测试数据，以方便读者测试自行完成上述题目的结果。随书附带的光盘中存放所有例题中完整的测试数据，以便于有更多需求的同学能利用规模更大的测试数据进行训练和学习。读者从附录A中可以看到，中山大学ACM/ICPC队13年来取得不俗的成绩。本书再次公开了中山大学ICPC集训队内部选拔赛的题目和题解，以便加强与读者的交流。在附录B中，介绍了中山大学集训队选拔流程。

本书收录了2005—2006年中山大学ICPC集训队内部选拔赛的全部试题、完整的测试数据和答案。为了方便读者学习，本书对每个题目做了详尽的题目分析并详细地讲解其算法实现的原理，同时提供了完善的标准程序及其程序分析。书中提供了基本测试数据，便于读者测试自行完成上述题目的结果。随书附带的光盘存放所有例题完整的测试数据，便于有更多需求的同学利用规模更大的测试数据进行训练和学习。

本书所提供的题目都是原创题，题目构思新颖，内容有趣。所涉及的算法知识面广，基本上覆盖大学计算机类本科专业的所学到的基本算法。

本书可以作为高等院校大学生和研究生准备参加各级国际大学生程序设计竞赛活动的辅导教材和训练题集，也可以作为高等院校研究生和本科高年级学生学习相关课程的参考书，同时还可以作为中学省级及以上信息学奥林匹克优秀选手备战高层次程序设计竞赛的参考用书。

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