国际大学生程序设计竞赛例题解 7 中山大学ICPC集训队内部选拔赛试题 2005-2006年PDF电子书下载

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