国际大学生程序设计竞赛例题解 4 广东省信息学奥林匹克竞赛试题 2003-2006年PDF电子书下载

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

第1章　GDKOI 2003及GDOI 2003式题选解 4

1.1　最大公共子串（难度：★★☆☆☆） 4

1.1.1 试题 4

1.1.2　题目分析及算法实现 4

1.1.3　参考程序及程序分析 5

1.1.4　测试数据及输出结果 7

1.2　圆桌会议（难度：★★★★☆） 7

1.2.1　试题 7

1.2.2　题目分析及算法实现 8

1.2.3　参考程序及程序分析 8

1.2.4　测试数据及输出结果 12

1.3　可怜的蜘蛛（难度：★★★★☆） 13

1.3.1 试题 13

1.3.2　题目分析及算法实现 15

1.3.3　参考程序及程序分析 15

1.3.4　测试数据及输出结果 19

1.4　星际争霸（难度：★★★★☆） 20

1.4.1　试题 20

1.4.2　题目分析及算法实现 21

1.4.3　参考程序及程序分析 22

1.4.4　测试数据及输出结果 24

1.5　求值（难度：★☆☆☆☆） 25

1.5.1 试题 25

1.5.2　题目分析及算法实现 25

1.5.3　参考程序及程序分析 26

1.5.4　测试数据及输出结果 27

第2章　GDKOI 2004试题选解 28

2.1　石子游戏（难度：★★☆☆☆） 28

2.1.1 试题 28

2.1.2　题目分析及算法实现 29

2.1.3　参考程序及程序分析 29

2.1.4　测试数据及输出结果 29

2.2　汉诺塔（难度：★★☆☆☆） 30

2.2.1　试题 30

2.2.2　题目分析及算法实现 30

2.2.3　参考程序及程序分析 31

2.2.4　测试数据及输出结果 32

2.3　城市统计（难度：★★★☆☆） 32

2.3.1　试题 32

2.3.2　题目分析及算法实现 33

2.3.3　参考程序及程序分析 34

2.3.4　测试数据及输出结果 36

2.4　使命的召唤（难度：★★★★☆） 37

2.4.1　试题 37

2.4.2　题目分析及算法实现 38

2.4.3　参考程序及程序分析 38

2.4.4　测试数据及输出结果 41

2.5　AWP（难度：★★☆☆☆） 41

2.5.1 试题 41

2.5.2　题目分析及算法实现 42

2.5.3　参考程序及程序分析 42

2.5.4　测试数据及输出结果 44

第3章　GDOI 2004式题选解 45

3.1　软件工程（难度：★☆☆☆☆） 45

3.1.1　试题 45

3.1.2　题目分析及算法实现 46

3.1.3　参考程序及程序分析 46

3.1.4　测试数据及输出结果 47

3.2 词法分析程序（难度：★★★☆☆） 47

3.2.1　试题 47

3.2.2　题目分析及算法实现 49

3.2.3　参考程序及程序分析 49

3.2.4　测试数据及输出结果 52

3.3　多项式运算（难度:★★★☆☆） 53

3.3.1　试题 53

3.3.2　题目分析及算法实现 54

3.3.3　参考程序及程序分析 54

3.3.4　测试数据及输出结果 57

3.4　城市规划（难度：★★★★☆） 58

3.4.1　试题 58

3.4.2　题目分析及算法实现 58

3.4.3　参考程序及程序分析 59

3.4.4　测试数据及输出结果 60

3.5　烟花的寿命（难度：★★★★☆） 61

3.5.1　试题 61

3.5.2　题目分析及算法实现 62

3.5.3　参考程序及程序分析 62

3.5.4　测试数据及输出结果 64

3.6 中奖的机率（难度：★★★☆☆） 65

3.6.1 试题 65

3.6.2　题目分析及算法实现 65

3.6.3　参考程序及程序分析 66

3.6.4　测试数据及输出结果 67

3.7　课程的安排（难度：★★★★★） 67

3.7.1 试题 67

3.7.2　题目分析及算法实现 68

3.7.3　参考程序及程序分析 69

37.4　测试数据及输出结果 73

第4章　GDKOI 2005试题解 75

4.1　二叉树（难度：★☆☆☆☆） 75

4.1.1　试题 75

4.1.2　题目分析及算法实现 76

4.1.3　参考程序及程序分析 77

4.1.4　测试数据及输出结果 77

4.2　商人的宣传（难度：★★★☆☆） 78

4.2.1　试题 78

4.2.2　题目分析及算法实现 79

4.2.3　参考程序及程序分析 79

4.2.4　测试数据及输出结果 81

4.3　建立航道（难度：★★★☆☆） 82

4.3.1　试题 82

4.3.2　题目分析及算法实现 82

4.3.3　参考程序及程序分析 84

4.3.4　测试数据及输出结果 85

4.4　打开遗迹之门（难度：★★★★☆） 85

4.4.1　试题 85

4.4.2　题目分析及算法实现 87

4.4.3　参考程序及程序分析 87

4.4.4　测试数据及输出结果 92

4.5　信号分析（难度：★★★☆☆） 93

4.5.1　试题 93

4.5.2　题目分析及算法实现 94

4.5.3　参考程序及程序分析 94

4.5.4　测试数据及输出结果 95

4.6　脱离地牢（难度：★★★☆☆） 96

4.6.1　试题 96

4.6.2　题目分析及算法实现 97

4.6.3　参考程序及程序分析 97

4.6.4　测试数据及输出结果 99

4.7　野外行军（难度：★★★☆☆） 100

4.7.1　试题 100

4.7.2　题目分析及算法实现 101

4.7.3　参考程序及程序分析 101

4.7.4　测试数据及输出结果 102

4.8　国王的勇士（难度：★★★★☆） 103

4.8.1　试题 103

4.8.2　题目分析及算法实现 105

4.8.3　参考程序及程序分析 105

4.8.4　测试数据及输出结果 110

第5章　GDOI 2005试题解 111

5.1　积木分发（难度：★☆☆☆☆） 111

5.1.1　试题 111

5.1.2　题目分析及算法实现 112

5.1.3　参考程序及程序分析 112

5.1.4　测试数据及输出结果 113

5.2　飞越原野（难度：★★★☆☆） 113

5.2.1　试题 113

5.2.2　题目分析及算法实现 114

5.2.3　参考程序及程序分析 115

5.2.4　测试数据及输出结果 117

5.3　山海经（难度：★★★★☆） 117

5.3.1　试题 117

5.3.2　题目分析及算法实现 118

5.3.3　参考程序及程序分析 119

5.3.4　测试数据及输出结果 122

5.4　河床（难度：★★☆☆☆） 122

5.4.1　试题 122

5.4.2　题目分析及算法实现 123

5.4.3　参考程序及程序分析 123

5.4.4　测试数据及输出结果 124

5.5 电路稳定性（难度：★★☆☆☆） 125

5.5.1　试题 125

5.5.2　题目分析及算法实现 125

5.5.3　参考程序及程序分析 126

5.5.4　测试数据及输出结果 127

5.6　寻宝之旅（难度：★★★☆☆） 127

5.6.1　试题 127

5.6.2　题目分析及算法实现 128

5.6.3　参考程序及程序分析 128

5.6.4　测试数据及输出结果 131

5.7　东东的游戏（难度：★★★★★） 131

5.7.1　试题 131

5.7.2　题目分析及算法实现 133

5.7.3　参考程序及程序分析 134

5.7.4　测试数据及输出结果 136

5.8　国王的遗产（难度：★★★★☆） 136

5.8.1　试题 136

5.8.2　题目分析及算法实现 137

5.8.3　参考程序及程序分析 138

5.8.4　测试数据及输出结果 141

5.9　猴子的争斗（难度：★★★☆☆） 141

5.9.1 试题 141

5.9.2　题目分析及算法实现 142

5.9.3　参考程序及程序分析 143

5.9.4　测试数据及输出结果 144

5.10　排序（难度：★★★★☆） 144

5.10.1　试题 144

5.10.2　题目分析及算法实现 145

5.10.3　参考程序及程序分析 145

5.10.4　测试数据及输出结果 147

5.11　双向环形网络（难度：★★★★★） 148

5.11.1　试题 148

5.11.2　题目分析及算法实现 149

5.11.3　参考程序及程序分析 150

5.11.4　测试数据及输出结果 153

5.12 选址（难度：★★★★★） 153

5.12.1　试题 153

5.12.2　题目分析及算法实现 154

5.12.3　参考程序及程序分析 155

5.12.4　测试数据及输出结果 157

第6章　GDKOI 2006试题选解 158

6.1　纪念邮票（难度：★☆☆☆☆） 158

6.1.1　试题 158

6.1.2　题目分析及算法实现 158

6.1.3　参考程序及程序分析 159

6.1.4　测试数据及输出结果 159

6.2　新红黑树（难度：★★★☆☆） 160

6.2.1　试题 160

6.2.2　题目分析及算法实现 160

6.2.3　参考程序及程序分析 161

6.2.4　测试数据及输出结果 162

6.3　破译密文（难度：★★★★☆） 163

6.3.1　试题 163

6.3.2　题目分析及算法实现 164

6.3.3　参考程序及程序分析 165

6.3.4　测试数据及输出结果 168

6.4　单词选择（难度：★★☆☆☆） 168

6.4.1　试题 168

6.4.2　题目分析及算法实现 169

6.4.3　参考程序及程序分析 169

6.4.4　测试数据及输出结果 172

6.5　防御力场（难度：★★★☆☆） 173

6.5.1　试题 173

6.5.2　题目分析及算法实现 174

6.5.3　参考程序及程序分析 174

6.5.4　测试数据及输出结果 176

6.6　速配游戏（难度：★☆☆☆☆） 176

6.6.1　试题 176

6.6.2　题目分析及算法实现 177

6.6.3　参考程序及程序分析 178

6.6.4　测试数据及输出结果 179

第7章　GDOI 2006试题解 180

7.1　伊甸园（难度：★★☆☆☆） 180

7.1.1　试题 180

7.1.2　题目分析及算法实现 181

7.1.3　参考程序及程序分析 182

7.1.4　测试数据及输出结果 183

7.2 比武大会（难度：★★☆☆☆） 183

7.2.1　试题 183

7.2.2　题目分析及算法实现 183

7.2.3　参考程序及程序分析 184

7.2.4　测试数据及输出结果 185

7.3 道路维修（难度：★★★★☆） 185

7.3.1 试题 185

7.3.2　题目分析及算法实现 186

7.3.3　参考程序及程序分析 187

7.3.4　测试数据及输出结果 190

7.4 Lie dice（难度：★★★★☆） 190

7.4.1 试题 190

7.4.2　题目分析及算法实现 192

7.4.3　参考程序及程序分析 192

7.4.4　测试数据及输出结果 195

7.5　亚特兰蒂斯之光（难度：★☆☆☆☆） 196

7.5.1　试题 196

7.5.2　题目分析及算法实现 197

7.5.3　参考程序及程序分析 197

7.5.4　测试数据及输出结果 199

7.6　外星信号（难度：★★★☆☆） 200

7.6.1　试题 200

7.6.2　题目分析及算法实现 200

7.6.3　参考程序及程序分析 201

7.6.4　测试数据及输出结果 203

7.7　排水系统（难度：★★★★★） 204

7.7.1　试题 204

7.7.2　题目分析及算法实现 205

7.7.3　参考程序及程序分析 206

7.7.4　测试数据及输出结果 210

7.8　The kth element（难度：★★★★☆） 211

7.8.1　试题 211

7.8.2　题目分析及算法实现 211

7.8.3　参考程序及程序分析 212

7.8.4　测试数据及输出结果 215

7.9　古文炼成（难度：★★☆☆☆） 215

7.9.1　试题 215

7.9.2　题目分析及算法实现 216

7.9.3　参考程序及程序分析 217

7.9.4　测试数据及输出结果 219

7.10　拯救亚特兰蒂斯（难度：★★★☆☆） 219

7.10.1　试题 219

7.10.2　题目分析及算法实现 221

7.10.3　参考程序及程序分析 221

7.10.4　测试数据及输出结果 223

7.11　最大和（难度：★★★★☆） 224

7.11.1　试题 224

7.11.2　题目分析及算法实现 225

7.11.3　参考程序及程序分析 225

7.11.4　测试数据及输出结果 228

7.12　天降馅饼（难度：★★★★★） 228

7.12.1　试题 228

7.12.2　题目分析及算法实现 229

7.12.3　参考程序及程序分析 229

7.12.4　测试数据及输出结果 232

附录A　GDKOI及GDOI简介 233

附录B　2003—2006年GDOI及GDKOI试题分布 235

参考文献 238

作者简介 239