ACM_算法模板集.pdf

根据给定文件的信息，我们可以将主要内容分为以下几个部分：数学与公式、大数处理与字符读入、数论算法、图论算法、几何算法以及专题讨论等。下面将逐一展开介绍这些知识点。 ### 一、数学与公式 #### 常用数学公式与定理 - **斐波那契数列 (Fibonacci Number)** - 定义：一个数列，其中每个数字是前两个数字的和。 - 公式：$F_n = F_{n-1} + F_{n-2}$，$F_0=0$，$F_1=1$。 - **卢卡斯数列 (Lucas Number)** - 定义：一个与斐波那契数列相似的数列。 - 公式：$L_n = L_{n-1} + L_{n-2}$，$L_0=2$，$L_1=1$。 - **卡特兰数 (Catalan Number)** - 定义：在解决许多计数问题时出现的一类自然数序列。 - 公式：$C_n = \frac{1}{n+1} {2n \choose n}$。 - **斯特林数第二类 (Stirling Number of the Second Kind)** - 定义：一种用于组合数学中的数，用来计算将$n$个不同元素分成$k$个非空集合的方法数量。 - 公式：${n \brace k}$。 - **贝尔数 (Bell Number)** - 定义：表示将$n$个不同元素划分为若干个不相交子集的方法数。 - 公式：$B_n = \sum_{k=0}^{n} {n \brace k}$。 - **斯特林近似公式 (Stirling's Approximation)** - 定义：用来估计阶乘的公式。 - 公式：$n! \approx \sqrt{2\pi n} (\frac{n}{e})^n$。 - **倒数和近似公式 (Sum of Reciprocal Approximation)** - 定义：用于估算特定类型的级数之和。 - **杨表 (Young Tableau)** - 定义：一种特殊的二维数组，常用于组合数学中。 - **整数划分** - 定义：指将一个正整数写成若干个正整数之和的不同方式的数量。 - **错排公式** - 定义：错排问题是指将$n$个对象重新排列使得没有对象位于原来位置上的方法数。 - **三角形内切圆半径公式** - 定义：给出三角形的三边长度$a,b,c$，可以计算出内切圆的半径$r$。 - **三角形外接圆半径公式** - 定义：给出三角形的三边长度$a,b,c$，可以计算出外接圆的半径$R$。 - **圆内接四边形面积公式** - 定义：给出了圆内接四边形的对角线长度$d_1,d_2$，可以计算其面积。 - **基础数论公式** - 包括但不限于各种与数论相关的公式和定理。 ### 二、大数模板与字符读入 #### 大数处理 - 大数加减乘除等运算的实现。 #### 字符读入 - 实现高效的字符读入功能，如读取单个字符、一行字符串等。 ### 三、数论算法 #### 数论基本算法 - **最大公约数 (Greatest Common Divisor)** - 定义：两个或多个整数共有的约数中最大的一个。 - 方法：辗转相除法。 - **素数判断 (Prime)** - 定义：检查一个数是否为素数。 - 方法：试除法、Miller-Rabin素性测试。 - **素数筛法 (Sieve Prime)** - 定义：高效地找出一定范围内的所有素数。 - 方法：埃拉托斯特尼筛法。 - **模逆元 (Module Inverse)** - 定义：求解$x$使得$a \cdot x \equiv 1 \pmod{m}$。 - 方法：扩展欧几里得算法。 - **扩展欧几里得算法 (Extended Euclid)** - 定义：不仅可以求出两数的最大公约数，还可以找到它们的倍数关系。 - **模线性方程 (Modular Linear Equation)** - 定义：形如$ax \equiv b \pmod{m}$的方程。 - **中国剩余定理 (Chinese Remainder Theorem)** - 定义：用于解决一组同余方程组。 - **欧拉函数 (Euler Function)** - 定义：小于或等于$n$的正整数中与$n$互质的数的数目。 - **费雷序列构造 (Farey Sequence Construction)** - 定义：有序的真分数序列。 - **米勒-拉宾素数测试 (Miller_Rabbin)** - 定义：一种概率性的素性测试算法。 - **波拉德-罗因式分解 (Pollard_rho)** - 定义：一种用于寻找合数因子的算法。 ### 四、图论算法 #### 图论基本算法 - **最小生成树 (Minimum Spanning Tree)** - 定义：在一个加权图中寻找连接所有顶点且总权重最小的树。 - 方法：Kruskal算法、Prim算法。 - **单源最短路径 (Single-Source Shortest Path)** - 定义：在一个加权图中从某个源点到其他所有顶点的最短路径。 - 方法：Bellman-Ford算法、Dijkstra算法。 - **全源最短路径 (All-Pairs Shortest Path)** - 定义：在一个加权图中任意两点之间的最短路径。 - 方法：Floyd算法。 - **拓扑排序 (Topological Sort)** - 定义：对于有向无环图的顶点进行排序，使得对于每条从顶点$u$到顶点$v$的有向边，都有$u$在$v$之前。 - **网络预流和最大流 (Network Preflow and Maximum Flow)** - 定义：在网络流问题中，从源点到汇点的最大流量。 - 方法：Ford-Fulkerson算法、Edmonds-Karp算法。 - **最大团 (Maximum Clique)** - 定义：图中最大的完全子图。 - **最大匹配 (Maximum Matching)** - 定义：在一个图中，尽可能多地匹配顶点对。 - 方法：匈牙利算法、Hopcroft-Karp算法。 - **带权二分图最优匹配 (Weighted Bipartite Matching)** - 定义：在带权二分图中寻找最优匹配。 - 方法：Kuhn-Munkres算法。 - **强连通分量 (Strongly Connected Components)** - 定义：图中所有顶点都相互可达的最大子图。 - 方法：Kosaraju算法、Gabow算法。 - **无向图割边割点和双连通分量 (Cut Edges, Cut Vertices, and Biconnected Components in Undirected Graphs)** - 定义：用于识别图中的关键结构。 - **最小树形图 (Minimum Tree Diagram)** - 定义：在特定条件下寻找具有最小代价的树形结构。 ### 五、几何算法 #### 几何基本算法 - **几何模板** - 包括各种几何操作和计算的基本函数。 - **球面上两点最短距离** - 定义：计算球面上两点之间的大圆弧距离。 - **三点求圆心坐标** - 定义：已知平面上三点，求这三点构成的圆的圆心坐标。 - **三角形几个重要的点** - 包括重心、内心、外心等。 ### 六、专题讨论 #### 数据结构与算法 - **树状数组 (Binary Indexed Tree)** - 定义：一种支持高效查询和更新的数据结构。 - **字典树 (Trie)** - 定义：一种用于存储字符串的树形数据结构。 - **后缀树 (Suffix Tree)** - 定义：一种用于存储字符串的所有后缀的树形数据结构。 - **线段树 (Segment Tree)** - 定义：一种用于区间查询和更新的高效数据结构。 - **并查集 (Disjoint Set)** - 定义：一种数据结构，用于处理一些不相交集合的合并及查询问题。 - **二叉堆 (Binary Heap)** - 定义：一种实现优先队列的数据结构。 - **逆序数 (Inversion Number)** - 定义：用于衡量一个排列的“乱序程度”。 - **树状DP (Tree Dynamic Programming)** - 定义：在树形结构上进行动态规划。 - **欧拉路 (Eulerian Path)** - 定义：图中一条经过所有边恰好一次的路径。 - **八数码 (8-Puzzle)** - 定义：一种经典的滑块拼图游戏。 - **高斯消元法 (Gaussian Elimination)** - 定义：一种解线性方程组的方法。 - **字符串匹配 (String Matching)** - 定义：在文本中查找模式串的位置。 - 方法：KMP算法。 - **全排列与全组合 (Permutations and Combinations)** - 定义：排列与组合的基本概念及其算法实现。 - **二维线段树 (2D Segment Tree)** - 定义：在线性空间上实现二维区间的查询和更新。 - **稳定婚姻匹配 (Stable Marriage Problem)** - 定义：寻找满足稳定条件的匹配。 - **后缀数组 (Suffix Array)** - 定义：字符串所有后缀按字典序排序的结果。 - **左偏树 (Left-Leaning Red-Black Tree)** - 定义：一种自平衡的二叉搜索树。 - **标准RMQ-ST (Range Minimum Query on Segment Tree)** - 定义：一种用于查询区间最小值的数据结构。 - **度限制最小生成树 (Degree-Constrained Minimum Spanning Tree)** - 定义：在最小生成树的基础上加入顶点度数的限制。 - **最优比率生成树 (Optimal Ratio Spanning Tree for 0/1 Fractional Programming)** - 定义：在特定类型的分数规划问题中寻找最优生成树。 - **最小花费置换 (Minimum Cost Perfect Matching)** - 定义：在带权图中寻找最小成本的完美匹配。 - **区间K大数 (Kth Largest Number in an Interval)** - 定义：查询区间中第K大的数。 - **LCA (Lowest Common Ancestor)** - 定义：树中两个节点的最近公共祖先。 - 方法：RMQ-ST方法、Tarjan算法。 - **指数型母函数 (Exponential Generating Function)** - 定义：用于处理计数组合问题的工具。 - **FFT (Fast Fourier Transform)** - 定义：一种快速计算离散傅里叶变换的算法。 - **二分图网络最大流最小割 (Max Flow Min Cut in Bipartite Graphs)** - 定义：在二分图中寻找最大流的同时确定最小割。 - **混合图欧拉回路 (Eulerian Circuit in Mixed Graphs)** - 定义：在包含边和弧的混合图中寻找欧拉回路。 - **无源汇上下界网络流 (Network Flow with Lower and Upper Bounds)** - 定义：在网络流问题中考虑边的流量限制。 - **二分图最小点权覆盖 (Minimum Weight Vertex Cover in Bipartite Graphs)** - 定义：在带权二分图中寻找最小点权覆盖。 - **带约束的轨道计数 (Counting Orbits under Group Actions)** - 定义：利用Burnside引理计算轨道数量。 - **三分法求函数波峰 (Ternary Search for Function Peaks)** - 定义：在特定条件下寻找函数的最大值。 - **单词计数与矩阵乘法 (Word Counting and Matrix Multiplication)** - 定义：包括单词计数和矩阵乘法等算法的应用。 - **字符串和数值哈希 (String and Numerical Hashing)** - 定义：通过哈希函数处理字符串和数值。 - **滚动队列与前向星表示法 (Rolling Queue and Forward Star Representation)** - 定义：用于高效维护队列和图的表示。 - **最小点基与最小权点基 (Minimum Point Basis and Minimum Weight Point Basis)** - 定义：在凸包问题中的应用。 - **LCSubsequence O(N^2/logN) (Longest Common Subsequence in O(N^2/logN))** - 定义：求两个序列最长公共子序列的一种算法。 - **伸展树 (Splay Tree)** - 定义：一种自调整的二叉搜索树。 - **Treap (Randomized Binary Search Tree)** - 定义：结合了二叉搜索树和堆性质的数据结构。 - **0/1分数规划K约束 (0/1 Fractional Programming with K Constraints)** - 定义：在0/1分数规划问题中加入额外的限制条件。 - **表达式求值 (Expression Evaluation)** - 定义：计算数学表达式的值。 - **乘除法博弈 (Multiplication and Division Game)** - 定义：一种基于数字操作的游戏。 - **状态压缩的积木型DP (Bitmask DP)** - 定义：在状态压缩的基础上实现动态规划。 以上是基于给定文档内容整理出的主要知识点概览。这些知识点涵盖了从数学公式到复杂数据结构和算法的广泛领域，对于深入理解计算机科学中的算法设计和分析至关重要。