ACM程序设计竞赛常用代码

"ACM 程序设计竞赛常用代码" 本资源是一个 ACM 程序设计竞赛的常用代码集，涵盖了数学问题、字符串处理、计算几何、数论、图论、排序/查找、数据结构等多个领域。下面是对每个领域的知识点的详细解释： 数学问题 * 精度计算——大数阶乘：使用数组存储大数的每一位，然后使用循环计算大数的阶乘结果。 * 精度计算——乘法（大数乘小数）：使用字符串表示大数，然后使用循环计算大数乘小数的结果。 * 精度计算——乘法（大数乘大数）：使用二维数组存储大数的每一位，然后使用循环计算大数乘大数的结果。 * 精度计算——加法、减法：使用数组存储大数的每一位，然后使用循环计算大数的加法和减法结果。 * 任意进制转换：使用数组存储大数的每一位，然后使用循环计算大数的任意进制转换结果。 * 最大公约数、最小公倍数：使用欧几里德算法计算最大公约数和最小公倍数。 * 组合序列：使用递推公式计算组合序列。 * 快速傅立叶变换（FFT）：使用快速傅立叶变换算法计算傅立叶变换的结果。 * Ronberg 算法计算积分：使用 Ronberg 算法计算积分的结果。 * 行列式计算：使用行列式的定义计算行列式的结果。 * 求排列组合数：使用递推公式计算排列组合数。 字符串处理 * 字符串替换：使用字符串的 replace 函数实现字符串的替换。 * 字符串查找：使用字符串的 find 函数实现字符串的查找。 * 字符串截取：使用字符串的 substr 函数实现字符串的截取。 计算几何 * 叉乘法求任意多边形面积：使用叉乘法计算任意多边形的面积。 * 求三角形面积：使用海伦公式计算三角形的面积。 * 两矢量间角度：使用 dot product 计算两矢量间的角度。 * 两点距离（2D、3D）：使用欧几里德距离公式计算两点之间的距离。 * 射向法判断点是否在多边形内部：使用射向法判断点是否在多边形内部。 * 判断点是否在线段上：使用点在线段上的判定公式判断点是否在线段上。 * 判断两线段是否相交：使用线段相交的判定公式判断两线段是否相交。 * 判断线段与直线是否相交：使用线段与直线相交的判定公式判断线段与直线是否相交。 * 点到线段最短距离：使用点到线段最短距离公式计算点到线段的最短距离。 * 求两直线的交点：使用两直线的交点公式计算两直线的交点。 * 判断一个封闭图形是凹集还是凸集：使用图形的凹凸判定公式判断一个封闭图形是凹集还是凸集。 * Graham 扫描法寻找凸包：使用 Graham 扫描法寻找凸包的结果。 数论 * x 的二进制长度：使用 bit manipulation 计算 x 的二进制长度。 * 返回 x 的二进制表示中从低到高的第 i 位：使用 bit manipulation 返回 x 的二进制表示中从低到高的第 i 位。 * 模取幂运算：使用模取幂运算公式计算模取幂运算的结果。 * 求解模线性方程：使用模线性方程的解公式计算模线性方程的解。 * 求解模线性方程组（中国余数定理）：使用中国余数定理计算模线性方程组的解。 * 筛法素数产生器：使用筛法产生素数。 * 判断一个数是否素数：使用素数判定公式判断一个数是否素数。 图论 * Prim 算法求最小生成树：使用 Prim 算法计算最小生成树的结果。 * Dijkstra 算法求单源最短路径：使用 Dijkstra 算法计算单源最短路径的结果。 * Bellman-ford 算法求单源最短路径：使用 Bellman-ford 算法计算单源最短路径的结果。 * Floyd 算法求每对节点间最短路径：使用 Floyd 算法计算每对节点间最短路径的结果。 排序/查找 * 快速排序：使用快速排序算法计算排序的结果。 * 希尔排序：使用希尔排序算法计算排序的结果。 * 选择法排序：使用选择法排序算法计算排序的结果。 * 二分查找：使用二分查找算法计算查找的结果。 数据结构 * 顺序队列：使用数组实现顺序队列的数据结构。 * 顺序栈：使用数组实现顺序栈的数据结构。 * 链表：使用链表实现链表的数据结构。 * 链栈：使用链表实现链栈的数据结构。 * 二叉树：使用二叉树实现二叉树的数据结构。