【清华内部ACM培训资料】涉及的是计算机科学竞赛中常见的算法和问题解决技巧，主要涵盖了数学、字符串处理、计算几何、数论、图论、排序和查找以及数据结构等多个领域。下面将对这些知识点进行详细解释：
**数学问题**：
1. **精度计算**：在算法竞赛中，大数计算是一个重要部分，包括大数阶乘、大数乘法（大数乘小数和大数乘大数）、加法、减法和任意进制转换。这些问题通常需要自定义算法来处理超过标准数据类型的数值。
2. **组合序列**：涉及到组合数学，如组合数C(n, k)的计算。
3. **快速傅立叶变换（FFT）**：一种用于高效计算离散傅立叶变换的算法，广泛应用于信号处理和图像处理等领域。
4. **Ronberg 算法计算积分**：一种数值积分方法，用于近似求解函数的定积分。
5. **行列式计算**和**求排列组合数**：矩阵和组合数学的基础概念，常常出现在线性代数和概率统计题目中。
**字符串处理**：
1. **字符串替换**：找到并替换字符串中的特定子串。
2. **字符串查找**：在字符串中搜索特定字符或子串的位置。
3. **字符串截取**：从字符串中提取一部分。
**计算几何**：
1. **叉乘法求多边形面积**：利用向量的叉乘来计算平面内的几何形状面积。
2. **求三角形面积**：使用海伦公式或其他几何方法。
3. **两矢量间角度**：计算两个向量之间的夹角。
4. **两点距离**：计算2D或3D空间中两点之间的欧几里得距离。
5. **判断点是否在多边形内**：射线法等方法判断点相对于多边形的位置。
6. **判断点是否在线段上**：检查点是否在线段的延长线上。
7. **判断两线段是否相交**：检测线段之间的交点。
8. **线段与直线是否相交**：线段和无限直线的交点检测。
9. **点到线段最短距离**：计算点到线段的垂直距离。
10. **求两直线的交点**：找到两条直线的交点坐标。
11. **判断凹集或凸集**：识别一个点集是凹的还是凸的。
12. **Graham 扫描法寻找凸包**：找到包含所有点的最小凸多边形。
**数论**：
1. **x 的二进制长度**：计算整数的二进制表示位数。
2. **二进制位提取**：获取二进制表示中的指定位。
3. **模取幂运算**：计算模意义下的幂次运算。
4. **模线性方程求解**：解决形如 ax ≡ b (mod m) 的线性同余方程。
5. **模线性方程组求解**：中国剩余定理用于解决多个线性同余方程组。
6. **筛法素数生成器**：通过埃拉托斯特尼筛法生成素数列表。
7. **素数判断**：确定一个整数是否为素数。
**图论**：
1. **Prim 算法**：用于寻找加权无向图的最小生成树。
2. **Dijkstra 算法**：单源最短路径问题的解决方案，适用于带权重的图。
3. **Bellman-Ford 算法**：能处理负权重边的单源最短路径算法。
4. **Floyd 算法**：计算图中所有顶点对的最短路径。
**排序/查找**：
1. **快速排序**：高效的排序算法，基于分治策略。
2. **希尔排序**：改进的插入排序，通过增量序列优化性能。
3. **选择法排序**：选取最小元素放到已排序部分的末尾。
4. **二分查找**：在有序数组中查找目标值，时间复杂度为O(log n)。
**数据结构**：
1. **顺序队列**：基于数组实现的线性数据结构，具有先进先出（FIFO）特性。
2. **顺序栈**：基于数组的后进先出（LIFO）数据结构。
3. **链表**：动态数据结构，每个元素（节点）包含数据和指向下一个节点的指针。
4. **链栈**：链式存储的栈，同样具备LIFO特性。
5. **二叉树**：每个节点最多有两个子节点的数据结构，常用于实现二叉搜索树和AVL树等。
这些算法和数据结构是ACM/ICPC等编程竞赛中常见的考点，掌握它们对于提高解决问题的能力至关重要。通过深入理解和实践，可以有效地解决各种复杂的计算问题。
