NOIP竞赛必备：C++基础算法模板详解（图论、字符串、数据结构与数学）

本文档提供了一个关于NOIP竞赛中C++基本算法模板的全面指南，主要涵盖图论、字符串处理、数据结构以及数学基础知识。以下是各部分的主要知识点详解： 1. **图论**： - **并查集**：并查集是一种用于解决集合合并问题的数据结构，包括初始化函数、查找根节点、合并集合和判断两个元素是否在同一个集合等操作。这些函数如`init`、`find`、`unite`和`same`是解决图论问题中连接关系的关键。 - **最小生成树**：虽然具体实现未在文中给出，但理解并查集后，可以利用Prim或Kruskal算法构建最小生成树，将图中的节点连接成一棵边权和最小的树。 - **单源最短路径**： - **Dijkstra算法**：该模板定义了`edge`结构来存储边的信息，包括目标节点和成本。`dijkstra`函数实现基于优先队列的Dijkstra算法，求解从起点到所有其他节点的最短路径。 - **SPFA算法**：另一种单源最短路径算法，不同于Dijkstra的是，SPFA通常用于加权图中存在负权重边的情况，通过广度优先搜索(BFS)结合松弛操作处理此类问题。 2. **字符串处理**： - **KMP和Extended KMP（ex-KMP）**：KMP算法用于字符串匹配，而ex-KMP是对KMP的扩展，提高了处理模式串中重复字符的效率。 - **Manacher's Algorithm**：这是一种高效的模式匹配算法，可以在具有回文性质的字符串上进行高效的查找。 - **最小表示法**：可能是指霍夫曼编码或字典序最小表示，用于字符串压缩或者编码优化问题。 3. **数据结构**： - **树状数组**：一种高效的数据结构，常用于动态维护区间查询或更新操作，如计算某个区间内的和。 - **线段树**：一种用于处理区间查询的数据结构，支持区间加、减、求和等操作。 4. **数学基础**： - **矩阵快速幂**：用于高效地计算矩阵的幂，常见于多项式乘法和某些递推问题的求解。 - **Lucas定理与Chinese Remainder Theorem（中国剩余定理）**：这两个数学定理在算法设计中分别涉及模运算和数论问题，如分解质因数和模运算的优化。 - **欧拉函数**：在数论中，欧拉函数与约数个数相关，对于密码学和组合计数问题很有用。 - **扩展欧几里得算法**：用于求解最大公约数和贝祖等式（ax + by = gcd(a, b)），是许多算法的基础，如模逆元的计算。 这些算法模板为参加NOIP竞赛的选手提供了坚实的基础，帮助他们在信息学竞赛中处理各种问题，特别是对于初学者来说，掌握这些核心算法是提升编程能力的关键。