acm模板（ACM/ICPC代码库）

### ACM模板（ACM/ICPC代码库） #### 概述 ACM/ICPC（国际大学生程序设计竞赛）是一项全球范围内重要的编程竞赛活动。它不仅考验参赛者的编程能力，还涉及广泛的算法知识。这份由吉林大学计算机科学与技术学院提供的讲义——“ACM/ICPC代码库”，为学习者提供了丰富的算法实例与解决方案，涵盖了图论、网络流、数据结构、数论等多个方面。 #### 图论 - **DAG的深度优先搜索标记**：DAG（有向无环图）是一种特殊的图结构，在这类图上进行深度优先搜索可以用于多种应用，如拓扑排序等。 - **无向图找桥**：在无向图中找到连接两个顶点的唯一路径上的边称为桥，这些边一旦删除会导致图变得不连通。 - **无向图连通度(割)**：连通度是指图中最少需要移除多少个顶点或边才能使图不连通，分为顶点连通度和边连通度。 - **最大团问题DP+DFS**：最大团问题是寻找图中最大的完全子图，通常采用动态规划结合深度优先搜索的方法解决。 - **欧拉路径O(E)**：欧拉路径是一条经过图中每条边恰好一次的路径。对于连通图，若有两个奇度顶点，则存在欧拉路径。 - **DIJKSTRA数组实现O（N^2）**：迪杰斯特拉算法是求解单源最短路径问题的经典算法之一，适用于没有负权重边的情况。 - **DIJKSTRA O(E*LOGE)**：通过优先队列优化后的迪杰斯特拉算法，适用于稀疏图。 - **BELLMAN-FORD单源最短路O(VE)**：贝尔曼-福特算法可以处理带有负权重边的图，并且能够检测是否存在负权重环。 - **SPFA (SHORTEST PATH FASTER ALGORITHM)**：最短路径快速算法，是对贝尔曼-福特算法的一种改进，适用于密集图。 - **第K短路（DIJKSTRA）**：利用迪杰斯特拉算法找到第K条最短路径，通常需要借助于优先队列来维护当前可能的最短路径集合。 - **第K短路（A\*）**：A\*算法是一种启发式搜索算法，可以用来寻找从起点到终点的第K条最短路径。 - **PRIM求MST**：普里姆算法是求解最小生成树的经典算法之一，适用于稠密图。 - **次小生成树O(V^2)**：在所有生成树中找到第二小的生成树，通常需要先找到最小生成树后再进行调整。 - **最小生成森林问题(K颗树)O(MLOGM)**：对于一个不连通的图，找到所有连通分量的最小生成树的总和。 - **有向图最小树形图**：对于有向图，找到一棵包含所有顶点的有向树，使得所有边权之和最小。 - **MINIMAL STEINERTREE**：在图中寻找一颗包含指定顶点集的树，使得所有边权之和最小。 - **TARJAN强连通分量**：Tarjan算法是一种经典的求解有向图强连通分量的算法。 - **弦图判断**：弦图是一种特殊的图，每个长度大于等于4的简单环至少有一个弦。 - **弦图的PERFECT ELIMINATION点排列**：在弦图中找到一种顶点排列方式，使得每次删除一个顶点及其相邻边后，剩余的图仍然是弦图。 - **稳定婚姻问题O(N^2)**：解决的是如何将两个不同的集合中的元素进行配对，使得不存在任何一对更愿意配对在一起的人。 - **拓扑排序**：对于有向无环图，按照某种顺序排序所有顶点，使得对于任意一条从u到v的边，u在v之前。 - **无向图连通分支(DFS/BFS邻接阵)**：利用深度优先搜索或广度优先搜索来确定无向图的连通分量。 - **有向图强连通分支(DFS/BFS邻接阵)O(N^2)**：求解有向图的强连通分量，可以使用深度优先搜索或广度优先搜索。 - **有向图最小点基(邻接阵)O(N^2)**：在有向图中找到一个顶点集，使得该集中每个顶点都是其他顶点的可达顶点之一。 - **FLOYD求最小环**：弗洛伊德算法不仅可以求解任意两点之间的最短路径，还可以用于检测图中是否存在负权重环。 - **2-SAT问题**：2-SAT（2-可满足性）问题是在布尔逻辑中确定一组特定类型的公式是否可满足的问题。 #### Network网络流 - **二分图匹配（匈牙利算法DFS实现）**：匈牙利算法是一种解决二分图匹配问题的有效算法，基于深度优先搜索实现。 - **二分图匹配（匈牙利算法BFS实现）**：另一种基于广度优先搜索实现的匈牙利算法。 - **二分图匹配（HOPCROFT-CARP的算法）**：Hopcroft-Karp算法是解决二分图最大匹配问题的一个有效算法。 - **二分图最佳匹配（KUHN-MUNKRAS算法O(M*M*N)）**：Kuhn-Munkras算法用于解决赋权二分图的最佳匹配问题。 - **无向图最小割O(N^3)**：最小割是指在一个给定的无向图中，将图分成两个互不相交的部分，使得被割断的边的权值之和最小。 - **有上下界的最小(最大)流**：在网络流问题中，除了边的容量限制外，还可能有额外的上下界约束。 - **DINIC最大流O(V^2*E)**：Dinic算法是求解最大流问题的一个高效算法，特别是对于稠密图。 - **HLPP最大流O(V^3)**：HLPP算法（Highest Label Preflow-Push Algorithm）是求解最大流问题的一种改进算法。 - **最小费用流O(V*E*F)**：在考虑边的成本时，最小费用流问题寻求的是花费最低的可行流。 - **最小费用流O(V^2*F)**：另一种求解最小费用流问题的算法，具有更好的时间复杂度。 - **最佳边割集**：最佳边割集是指在图中去掉一些边，使得图被分割成两部分，且这些边的权值之和最小。 - **最佳点割集**：最佳点割集是指在图中去掉一些顶点，使得图被分割成两部分，且这些顶点的权值之和最小。 - **最小边割集**：最小边割集是最佳边割集的一种特殊情况，即在满足条件的所有边割集中，其权值之和最小。 - **最小点割集（点连通度）**：最小点割集是最佳点割集的一种特殊情况，即在满足条件的所有点割集中，其权值之和最小。 - **最小路径覆盖O(N^3)**：在有向图中找到一个路径集，使得每个顶点都恰好被一条路径覆盖。 - **最小点集覆盖**：在图中找到一个顶点集，使得每个边至少与该顶点集中一个顶点关联。 #### Structure数据结构 - **求某天是星期几**：利用Zeller公式或其他方法计算某个具体日期是星期几。 - **左偏树合并复杂度O(LOGN)**：左偏树是一种自平衡的二叉查找树，合并两个左偏树的时间复杂度较低。 - **树状数组**：也称作二叉索引树，是一种支持查询和更新操作的数据结构。 - **二维树状数组**：二维树状数组可以用于二维范围查询问题。 - **TRIE树(K叉)**：Trie树是一种用于存储字符串的树形数据结构，可以有效地进行字符串的插入和查询操作。 - **TRIE树(左儿子右兄弟)**：Trie树的另一种实现方式，使用左儿子右兄弟的链接结构。 - **后缀数组O(N*LOGN)**：后缀数组是字符串处理中的一种数据结构，可以高效地进行字符串的模式匹配。 - **后缀数组O(N)**：另一种构建后缀数组的方法，具有线性时间复杂度。 - **RMQ离线算法O(N*LOGN)+O(1)**：范围最小值查询（Range Minimum Query）问题的离线解法。 - **RMQ (RANGE MINIMUM/MAXIMUM QUERY)-ST算法 (O(NLOGN+Q))**：RMQ问题的在线解法，使用线段树实现。 - **RMQ离线算法O(N*LOGN)+O(1)求解LCA**：利用RMQ算法求解最近公共祖先问题。 - **LCA离线算法O(E)+O(1)**：最近公共祖先（Lowest Common Ancestor）问题的离线解法。 - **带权值的并查集**：并查集是一种常用的数据结构，用于处理集合的合并及查询问题。 - **快速排序**：快速排序是一种高效的排序算法，采用分治策略。 - **2台机器工作调度**：工作调度问题涉及到任务分配给多个处理器，目标是最小化完成所有任务的时间。 - **比较高效的大数**：在某些情况下，标准整数类型不足以表示非常大的数，因此需要使用特殊的数据结构来处理大数。 - **普通的大数运算**：大数的基本运算，如加、减、乘、除等。 - **最长公共递增子序列O(N^2)**：给定一个序列，找出其中最长的递增子序列。 - **0-1分数规划**：0-1分数规划是一种优化问题，目标是在一组变量只能取0或1的情况下最大化或最小化一个分数形式的目标函数。 - **最长有序子序列（递增/递减/非递增/非递减）**：给定一个序列，找出其中最长的递增或递减子序列。 - **最长公共子序列**：最长公共子序列（Longest Common Subsequence）问题是寻找两个序列的最长公共子序列。 - **最少找硬币问题（贪心策略-深搜实现）**：最少找零问题可以通过贪心策略解决，但有时需要使用深度优先搜索来验证解的正确性。 - **棋盘分割**：将一个棋盘分割成特定形状的小块，通常需要通过回溯法解决。 - **汉诺塔**：汉诺塔问题是一个经典的递归问题，涉及到将一系列圆盘从一个柱子移动到另一个柱子。 - **STL中的PRIORITY_QUEUE**：优先队列是C++ STL中提供的一种容器，支持高效地插入元素和获取最高优先级的元素。 - **堆栈**：堆栈是一种基本的数据结构，遵循先进后出的原则。 - **区间最大频率**：给定一个数组和一些查询，返回查询区间内出现次数最多的数字。 - **取第K个元素**：在未排序的数组中找到第K小的元素。 - **归并排序求逆序数**：归并排序可以用来统计数组中的逆序数。 - **逆序数推排列数**：逆序数是衡量数组无序程度的一个指标，可以用于推导排列的数量。 - **二分查找**：二分查找是一种在有序数组中查找特定元素的高效算法。 - **二分查找（大于等于V的第一个值）**：在有序数组中查找第一个大于等于给定值的位置。 - **所有数位相加**：给定一个正整数，计算它的所有位上的数字之和。 #### Number数论 - **递推求欧拉函数PHI(I)**：欧拉函数是一个数论函数，表示小于等于n的正整数中与n互质的数的数目。 - **单独求欧拉函数PHI(X)**：直接计算某个数值的欧拉函数值。 - **GCD最大公约数**：两个或多个整数共有因子中最大的一个。 - **快速GCD**：通过一些技巧提高计算最大公约数的速度。 - **扩展GCD**：不仅可以计算两个数的最大公约数，还可以找到它们的一个线性组合等于最大公约数。 - **模线性方程A*X=B(%N)**：求解形如ax ≡ b (mod n)的方程。 - **模线性方程组**：求解形如a1x1 + a2x2 + ... + anxn ≡ b (mod n)的方程组。 - **筛素数[1..N]**：埃拉托斯特尼筛法是求解一定范围内所有素数的有效算法。 - **高效求小范围素数[1..N]**：针对较小范围内的素数筛选算法。 - **随机素数测试(伪素数原理)**：通过随机测试的方法来检验一个数是否为素数。 - **组合数学相关**：组合数学研究的是在给定条件下选择对象的方式数量。 - **POLYA计数**：Polya计数定理是用于解决计数问题的一种工具。 - **组合数C(N,R)**：组合数是指从n个不同元素中取出r个元素的方法数。 - **最大1矩阵**：在一维数组中，寻找连续的1的最大长度。 - **约瑟夫环问题（数学方法）**：约瑟夫环问题是一个经典问题，通过数学方法解决。 - **约瑟夫环问题（数组模拟）**：通过数组模拟约瑟夫环问题的过程。 - **取石子游戏1**：取石子游戏是一种典型的博弈论问题。 - **集合划分问题**：将一个集合分成若干个互不相交的子集。 - **大数平方根（字符串数组表示）**：当数很大时，使用字符串数组表示来计算平方根。 - **大数取模的二进制方法**：大数取模时，可以使用二进制的方法提高效率。 - **线性方程组A[][]X[]=B[]**：求解线性方程组Ax = b，其中A是系数矩阵，b是常数项。 - **追赶法解周期性方程**：对于一些具有周期性的方程，可以使用追赶法求解。 - **阶乘最后非零位,复杂度O(NLOGN)**：计算一个阶乘结果的最后一位非零数字。 - **递归方法求解排列组合问题**：使用递归方法解决排列和组合问题。 - **类循环排列**：类循环排列是指将元素按某种规律排列成环状。 - **全排列**：给定一个集合，求出该集合的所有可能排列。 - **不重复排列**：给定一个集合，求出其中所有元素不重复的排列。 - **全组合**：给定一个集合，求出该集合的所有可能组合。 - **不重复组合**：给定一个集合，求出其中所有元素不重复的组合。