本书是针对大学生程序设计竞赛的训练指南, 主要介绍程序设计和针对竞赛训练所需的基础知识和基本数学概念, 包括UVa OJ平台的使用方法、C++的输入输出处理、C++库实现所包含的数据结构、高级数据结构、字符串的处理和相关算法、排序与查找算法、代数、组合数学、数论、几何等内容。本书在介绍基础概念的基础上, 引入了众多题目, 以C++解题, 针对部分题目给出参考代码, 方便参考和练习。
邱秋, 大学期间自学计算机技术, 工作期间曾开发数字营区、局域网考核、患者健康随访等用途的多款软件。
目录
第 1章 准备 1
1.1 什么是程序设计竞赛 1
1.1.1 ACM-ICPC 1
1.1.2 Google Code Jam（GCJ） 1
1.1.3 TopCoder 2
1.1.4 CodeForces 2
1.1.5 IOI 2
1.2 如何使用UVa OJ 3
1.2.1 注册 3
1.2.2 提交 3
1.3 如何选择编程语言 6
1.4 辅助工具 6
1.3.1 UVa Arena 6
1.3.2 uHunt 6
1.3.3 uDebug 6
1.3.4 VirtualBox 6
1.3.5 Virtual Judge 7
1.3.6 洛谷 7
第 2章 入门 8
2.1 基本数据类型 8
2.1.1 整数的表示 8
2.1.2 浮点数的表示及精度 9
2.1.3 数据类型的取值范围 12
2.2 格式化输入 13
2.2.1 概述 13
2.2.2 标准输入 14
2.2.3 字符串输入 15
2.3 格式化输出 18
2.3.1 概述 18
2.3.2 输出对齐 20
2.3.3 整数输出 20
2.3.4 实数输出 21
2.3.5 缓冲区与输入输出同步 24
2.4 小结 26
第3章 数据结构 27
3.1 内置数组 27
3.1.1 顺序记录 27
3.1.2 游戏模拟 29
3.1.3 矩阵变换 30
3.1.4 约瑟夫问题 30
3.2 向量 34
3.3 栈 37
3.4 队列及优先队列 41
3.4.1 队列 41
3.4.2 优先队列 44
3.5 双端队列 46
3.6 映射 48
3.7 集合 52
3.8 位集 55
3.9 链表 58
3.10 二叉树 59
3.11 范围查询 64
3.11.1 线段树 64
3.11.2 二维线段树 70
3.11.3 区间树 76
3.11.4 树状数组 77
3.11.5 稀疏表 80
3.11.6 根号分块 81
3.12 并查集 85
3.13 算法库函数 87
3.13.1 accumulate和count、
count_if 87
3.13.2 copy和reverse_copy 88
3.13.3 fill 88
3.13.4 iotac++11 89
3.13.5 max和min 89
3.13.6 max_element和min_element 90
3.13.7 memcpy和memset 90
3.14 小结 92
第4章 字符串 93
4.1 编码 93
4.2 字符串类 94
4.2.1 声明 95
4.2.2 赋值 96
4.2.3 遍历 96
4.2.4 连接与删除 97
4.2.5 查找与替换 98
4.2.6 其他操作 99
4.3 字符串库函数 99
4.4 字符串类应用 101
4.4.1 文本解析 101
4.4.2 语法分析 105
4.4.3 KMP匹配算法 108
4.4.4 扩展KMP匹配算法 114
4.4.5 Z算法 116
4.4.6 字符串的小表示 117
4.5 字符串数据结构及应用 118
4.5.1 Trie 118
4.5.2 Aho-Corasick算法 119
4.5.3 后缀数组 124
4.5.4 长公共子串 131
4.5.5 长重复子串 134
4.5.6 Burrows-Wheeler变换 135
4.6 正则表达式 136
4.6.1 元字符 136
4.6.2 转义字符 137
4.6.3 数量匹配符和分组 137
4.6.4 字符类和可选模式 137
4.6.5 断言 138
4.6.6 正则表达式类 138
4.7 算法库函数 139
4.7.1 lexicographical_compare 139
4.7.2 next_permutation和prev_
permutation 140
4.7.3 rece 143
4.7.4 reverse 143
4.7.5 transform 144
4.8 小结 144
第5章 排序与查找 145
5.1 交换排序 145
5.1.1 冒泡排序 145
5.1.2 快速排序 146
5.1.3 中位数 147
5.2 插入排序 149
5.2.1 直接插入排序 149
5.2.2 希尔排序 149
5.3 选择排序 150
5.3.1 直接选择排序 150
5.3.2 堆排序 150
5.4 归并排序 151
5.4.1 逆序对数 151
5.5 计数排序 153
5.6 基数排序 153
5.7 桶排序 155
5.8 查找 155
5.8.1 顺序查找 155
5.8.2 二分查找 156
5.8.3 方程似解 157
5.8.4 大值小化问题 159
5.8.5 三分搜索 160
5.9 算法库函数 162
5.9.1 binary_search 162
5.9.2 find 162
5.9.3 lower_bound和upper_bound 163
5.9.4 nth_element 167
5.9.5 partial_sort 168
5.9.6 sort 168
5.9.7 le_sort 171
5.9.8 unique 172
5.10 小结 173
第6章 算术与代数 174
6.1 割鸡焉用牛刀乎 174
6.2 他山之石，可以攻玉 180
6.3 高精度整数类的实现 182
6.4制及其转换 190
6.4.1 制数转换为制数 190
6.4.2 制数转换为制数 191
6.4.3 任制数之间的相互转换 192
6.4.4 罗马计数法 193
6.5 实数 195
6.5.1 分数 195
6.5.2 连续分数 198
6.5.3 分数转换为小数 198
6.5.4 小数转换为分数 199
6.5.5 实数大小的比较 200
6.6 代数 201
6.6.1 多项式运算 201
6.6.2 高斯消元法 202
6.7 幂与对数 209
6.8 实数函数库 211
6.9 小结 212
第7章 组合数学 213
7.1 计数原理 213
7.1.1 加法原理 213
7.1.2 乘法原理 214
7.2 排列与组合 216
7.2.1 康托展开和康托逆展开 217
7.2.2 方程的整数解个数 222
7.3 Pólya计数定理 223
7.3.1 基本概念 223
7.3.2 Burnside引理 228
7.3.3 Pólya计数定理 231
7.4 鸽笼原理 236
7.4.1 拉姆齐理论 238
7.5 容斥原理 238
7.5.1 错排问题 239
7.6 初等数列 240
7.6.1 等差数列 240
7.6.2 等比数列 240
7.6.3 其他数列 240
7.7 计数序列 241
7.7.1 斐波那契数 241
7.7.2 卡特兰数 245
7.7.3 欧拉数 248
7.7.4 斯特林数 248
7.7.5 调和级数 249
7.7.6 其他序列 250
7.8 概率论 251
7.8.1 基本概念 251
7.8.2 条件概率和独立事件 254
7.8.3 全概率公式与贝叶斯公式 256
7.8.4 随机变量 260
7.8.5 期望 261
7.9 博弈论 269
7.9.1 Nim游戏 270
7.9.2 Sprague-Grundy定理 272
7.9.3 Nim游戏和Sprague-Grundy定理
扩展 273
7.9.4 PN态分析 278
7.10 小结 282
第8章 数论 283
8.1 素数 283
8.1.1 素数判定 284
8.1.2 米勒-拉宾素性测试 285
8.1.3 高斯素数 287
8.1.4 生成素数序列 288
8.1.5 素因子分解 291
8.2 整除性 292
8.2.1 大公约数 292
8.2.2 扩展欧几里得算法 295
8.2.3 线性同余方程 297
8.2.4 小公倍数 298
8.2.5 欧拉函数 299
8.2.6 莫比乌斯函数 303
8.3 模算术 305
8.3.1 整数拆分 306
8.3.2 可乐兑换 306
8.3.3 模运算规则 306
8.3.4 模的逆元 307
8.3.5 离散对数 309
8.3.6 中国剩余定理 310
8.3.7 波拉德ρ启发式因子分解
算法 311
8.4 日期和时间转换 313
8.4.1 日期转换 313
8.4.2 时间转换 317
8.5 小结 318
第9章 几何 319
9.1 点 319
9.2 直线 320
9.2.1 直线的表示 320
9.2.2 直线间关系 321
9.2.3 相互垂直的两条直线交点 322
9.3 坐标和坐标系变换 322
9.3.1移 322
9.3.2 旋转 323
9.3.3 缩放 325
9.4 三角形 329
9.4.1 勾股定理 329
9.4.2 三角函数 331
9.4.3 正弦定理 332
9.4.4 余弦定理 332
9.4.5 三角形面积 334
9.4.6 三角函数库 336
9.4.7 桌球碰撞问题 337
9.5 多边形 339
9.5.1 矩形 339
9.5.2 四边形和正多边形 341
9.6 圆 341
9.6.1 圆的周长和面积 342
9.6.2 圆的切线 343
9.6.3 三角形的内切圆与外接圆 345
9.6.4 圆与圆的位置关系 347
9.6.5 小圆覆盖 351
9.7 小结 352
第 10章 计算几何 353
10.1 基本概念 353
10.1.1 线段 353
10.1.2 多边形 353
10.2 几何对象间的关系 354
10.2.1 向量、内积和外积 354
10.2.2 点和直线的关系 356
10.2.3 确定线段转动方向 358
10.2.4 确定线段是否相交 359
10.2.5 点的投影 362
10.2.6 点的映像 364
10.2.7 点和直线间距离 364
10.2.8 点和线段间距离 365
10.2.9 线段和线段间距离 366
10.2.10 点和多边形的关系 366
10.2.11 直线和圆的交点 369
10.2.12 圆和圆的交点 370
10.2.13 圆的切点 370
10.3 扫描线算法 371
10.4 坐标离散化 373
10.4.1 大化矩形问题 376
10.4.2 矩形并的面积 377
10.4.3 矩形并的周长 379
10.5 383
10.5.1 Graham扫描法 383
10.5.2 Jarvis法 387
10.5.3 Andrew合并法 389
10.5.4 Melkman算法 391
10.6 公式及定理应用 392
10.6.1 Pick定理 392
10.6.2 多边形面积 393
10.6.3 多边形重心 393
10.6.4 三维几何体的表面积和体积 395
10.7 面交问题 396
10.7.1 凸多边形切分 396
10.7.2 多边形内核 401
10.8 点对问题 402
10.9 远点对问题 405
10.10 三维空间计算几何 409
10.10.1 点 410
10.10.2 直线 411
10.10.3面 414
10.10.2 三维 419
10.11 小结 423
附录 425
1 ASCII表 425
2 C++运算符优先级 426
3 引 426
参考资料 427
书单推荐
