1、 几何 25
1.1 注意 25
1.2 几何公式 25
1.3 多边形 27
1.4 多边形切割 30
1.5 浮点函数 31
1.6 面积 36
1.7 球面 37
1.8 三角形 38
1.9 三维几何 40
1.10 凸包 47
1.11 网格 49
1.12 圆 49
1.13 整数函数 51
2、 组合 54
2.1 组合公式 54
2.2 排列组合生成 54
2.3 生成gray码 56
2.4 置换(polya) 56
2.5 字典序全排列 57
2.6 字典序组合 57
3、 结构 58
3.1 并查集 58
3.2 堆 59
3.3 线段树 60
3.4 子段和 65
3.5 子阵和 65
4、 数论 66
4.1 阶乘最后非0位 66
4.2 模线性方程组 67
4.3 素数 68
4.4 欧拉函数 69
5、 数值计算 70
5.1 定积分计算(Romberg) 70
5.2 多项式求根(牛顿法) 72
5.3 周期性方程(追赶法) 73
6、 图论—NP搜索 74
6.1 最大团 74
6.2 最大团(n<64)(faster) 75
7、 图论—连通性 77
7.1 无向图关键点(dfs邻接阵) 77
7.2 无向图关键边(dfs邻接阵) 78
7.3 无向图的块(bfs邻接阵) 79
7.4 无向图连通分支(dfs/bfs邻接阵) 80
7.5 有向图强连通分支(dfs/bfs邻接阵) 81
7.6 有向图最小点基(邻接阵) 82
8、 图论—匹配 83
8.1 二分图最大匹配(hungary邻接表) 83
8.2 二分图最大匹配(hungary邻接阵) 84
8.3 二分图最大匹配(hungary正向表) 84
8.4二分图最佳匹配(kuhn_munkras邻接阵) 85
8.5 一般图匹配(邻接表) 86
8.6 一般图匹配(邻接阵) 87
8.7 一般图匹配(正向表) 87
9、 图论—网络流 88
9.1 最大流(邻接阵) 88
9.2 上下界最大流(邻接阵) 89
9.3 上下界最小流(邻接阵) 90
9.4 最大流无流量(邻接阵) 91
9.5 最小费用最大流(邻接阵) 91
10、 图论—应用 92
10.1 欧拉回路(邻接阵) 92
10.2 树的前序表转化 93
10.3 树的优化算法 94
10.4 拓扑排序(邻接阵) 95
10.5 最佳边割集 96
10.6 最佳点割集 97
10.7 最小边割集 98
10.8 最小点割集 99
10.9 最小路径覆盖 101
11、 图论—支撑树 101
11.1 最小生成树(kruskal邻接表) 101
11.2 最小生成树(kruskal正向表) 103
11.3 最小生成树(prim+binary_heap邻接表) 104
11.4 最小生成树(prim+binary_heap正向表) 105
11.5 最小生成树(prim+mapped_heap邻接表) 106
11.6 最小生成树(prim+mapped_heap正向表) 108
11.7 最小生成树(prim邻接阵) 109
11.8 最小树形图(邻接阵) 109
12、 图论—最短路径 111
12.1 最短路径(单源bellman_ford邻接阵) 111
12.2 最短路径(单源dijkstra+bfs邻接表) 111
12.3 最短路径(单源dijkstra+bfs正向表) 112
12.4 最短路径(单源dijkstra+binary_heap邻接表) 113
12.5 最短路径(单源dijkstra+binary_heap正向表) 114
12.6 最短路径(单源dijkstra+mapped_heap邻接表) 115
12.7 最短路径(单源dijkstra+mapped_heap正向表) 116
12.8 最短路径(单源dijkstra邻接阵) 117
12.9 最短路径(多源floyd_warshall邻接阵) 118
13、 应用 118
13.1 Joseph问题 118
13.2 N皇后构造解 119
13.3 布尔母函数 120
13.4 第k元素 120
13.5 幻方构造 121
13.6 模式匹配(kmp) 122
13.7 逆序对数 123
13.8 字符串最小表示 123
13.9 最长公共单调子序列 124
13.10 最长子序列 125
13.11 最大子串匹配 126
13.12 最大子段和 127
13.13 最大子阵和 127
14、 其它 128
14.1 大数(只能处理正数) 128
14.2 分数 134
14.3 矩阵 136
14.4 线性方程组 138
14.5 线性相关 140
14.6 日期 140
数据结构的钻石版 ACM 模板是一份包含多种算法和数据结构实现的代码库，主要针对ACM（国际大学生程序设计竞赛）等算法竞赛。这个模板由浙江大学ICPC团队维护，由WishingBone于2002年创建，并在2004年由Riveria进行了最后的更新。
1. **几何**：
- **注意**：在处理几何问题时，需要注意精度问题，浮点数运算可能会导致误差。
- **几何公式**：包括点、线、面的坐标运算和几何变换。
- **多边形**：处理多边形的性质，如判断点是否在多边形内。
- **多边形切割**：将多边形切割成更小的部分，用于复杂的几何操作。
- **浮点函数**：涉及浮点数的计算，如距离、角度等。
- **面积**：计算各种几何形状的面积，如矩形、圆形、三角形等。
- **球面**：处理球面上的点和线，如大圆路径。
- **三角形**：涉及三角形的性质，如边角关系、面积、周长等。
- **三维几何**：扩展到三维空间的几何问题，如体积、表面积计算。
- **凸包**：找到一组点的最小凸多边形包围。
- **网格**：处理网格结构，如二维或三维的格子。
- **圆**：处理圆形和圆上的点，如碰撞检测。
2. **组合**：
- **组合公式**：计算组合的数量。
- **排列组合生成**：生成所有可能的排列和组合。
- **Gray码**：生成无跳跃的二进制码序列。
- **置换(Polya)**：处理排列的统计特性。
- **字典序全排列**：按字典序生成全排列。
- **字典序组合**：按字典序生成组合。
3. **结构**：
- **并查集**：用于处理集合的合并与查找问题。
- **堆**：实现最大堆和最小堆，用于优先队列。
- **线段树**：处理区间查询和修改，如求和、查找最值。
- **子段和**：快速查询和更新一段连续区间的和。
- **子阵和**：扩展线段树处理矩阵中的子区域和。
4. **数论**：
- **阶乘最后非0位**：确定阶乘末尾非零数字的数量。
- **模线性方程组**：解模线性方程组，如扩展欧几里得算法。
- **素数**：素数检测、质因数分解等。
- **欧拉函数**：计算欧拉函数的值，与同余群有关。
5. **数值计算**：
- **定积分计算(Romberg)**：使用Romberg方法计算定积分。
- **多项式求根(牛顿法)**：通过牛顿迭代法求解多项式的根。
- **周期性方程(追赶法)**：处理周期性方程的求解。
6. **图论-NP搜索**：
- **最大团**：寻找图中的最大独立集。
- **最小点基**：寻找图中的最小点基，与图的连通性相关。
7. **图论-连通性**：
- **关键点/关键边**：确定无向图的关键连接。
- **块**：识别无向图的连通分量。
- **连通分支**：获取无向图和有向图的连通分支。
- **强连通分支**：找出有向图中的强连通分量。
8. **图论-匹配**：
- **二分图最大匹配**：应用匈牙利算法解决二分图的匹配问题。
- **一般图匹配**：处理非二分图的匹配问题。
9. **图论-网络流**：
- **最大流**：寻找网络中的最大流量。
- **上下界最大流**：处理带上下界的流量问题。
- **最小费用最大流**：考虑成本的网络流问题。
10. **图论-应用**：
- **欧拉回路**：寻找图中的欧拉回路。
- **树的前序表转化**：将前序遍历转换为树结构。
- **拓扑排序**：对有向无环图进行拓扑排序。
11. **图论-支撑树**：
- **最小生成树**：使用Kruskal、Prim等算法寻找图的最小生成树。
12. **图论-最短路径**：
- **单源最短路径**：Dijkstra、Bellman-Ford等算法。
- **多源最短路径**：Floyd-Warshall算法。
13. **应用**：
- **Joseph问题**：处理Josephus问题的循环移除算法。
- **N皇后构造解**：解决N皇后问题的解法构造。
- **布尔母函数**：处理布尔代数中的母函数运算。
- **第k元素**：找出数组中的第k小（大）元素。
- **幻方构造**：生成特定大小的幻方。
- **模式匹配(KMP)**：快速字符串模式匹配算法。
- **逆序对数**：计算数组中逆序对的数量。
- **字符串最小表示**：找到字符串的最小表示形式。
- **最长公共单调子序列**：寻找两个序列中最长的公共单调子序列。
- **最长子序列**：寻找两个序列的最长公共子序列。
- **最大子串匹配**：找出最长的相同子串。
- **最大子段和**：计算数组中的最大连续子段和。
- **最大子阵和**：在矩阵中找到最大的子矩阵和。
14. **其它**：
- **大数**：处理大整数的运算，通常用于超出了标准整型范围的情况。
- **分数**：实现分数类，处理有理数的运算。
- **矩阵**：矩阵的加减乘除和求逆等操作。
- **线性方程组**：解线性方程组的算法。
- **线性相关**：检查向量或矩阵的线性相关性。
- **日期**：处理日期相关的操作。
这个模板涵盖了算法竞赛中常见的几何、组合数学、数据结构、数论、数值计算和图论问题，为参赛者提供了丰富的工具箱，有助于高效解决各种复杂问题。
