ACM 模板
JPVision Fighting!
To be or not to be , that is a question.
alpc48
2008-10-5
Acm 常用算法模板
2
ACM Fighting!
ACM Fighting!..................................................................................................................................................2
1.
计算几何
........................................................................................................................................................5
1.1 注意........................................................................................................................................................................5
1.2 几何公式.................................................................................................................................................................6
1.3 多边形....................................................................................................................................................................8
1.4 多边形切割........................................................................................................................................................... 11
1.5 浮点函数..............................................................................................................................................................12
1.6 面积......................................................................................................................................................................18
1.7 球面.......................................................................................................................................................................18
1.8 三角形...................................................................................................................................................................19
1.9 三维几何...............................................................................................................................................................22
1.10 凸包....................................................................................................................................................................30
1.11 网格....................................................................................................................................................................32
1.12 圆........................................................................................................................................................................33
1.13 矢量运算求几何模板........................................................................................................................................35
1.14 结构体表示几何图形.........................................................................................................................................47
1.15 四城部分几何模板.............................................................................................................................................52
1.16 一些代码..........................................................................................................................................................54
1.16.1 最小圆覆盖_zju1450 ................................................................................................................................................... 54
1.16.2 直线旋转_两凸包的最短距离(poj3608)..................................................................................................................... 58
1.16.3 扇形的重心 .................................................................................................................................................................. 62
1.16.4 根据经度纬度求球面距离 .......................................................................................................................................... 63
1.16.5 多边形的重心 .............................................................................................................................................................. 64
1.16.6 存不存在一个平面把两堆点分开(poj3643)............................................................................................................... 66
1.16.7 pku_3335_判断多边形的核是否存在 ......................................................................................................................... 67
1.16.8 pku_2600_二分+圆的参数方程 ................................................................................................................................... 74
1.16.9 pku_1151_矩形相交的面积 ......................................................................................................................................... 76
1.16.10 pku_1118_共线最多的点的个数................................................................................................................................ 78
1.16.11 pku2826_线段围成的区域可储水量.......................................................................................................................... 80
1.16.12 Pick公式...................................................................................................................................................................... 84
1.16.13 N点中三个点组成三角形面积最大........................................................................................................................... 86
1.16.14 直线关于圆的反射 .................................................................................................................................................... 89
1.16.15 pku2002_3432_N个点最多组成多少个正方形(hao) ................................................................................................ 94
Acm 常用算法模板
3
1.16.16 pku1981_单位圆覆盖最多点(poj1981)CircleandPoints ............................................................................................ 97
1.16.17 pku3668_GameofLine_N个点最多确定多少互不平行的直线(poj3668)................................................................. 99
1.16.18 求凸多边形直径 ...................................................................................................................................................... 100
2.
组合
............................................................................................................................................................102
2.1 组合公式............................................................................................................................................................102
2.2 排列组合生成....................................................................................................................................................102
2.3 生成gray码........................................................................................................................................................104
2.4 置换(polya)........................................................................................................................................................104
2.5 字典序全排列....................................................................................................................................................105
2.6 字典序组合........................................................................................................................................................105
2.7 一些原理及其例子............................................................................................................................................106
3.
数论
............................................................................................................................................................108
3.1 阶乘最后非 0 位................................................................................................................................................108
3.2 模线性方程组....................................................................................................................................................108
3.3 素数.................................................................................................................................................................... 110
3.4 欧拉函数............................................................................................................................................................ 114
3.6 高精度................................................................................................................................................................. 116
3.6.1 平方根 ........................................................................................................................................................................... 116
3.6.2 高精度乘幂 .................................................................................................................................................................. 117
3.7 高斯消元回代法................................................................................................................................................123
3.8 数值计算............................................................................................................................................................124
3.8.1 定积分计算 .................................................................................................................................................................. 124
3.8.2 多项式求根(牛顿法).................................................................................................................................................... 125
3.8.3 周期性方程(追赶法).................................................................................................................................................... 127
4.
排序
............................................................................................................................................................128
4.1 快速选择算法.....................................................................................................................................................128
4.2 归并排序+逆序数的求取 ..................................................................................................................................129
5.
字符串
........................................................................................................................................................130
5.1 KMP应用 ...........................................................................................................................................................130
5.2 后缀数组............................................................................................................................................................131
5.3 中缀表达式转后缀表达式................................................................................................................................134
5.4 Firefighters 表达式求值...................................................................................................................................135
6.
博弈
............................................................................................................................................................139
6.1 博弈的AB剪枝 ..................................................................................................................................................139
Acm 常用算法模板
4
6.1.1 取石子.......................................................................................................................................................................... 139
6.2 博弈 SG函数 局势分割...................................................................................................................................141
7.
数据结构
....................................................................................................................................................142
7.1 TRIE...................................................................................................................................................................142
7.2 线段树................................................................................................................................................................147
7.3 并查集................................................................................................................................................................151
7.4 树状数组............................................................................................................................................................152
7.5 点树....................................................................................................................................................................154
7.6 STL.....................................................................................................................................................................156
7.7 离散化................................................................................................................................................................157
8.
图论
............................................................................................................................................................158
8.0 2-SAT..................................................................................................................................................................158
8.2 寻找Euler回路 ..................................................................................................................................................163
8.3 拓扑排序............................................................................................................................................................163
8.4 差分约束系统....................................................................................................................................................164
8.5 笛卡尔树............................................................................................................................................................165
8.6 LCA和RMQ.......................................................................................................................................................167
8.7 割和桥................................................................................................................................................................171
8.8 最小生成树(kruskal)........................................................................................................................................172
8.9 最短路径............................................................................................................................................................173
8.10 最大网络流......................................................................................................................................................175
8.11 最小费用流......................................................................................................................................................180
8.12 最大团问题......................................................................................................................................................182
8.13 二分图匹配......................................................................................................................................................184
8.14 带权的最优二分图匹配..................................................................................................................................184
9.
搜索算法概略
............................................................................................................................................187
9.1 迭代深搜+IDA*................................................................................................................................................187
9.2 分之界限法(深搜)........................................................................................................................................189
9.3 A* 8 数码问题( pascal ).....................................................................................................................................192
9.4 优先队列广搜....................................................................................................................................................194
10.
应用
..........................................................................................................................................................197
10.1 Joseph问题.......................................................................................................................................................197
Acm 常用算法模板
5
10.2 N皇后构造解....................................................................................................................................................197
10.3 布尔母函数......................................................................................................................................................198
10.4 第k元素 ...........................................................................................................................................................199
10.5 幻方构造..........................................................................................................................................................199
10.6 模式匹配(kmp) ...............................................................................................................................................201
10.7 逆序对数..........................................................................................................................................................201
10.8 字符串最小表示..............................................................................................................................................202
10.9 最长公共单调子序列......................................................................................................................................202
10.10 最长子序列....................................................................................................................................................204
10.11 最大子串匹配................................................................................................................................................204
10.12 最大子段和....................................................................................................................................................205
10.13 最大子阵和....................................................................................................................................................206
11.
其它
...........................................................................................................................................................207
11.1 大数(只能处理正数) .......................................................................................................................................207
11.2 分数..................................................................................................................................................................212
11.3 矩阵..................................................................................................................................................................214
11.4 线性方程组......................................................................................................................................................216
11. 5 线性相关.........................................................................................................................................................218
11.6 日期..................................................................................................................................................................219
11.7 读入..................................................................................................................................................................220
11.8 函数..................................................................................................................................................................220
1.计算几何
1.1 注意
1. 注意舍入方式(0.5 的舍入方向);防止输出-0.
2. 几何题注意多测试不对称数据.
3. 整数几何注意 xmult 和 dmult 是否会出界;
符点几何注意 eps 的使用.
4. 避免使用斜率;注意除数是否会为 0.
5. 公式一定要化简后再代入.
6. 判断同一个 2*PI 域内两角度差应该是
abs(a1-a2)<beta||abs(a1-a2)>pi+pi-beta;