程序设计竞赛训练营:基础与数学概念电子书

版 权

内容提要

前言

资源与支持

第1章 准备

1.1 什么是程序设计竞赛

1.1.1 ACM-ICPC

1.1.2 Google Code Jam（GCJ）

1.1.3 TopCoder

1.1.4 CodeForces

1.1.5 IOI

1.2 如何使用UVa OJ

1.2.1 注册

1.2.2 提交

1.3 如何选择编程语言

1.4 辅助工具

第2章 入门

2.1 基本数据类型

2.1.1 整数的表示

2.1.2 浮点数的表示及精度

2.1.3 数据类型的取值范围

2.2 格式化输入

2.2.1 概述

2.2.2 标准输入

2.2.3 字符串输入

2.3 格式化输出

2.3.1 概述

2.3.2 输出对齐

2.3.3 整数输出

2.3.4 实数输出

2.3.5 缓冲区与输入输出同步

2.4 小结

第3章 数据结构

3.1 内置数组

3.1.1 顺序记录

3.1.2 游戏模拟

3.1.3 矩阵变换

3.1.4 约瑟夫问题

3.2 向量

3.3 栈

3.4 队列及优先队列

3.4.1 队列

3.4.2 优先队列

3.5 双端队列

3.6 映射

3.7 集合

3.8 位集

3.9 链表

3.10 二叉树

3.11 范围查询

3.11.1 线段树

3.11.2 二维线段树

3.11.3 区间树

3.11.4 树状数组

3.11.5 稀疏表

3.11.6 根号分块

3.12 并查集

3.13 算法库函数

3.13.1 accumulate、count和count_if函数

3.13.2 copy和reverse_copy函数

3.13.3 fill函数

3.13.4 iotaC++11函数

3.13.5 max和min函数

3.13.6 max_element和min_element函数

3.13.7 memcpy和memset函数

3.14 小结

第4章 字符串

4.1 编码

4.2 字符串类

4.2.1 声明

4.2.2 赋值

4.2.3 遍历

4.2.4 连接与删除

4.2.5 查找与替换

4.2.6 其他操作

4.3 字符串库函数

4.4 字符串类应用

4.4.1 文本解析

4.4.2 语法分析

4.4.3 KMP匹配算法

4.4.4 扩展KMP匹配算法

4.4.5 Z算法

4.4.6 字符串的最小表示

4.5 字符串数据结构及应用

4.5.1 Trie

4.5.2 Aho-Corasick算法

4.5.3 后缀数组

4.5.4 最长公共子串

4.5.5 最长重复子串

4.5.6 Burrows-Wheeler变换

4.6 正则表达式

4.6.1 元字符

4.6.2 转义字符

4.6.3 数量匹配符和分组

4.6.4 字符类和可选模式

4.6.5 断言

4.6.6 正则表达式类

4.7 算法库函数

4.7.1 lexicographical_compare函数

4.7.2 next_permutation和prev_permutation函数

4.7.3 replace函数

4.7.4 reverse函数

4.7.5 transform函数

4.8 小结

第5章 排序与查找

5.1 交换排序

5.1.1 冒泡排序

5.1.2 快速排序

5.1.3 中位数

5.2 插入排序

5.2.1 直接插入排序

5.2.2 希尔排序

5.3 选择排序

5.3.1 直接选择排序

5.3.2 堆排序

5.4 归并排序

逆序对数

5.5 计数排序

5.6 基数排序

5.7 桶排序

5.8 查找

5.8.1 顺序查找

5.8.2 二分查找

5.8.3 方程求近似解

5.8.4 最大值最小化问题

5.8.5 三分搜索

5.9 算法库函数

5.9.1 binary_search函数

5.9.2 find函数

5.9.3 lower_bound和upper_bound函数

5.9.4 nth_element函数

5.9.5 partial_sort函数

5.9.6 sort函数

5.9.7 stable_sort函数

5.9.8 unique函数

5.10 小结

第6章 算术与代数

6.1 割鸡焉用牛刀乎

6.2 他山之石，可以攻玉

6.3 高精度整数类的实现

6.4 进制及其转换

6.4.1 进制数转换为十进制数

6.4.2 十进制数转换为进制数

6.4.3 任意进制数之间的相互转换

6.4.4 罗马计数法

6.5 实数

6.5.1 分数

6.5.2 连续分数

6.5.3 分数转换为小数

6.5.4 小数转换为分数

6.5.5 实数大小的比较

6.6 代数

6.6.1 多项式运算

6.6.2 高斯消元法

6.7 幂与对数

6.8 实数函数库

6.9 小结

第7章 组合数学

7.1 计数原理

7.1.1 加法原理

7.1.2 乘法原理

7.2 排列与组合

7.2.1 康托展开和康托逆展开

7.2.2 方程的整数解数量

7.3 Pólya计数定理

7.3.1 基本概念

7.3.2 Burnside引理

7.3.3 Pólya计数定理

7.4 鸽笼原理

拉姆齐理论

7.5 容斥原理

错排问题

7.6 初等数列

7.6.1 等差数列

7.6.2 等比数列

7.6.3 其他数列

7.7 计数序列

7.7.1 斐波那契数

7.7.2 卡特兰数

7.7.3 欧拉数

7.7.4 斯特林数

7.7.5 调和级数

7.7.6 其他序列

7.8 概率论

7.8.1 基本概念

7.8.2 条件概率和独立事件

7.8.3 全概率公式与贝叶斯公式

7.8.4 随机变量

7.8.5 期望

7.9 博弈论

7.9.1 Nim游戏

7.9.2 Sprague-Grundy定理

7.9.3 Nim游戏和Sprague-Grundy定理扩展

7.9.4 PN态分析

7.10 小结

第8章 数论

8.1 素数

8.1.1 素数判定

8.1.2 米勒-拉宾素性测试

8.1.3 高斯素数

8.1.4 生成素数序列

8.1.5 素因子分解

8.2 整除性

8.2.1 最大公约数

8.2.2 扩展欧几里得算法

8.2.3 线性同余方程

8.2.4 最小公倍数

8.2.5 欧拉函数

8.2.6 莫比乌斯函数

8.3 模算术

8.3.1 整数拆分

8.3.2 可乐兑换

8.3.3 模运算规则

8.3.4 模的逆元

8.3.5 离散对数

8.3.6 中国剩余定理

8.3.7 波拉德启发式因子分解算法

8.4 日期和时间转换

8.4.1 日期转换

8.4.2 时间转换

8.5 小结

第9章 几何

9.1 点

9.2 直线

9.2.1 直线的表示

9.2.2 直线间关系

9.2.3 相互垂直的两条直线交点

9.3 坐标和坐标系变换

9.3.1 平移

9.3.2 旋转

9.3.3 缩放

9.4 三角形

9.4.1 勾股定理

9.4.2 三角函数

9.4.3 正弦定理

9.4.4 余弦定理

9.4.5 三角形面积

9.4.6 三角函数库

9.4.7 桌球碰撞问题

9.5 多边形

9.5.1 矩形

9.5.2 四边形和正多边形

9.6 圆

9.6.1 圆的周长和面积

9.6.2 圆的切线

9.6.3 三角形的内切圆与外接圆

9.6.4 圆与圆的位置关系

9.6.5 最小圆覆盖

9.7 小结

第10章 计算几何

10.1 基本概念

10.1.1 线段

10.1.2 多边形

10.2 几何对象间的关系

10.2.1 向量、内积和外积

10.2.2 点和直线的关系

10.2.3 确定线段转动方向

10.2.4 确定线段是否相交

10.2.5 点的投影

10.2.6 点的映像

10.2.7 点和直线间距离

10.2.8 点和线段间距离

10.2.9 线段和线段间距离

10.2.10 点和多边形的关系

10.2.11 直线和圆的交点

10.2.12 圆和圆的交点

10.2.13 圆的切点

10.3 扫描线算法

10.4 坐标离散化

10.4.1 最大化矩形问题

10.4.2 矩形并的面积

10.4.3 矩形并的周长

10.5 凸包

10.5.1 Graham扫描法

10.5.2 Jarvis步进法

10.5.3 Andrew合并法

10.5.4 Melkman算法

10.6 公式及定理应用

10.6.1 Pick定理

10.6.2 多边形面积

10.6.3 多边形重心

10.6.4 三维几何体的表面积和体积

10.7 半平面交问题

10.7.1 凸多边形切分

10.7.2 多边形内核

10.8 最近点对问题

10.9 最远点对问题

10.10 三维空间计算几何

10.10.1 点

10.10.2 直线

10.10.3 平面

10.10.4 三维凸包

10.11 小结

附录A ASCII表

附录B C++运算符优先级

参考资料