国际大学生程序设计竞赛例题解

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