第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