国际大学生程序设计竞赛例题解 2 广东省大学生程序设计竞赛试题 2003-2005年PDF电子书下载

本书试题涉及知识点的说明 1

第1章 第1届广东省大学生程序设计竞赛暨第6届中山大学程序设计竞赛（2003年）试题分析 3

1.1 学会奖章（简单统计） 3

1.1.1 试题 3

1.1.2 题目分析与算法实现 4

2.6.3 标准程序与程序分析 5

1.1.3 标准程序与程序分析 5

1.1.4 测试数据与输出结果 6

1.2 老师的数字（数论） 7

1.2.1 式题 7

1.2.2 题目分析与算法实现 8

1.2.3 标准程序与程序分析 10

1.2.4 测试数据与输出结果 12

1.3 国际象棋（复杂模拟） 13

1.3.1 试题 13

1.3.2 题目分析与算法实现 20

1.3.3 标准程序与程序分析 22

1.3.4 测试数据与输出结果 36

1.4.1 试题 37

1.4 幻方（数学分析） 37

1.4.2 题目分析与算法实现 39

1.4.3 标准程序与程序分析 40

1.4.4 测试数据与输出结果 41

1.5 工作安排（图论） 42

1.5.1 试题 42

1.5.2 题目分析与算法实现 43

1.5.3 标准程序与程序分析 43

1.5.4 测试数据与输出结果 47

1.6 邮递食物（搜索） 48

1.6.1 试题 48

1.6.3 标准程序与程序分析 50

1.6.2 题目分析与算法实现 50

1.6.4.测试数据与输出结果 53

1.7 谁是赢家（博弈演化为递推） 54

1.7.1 试题 54

1.7.2 题目分析与算法实现 55

1.7.3 标准程序与程序分析 56

1.7.4 测试数据与输出结果 58

1.8 排序算法（排序） 59

1.8.1 试题 59

1.8.2 题目分析与算法实现 60

1.8.3 标准程序与程序分析 60

1.8.4 测试数据与输出结果 62

1.9 TYLY语言（图论） 62

1.9.1 试题 62

1.9.2 题目分析与算法实现 65

1.9.3 标准程序与程序分析 65

1.9.4 测试数据与输出结果 69

1.10.1 试题 70

1.10 工作依赖（图搜索） 70

1.10.2 题目分析与算法实现 71

1.10.3 标准程序与程序分析 71

1.10.4 测试数据与输出结果 73

1.11 总体题目分析与比赛情况 74

1.11.1 题目总结分析 74

1.11.2 比赛情况 74

第2章 第2届广东省大学生程序设计竞赛暨第7届中山大学程序设计竞赛（2004年）试题分析 75

2.1 二进制最大公约数（简单数论） 75

2.1.1 试题 75

2.1.2 题目分析与算法实现 76

2.1.3 标准程序与程序分析 76

2.2.1 试题 79

2.2 船舶停靠（贪心和数据结构设计） 79

2.1.4 测试数据与输出结果 79

2.2.2 题目分析与算法实现 82

2.2.3 标准程序与程序分析 86

2.2.4 测试数据与输出结果 96

2.3 凸边形外壳（凸包） 97

2.3.1 试题 97

2.3.2 题目分析与算法实现 98

2.3.3 标准程序与程序分析 101

2.3.4 测试数据与输出结果 103

2.4 加密（简单模拟） 104

2.4.1 试题 104

2.4.2 题目分析与算法实现 105

2.4.3 标准程序与程序分析 105

2.4.4 测试数据与输出结果 106

2.5 发电站网络（树型动态规划） 107

2.5.1 试题 107

2.5.2 题目分析与算法实现 109

2.5.3 标准程序与程序分析 109

2.5.4 测试数据与输出结果 111

2.6 有趣的游戏（博弈） 112

2.6.1 试题 112

2.6.2 题目分析与算法实现 114

2.6.4 测试数据与输出结果 119

2.7 准备好了吗（简单排序） 119

2.7.1 试题 119

2.7.2 题目分析与算法实现 120

2.7.3 标准程序与程序分析 120

2.7.4 测试数据与输出结果 121

2.8.1 试题 122

2.8 有用的论文（贪心） 122

2.8.2 题目分析与算法实现 123

2.8.3 标准程序与程序分析 124

2.8.4 测试数据与输出结果 127

2.9 税收（数据结构设计） 128

2.9.1 试题 128

2.9.2 题目分析与算法实现 129

2.9.3 标准程序与程序分析 131

2.9.4 测试数据与输出结果 134

2.10 游览珠海校区（简单计算几何） 135

2.10.1 试题 135

2.10.2 题目分析与算法实现 136

2.10.3 标准程序与程序分析 137

2.11 总体题目分析与比赛情况 138

2.11.1 题目总结分析 138

2.10.4 测试数据与输出结果 138

2.11.2 比赛情况 139

第3章 第8届中山大学程序设计竞赛预选赛（2005年）试题分析 140

3.1 兔子（简单递推） 140

3.1.1 试题 140

3.1.2 题目分析与算法实现 141

3.1.3 标准程序与程序分析 141

3.1.4 测试数据与输出结果 142

3.2 任务调度（拓扑排序） 143

3.2.1 试题 143

3.2.2 题目分析与算法实现 145

3.2.3 标准程序与程序分析 146

3.2.4 测试数据与输出结果 148

3.3 大学校区（图论） 149

3.3.1 试题 149

3.3.2 题目分析与算法实现 151

3.3.3 标准程序与程序分析 152

3.3.4 测试数据与输出结果 153

3.4 加油站（解方程组） 154

3.4.1 试题 154

3.4.2 题目分析与算法实现 156

3.4.3 标准程序与程序分析 160

3.4.4 测试数据与输出结果 161

3.5 城市道路（动态规划） 162

3.5.1 试题 162

3.5.2 题目分析与算法实现 163

3.5.3 标准程序与程序分析 164

3.5.4 测试数据与输出结果 166

3.6 森林（简单图论） 166

3.6.1 试题 166

3.6.2 题目分析与算法实现 167

3.6.3 标准程序与程序分析 168

3.6.4 测试数据与输出结果 169

3.7.DNA匹配（字符串匹配） 170

3.7.1 试题 170

3.7.2 题目分析与算法实现 171

3.7.3 标准程序与程序分析 172

3.7.4 测试数据与输出结果 173

3.8 题目总结分析与比赛情况 174

3.8.1 题目总结分析 174

3.8.2 比赛情况 174

第4章 第3届广东省大学生程序设计竞赛暨第8届中山大学程序设计竞赛（2005年）试题分析 175

4.1 放球（递推） 175

4.1.1 试题 175

4.1.2 题目分析与算法实现 176

4.1.3 标准程序及程序分析 177

4.1.4 测试数据与输出结果 178

4.2 房子（简单图论） 179

4.2.1 试题 179

4.2.2 题目分析与算法实现 180

4.2.3 标准程序与程序分析 180

4.2.4 测试数据与输出结果 181

4.3 计算机（贪心＋最小堆） 183

4.3.1 试题 183

4.3.2 题目分析与算法实现 184

4.3.3 标准程序与程序分析 186

4.3.4 测试数据与输出结果 189

4.4 大学排名（动态规划） 190

4.4.1 试题 190

4.4.2 题目分析与算法实现 191

4.4.3 标准程序与程序分析 192

4.4.4 测试数据与输出结果 194

4.5 椭圆相交（微积分） 195

4.5.1 试题 195

4.5.2 题目分析与算法实现 196

4.5.3 标准程序与程序分析 197

4.5.4 测试数据与输出结果 198

4.6 图灵机编程（构造） 199

4.6.1 试题 199

4.6.2 题目分析与算法实现 201

4.6.3 标准程序与程序分析 202

4.6.4 测试数据与输出结果 205

4.7 格雷码（分治） 208

4.7.1 试题 208

4.7.2 题目分析与算法实现 209

4.7.3 标准程序与程序分析 210

4.7.4 测试数据与输出结果 210

4.8.1 试题 212

4.8 英雄（宽度优先搜索） 212

4.8.2 题目分析与算法实现 214

4.8.3 标准程序与程序分析 215

4.8.4 测试数据与输出结果 218

4.9 程序重构（简单模拟） 219

4.9.1 试题 219

4.9.2 题目分析与算法实现 220

4.9.3 标准程序与程序分析 220

4.9.4 测试数据与输出结果 221

4.10 多边形旋转（计算几何） 225

4.10.1 试题 225

4.10.2 题目分析与算法实现 227

4.10.3 标准程序与程序分析 228

4.10.4 测试数据与输出结果 233

4.11.2 比赛情况 235

4.11.1 题目总结分析 235

4.11 总体题目分析与比赛情况 235

第5章 第28届ACM/ICPC国际大学生程序设计竞赛亚洲预赛广州赛区竞赛（2003年）试题分析 236

5.1 原子实验（动态规划） 236

5.1.1 试题 236

5.1.2 题目分析与算法实现 238

5.1.3 标准程序与程序分析 239

5.1.4 测试数据与输出结果 243

5.2 电梯调度计划（动态规划） 245

5.2.1 式题 245

5.2.2 题目分析与算法实现 246

5.2.3 标准程序与程序分析 247

5.2.4 测试数据与输出结果 249

5.3 新围棋游戏（回溯） 251

5.3.1 试题 251

5.3.2 题目分析与算法实现 253

5.3.3 标准程序与程序分析 255

5.3.4 测试数据与输出结果 263

5.4 互联网（模拟） 265

5.4.1 试题 265

5.4.2 题目分析与算法实现 270

5.4.3 标准程序与程序分析 271

5.4.4 测试数据与输出结果 276

5.5 折纸条（计算几何） 278

5.5.1 试题 278

5.5.2 题目分析与算法实现 279

5.5.3 标准程序与程序分析 280

5.5.4 测试数据与输出结果 286

5.6 阶乘之和（简单数学） 287

5.6.1 试题 287

5.6.2 题目分析与算法实现 288

5.6.3 标准程序与程序分析 289

5.6.4 测试数据与输出结果 290

5.7 任务序列（图论） 291

5.7.1 试题 291

5.7.2 题目分析与算法实现 293

5.7.3 标准程序与程序分析 294

5.7.4 测试数据与输出结果 295

5.8 Vivian的问题（数论） 298

5.8.1 试题 298

5.8.2 题目分析与算法实现 299

5.8.3 标准程序与程序分析 300

5.8.4 测试数据与输出结果 302

5.9 总体题目分析与比赛情况 305

5.9.1 题目总结分析 305

5.9.2 比赛情况 306

参考文献 307

作者简介 308