挑战编程 程序设计竞赛训练手册PDF电子书下载

第1章　入门 1

1.1　初识自动评测系统 1

1.1.1　评测系统反馈 1

1.2　挑选你的武器 3

1.2.1　程序设计语言 3

1.2.2　如何阅读本书的程序 4

1.2.3　标准输入输出 5

1.3　编程提示 6

1.4　基本数据类型 8

1.5　关于习题 10

1.6　习题 11

1.6.1　3n+1问题（3n+1 Problem） 11

1.6.2　扫雷（Minesweeper） 12

1.6.3　旅行（The Trip） 13

1.6.4　液晶显示屏（LC-Display） 14

1.6.5　图形化编辑器（Graphical Editor） 15

1.6.6　解释器（Interpreter） 16

1.6.7　将军（Check the Check） 17

1.6.8　澳大利亚投票（Australian Voting） 19

1.7　提示 20

1.8　注解 20

第2章　数据结构 22

2.1　基本数据结构 22

2.1.1　栈 22

2.1.2　队列 23

2.1.3　字典 25

2.1.4　优先队列 26

2.1.5　集合 26

2.2　库函数 27

2.2.1　C＋＋标准模板库 27

2.3　程序设计实例：纸牌大战 28

2.4　准备行动 29

2.5　字符串输入输出 30

2.6　赢得战争 32

2.7　测试与调试 33

2.8　习题 35

2.8.1　快乐的跳跃者（Jolly Jumper） 35

2.8.2　扑克牌型（Poker Hands） 35

2.8.3　罢工（Hartals） 36

2.8.4　解密（Crypt Kicker） 37

2.8.5　完美洗牌术（Stack'em Up） 38

2.8.6 Erd？s数（Erd？s Numbers） 41

2.8.7　比赛记分板（Contest Scoreboard） 42

2.8.8　Yahtzee游戏（Yahtzee） 43

2.9　习题 45

2.10　注解 45

第3章　字符串 47

3.1　字符编码 47

3.2 字符串的表示 49

3.3　程序设计实例：公司更名 49

3.4　模式查找 51

3.5　字符串操作 52

3.6　程序的完成 54

3.7　字符串库函数 54

3.8　习题 56

3.8.1　WERTYU键盘（WERTYU） 56

3.8.2　寻找单词（Where's Waldorf?） 57

3.8.3 公共排列（Common Permutation） 58

3.8.4　解密Ⅱ（Crypt Kicker Ⅱ） 59

3.8.5　自动评测脚本（Automated Judge Script） 60

3.8.6　文件碎片（File Fragmentation） 62

3.8.7　Doublet序列（Doublets） 63

3.8.8　Fmt程序（Fmt） 63

3.9　提示 65

3.10　注解 65

第4章　排序 66

4.1　排序的应用 66

4.2　排序算法 67

4.3　程序设计举例：给绅士排名 69

4.4　与排序相关的库函数 71

4.5　给绅士排名 72

4.6　习题 75

4.6.1　Vito家族（Vito's Family） 75

4.6.2　煎饼堆（Stacks of Flapjacks） 75

4.6.3　过桥（Bridge） 76

4.6.4　最长打盹时间（Longest Nap） 77

4.6.5　鞋匠的烦恼（Shoemaker's Problem） 79

4.6.6　CDVII高速公路（CDVII） 80

4.6.7　龟壳排序（ShellSort） 81

4.6.8　足球（Football（aka Soccer）） 82

4.7　提示 84

4.8　注解 85

第5章　算术与代数 86

5.1　机器算术 86

5.1.1　整数库函数 86

5.2　高精度整数 87

5.3　高精度算术 88

5.4　进制及其转换 94

5.5　实数 96

5.5.1　如何处理实数 97

5.5.2　分数 97

5.5.3　十进制实数 98

5.6　代数 98

5.6.1　多项式运算 98

5.6.2　多项式求根 99

5.7　对数 100

5.8　实数函数库 101

5.9　习题 101

5.9.1　小学生算术（Primary Arithmetic） 101

5.9.2　反转相加（Reverse and Add） 102

5.9.3　考古学家的烦恼（The Archeologist's Dilemma） 103

5.9.4　仅由1组成的数（Ones） 104

5.9.5　乘法游戏（A Multiplication Game） 104

5.9.6　多项式的系数（Polynomial Coefficients） 105

5.9.7　Stern-Brocot代数系统（The Stern-Brocot Number System） 105

5.9.8　两两之和（Pairsumonious Numbers） 106

5.10　提示 107

5.11　注解 108

第6章　组合数学 109

6.1　基本计数技巧 109

6.2　递推关系 110

6.3　二项式系数 111

6.4　其他计数序列 113

6.5　递归与数学归纳法 115

6.6　习题 116

6.6.1　斐波那契计数（How Many Fibs?） 116

6.6.2　土地分割（How Many Pieces of Land?） 116

6.6.3　数数（Counting） 117

6.6.4　括号表达式（Expressions） 118

6.6.5　完全树标号（Complete Tree Labeling） 119

6.6.6　牧师数学家（The Priest Mathematician） 119

6.6.7　自描述序列（Self-describing Sequence） 120

6.6.8　数轴行走（Steps） 121

6.7　提示 122

6.8　注解 122

第7章　数论 123

7.1　素数 123

7.1.1　寻找素数 123

7.1.2　素数的个数 124

7.2　整除性 125

7.2.1　最大公约数 125

7.2.2　最小公倍数 127

7.3　模算术 127

7.4　同余 129

7.4.1　同余运算 129

7.4.2　求解线性同余式 130

7.4.3　不定方程 131

7.5　数论函数库 131

7.6　习题 132

7.6.1　开灯与关灯（Light,More Light） 132

7.6.2　Carmichael数（Carmichael Numbers） 132

7.6.3　欧几里德问题（Euclid Problem） 133

7.6.4　阶乘与整除（Factovisors） 134

7.6.5　四素数之和（Summation of Four Primes） 134

7.6.6　Smith数（Smith Numbers） 135

7.6.7　弹珠（Marbles） 135

7.6.8　重新打包（RePackaging） 136

7.7　提示 137

7.8　注解 137

第8章 回溯法 138

8.1　回溯法 138

8.2　构造所有子集 140

8.3　构造所有排列 141

8.4　程序设计举例：八皇后问题 143

8.5　搜索中的剪枝 144

8.6　习题 147

8.6.1　棋盘上的象（Little Bishops） 147

8.6.2　15数码游戏（15-Puzzle Problem） 148

8.6.3　队伍（Queue） 149

8.6.4　服务站（Servicing Stations） 150

8.6.5　拔河（Tug of War） 150

8.6.6　伊甸园（Garden of Eden） 151

8.6.7　色彩缤纷游戏（Color Hash） 153

8.6.8　拼接正方形（Bigger Square Please...） 154

8.7　提示 156

8.8　注解 156

第9章　图遍历 157

9.1　图的不同属性 157

9.2　图的数据结构 158

9.3　图的遍历：宽度优先 162

9.3.1　宽度优先遍历 162

9.3.2　遍历的应用 163

9.3.3　寻找路径 164

9.4　图的遍历：深度优先 165

9.4.1　寻找环 166

9.4.2　连通分量 167

9.5　拓扑排序 168

9.6　习题 170

9.6.1　双着色（Bicoloring） 170

9.6.2　摆弄轮子（Playing With Wheels） 171

9.6.3　导游（The Tourist Guide） 173

9.6.4　斜线迷宫（Slash Maze） 174

9.6.5　递变阶梯（Edit Step Ladders） 175

9.6.6　立方体之塔（Tower of Cubes） 176

9.6.7　从黄昏到拂晓（From Dusk till Dawn） 177

9.6.8　汉诺塔卷土重来！（Hanoi Tower Troubles Again!） 179

9.7　提示 179

第10章　图算法 181

10.1　图论 181

10.1.1　度的性质 181

10.1.2　连通性 182

10.1.3　图中的回路 182

10.1.4　平面图 183

10.2　最小生成树 183

10.3　最短路 186

10.3.1　Dijkstra算法 186

10.3.2　每对结点之间的最短路 188

10.4　网络流和二分图匹配 191

10.5 习题 195

10.5.1　斑点（Freckles） 195

10.5.2　项链（The Necklace） 195

10.5.3　消防站（Fire Station） 197

10.5.4　铁路（Railroads） 198

10.5.5　战争（War） 199

10.5.6　导游（Tourist Guide） 201

10.5.7　丰盛的晚餐（The Grand Dinner） 202

10.5.8　命题者的难题（The Problem With the Problem Setter） 203

10.6　提示 205

第11章　动态规划 206

11.1　慎用贪心法 206

11.2　编辑距离 207

11.3　重建路径 211

11.4　编辑距离的变种 212

11.5　程序设计举例：电梯优化 214

11.6　习题 218

11.6.1　越大越聪明？（Is Bigger Smarter?） 218

11.6.2　不同的子序列（Distinct Subsequences） 219

11.6.3　重量和力量（Weights and Measures） 219

11.6.4　单向TSP（Unidirectional TSP） 220

11.6.5　切割小木棍（Cutting Sticks） 221

11.6.6　渡船装载（Ferry Loading） 222

11.6.7　筷子（Chopsticks） 223

11.6.8　搬家大冒险：第四部（Adventures in Moving:Part IV） 224

11.7　提示 225

11.8　注解 225

第12章 网格 226

12.1　矩形网格 226

12.1.1　遍历 227

12.1.2　对偶图及其表示 228

12.2　三角形网格和六边形网格 229

12.2.1　三角形网格 229

12.2.2　六边形网格 230

12.3　程序设计举例：西餐碟的重量 232

12.4　给圆打包 234

12.5　经度和纬度 236

12.6　习题 236

12.6.1　棋盘上的蚂蚁（Ant on a Chessboard） 236

12.6.2　独轮车（The Monocycle） 237

12.6.3　六角星（Star） 239

12.6.4　蜜蜂Maja（Bee Maja） 240

12.6.5　抢劫案（Robbery） 241

12.6.6　（2/3/4）-维立方体？（（2/3/4）-D Sqr/Rects/Cubes/Boxes?） 242

12.6.7 Dermuba三角（Dermuba Triangle） 243

12.6.8　航线（Airlines） 244

12.7　提示 246

第13章　几何 247

13.1　直线 247

13.2　三角形和三角学 250

13.2.1　直角三角形和勾股定理 251

13.2.2　三角函数 251

13.2.3　解三角形 252

13.3　圆 253

13.4　程序设计举例：超高速飞行 255

13.5　三角函数库 257

13.6　习题 259

13.6.1　狗拿地鼠（Dog and Gopher） 259

13.6.2　绳子王国的危机！（Rope Crisis in Ropeland!） 260

13.6.3　圆桌骑士（The Knights of the Round Table） 260

13.6.4　巧克力片饼干（Chocolate Chip Cookies） 261

13.6.5　生日蛋糕（Birthday Cake） 262

13.6.6　最大／最小的盒子（The Largest/Smallest Box...） 263

13.6.7　要算积分吗？（Is This Integration?） 264

13.6.8　它有多大？（How Big Is It?） 265

13.7　提示 266

第14章　计算几何 277

14.1　线段及其相交 277

14.2　多边形及旋转方向 278

14.3　凸包 270

14.4　三角剖分：算法与相关问题 274

14.4.1　Van Gogh算法 274

14.4.2　面积计算 276

14.4.3　点定位 277

14.5　网格上的算法 278

14.5.1 范围查询 278

14.5.2　网格多边形与Pick定理 279

14.6 几何函数库 280

14.7　习题 280

14.7.1　新生集会（Herding Frosh） 280

14.7.2　最近点对问题（The Closest Pair Problem） 281

14.7.3　电锯惊魂（Chainsaw Massacre） 282

14.7.4　冷热游戏（Hotter Colder） 283

14.7.5　没用的瓷砖打包公司（Useless Tile Packers） 284

14.7.6　雷达追踪（Radar Tracking） 285

14.7.7　岛上的树（Trees on My Island） 286

14.7.8　美味的牛奶（Nice Milk） 287

14.8　提示 288

附录A 290

A.1　ACM国际大学生程序设计竞赛 290

A.1.1　准备 290

A.1.2　战略战术 292

A.2　国际信息学奥林匹克 293

A.2.1　如何参加 293

A.2.2　比赛形式 294

A.2.3　准备 295

A.3 Topcoder.com 295

A.4　念研究生吧！ 296

A.5　题目致谢 297

参考文献 300