程序设计常用算法模版¶

👉 总结c++算法题中常用的一些算法模版

矩阵快速幂¶

带模数的矩阵快速幂乘法，常用于矩阵DP的快速计算。

Matrix multiply(const Matrix& A, const Matrix& B) {
    Matrix C;
    for (int i = 0; i < MATRIX_SIZE; ++i) {
        for (int j = 0; j < MATRIX_SIZE; ++j) {
            for (int k = 0; k < MATRIX_SIZE; ++k) {
                // Use __int128 for intermediate multiplication to avoid overflow
                // before taking modulo. (A.mat[i][k] * B.mat[k][j]) can exceed LLONG_MAX
                __int128 temp = (__int128)A.mat[i][k] * B.mat[k][j];
                C.mat[i][j] = (C.mat[i][j] + temp) % MOD;
            }
             // Ensure result stays positive after modulo
             if (C.mat[i][j] < 0) C.mat[i][j] += MOD;
        }
    }
    return C;
}

Matrix matrix_pow(Matrix M, ll p) { // Exponent p can be large, use ll
    Matrix result;
    // Initialize result as identity matrix
    for (int i = 0; i < MATRIX_SIZE; ++i) result.mat[i][i] = 1;

    while (p > 0) {
        if (p & 1) { // If p is odd
            result = multiply(result, M);
        }
        M = multiply(M, M);
        p >>= 1; // p = p / 2
    }
    return result;
}

离散化模版¶

原数组为a[i], 其中的值可能很大，且有重复。这时采用离散化处理a[i]，方便后续计算。

利用vector去重的版本

    vector<int> value_for_compression;// 用于存储节点值的压缩
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);//每个节点的粽子编号
        value_for_compression.push_back(a[i]); // 将节点值加入压缩数组
    }
    sort(value_for_compression.begin(), value_for_compression.end()); // 排序
    value_for_compression.erase(unique(value_for_compression.begin(), value_for_compression.end()), value_for_compression.end()); // 去重，unique将不重复元素移到前面，重复元素移到后面，返回第一个重复元素的迭代器
    map<int, int> value_to_c ompressed; // 用于存储节点值到压缩值的映射
    for (int i=0;i<value_for_compression.size();i++)
    {
        value_to_compressed[value_for_compression[i]]=i+1; // 映射
    }
    for (int i=1;i<=n;i++)
    {
        a[i]=value_to_compressed[a[i]]; // 压缩节点值
    }

利用unordered_map去重的版本，但是不一定能保证大的数离散化之后也大（但原始序列有序就行）

    // 更高效的离散化处理
    unordered_map<int, int> compress;
    int compress_id = 1;

    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if (compress.find(a[i]) == compress.end()) {
            compress[a[i]] = compress_id++;
        }
    }

    // 应用压缩值
    for (int i = 1; i <= n; i++) {
        a[i] = compress[a[i]];
    }

优先队列常用功能¶

默认大顶堆，若要小顶堆使用greater
若数据类型是自定义的结构体，则需要在结构体中重构小于符号

struct Task{
    int val;
    bool operator < (const Task&other) const{
        return val < other.val; // 大顶堆
    }
}t[100];
priority_queue<Task> q;
priority_queue<int,vector<int>,greater<int>> q2; // 小顶堆

素数三大判断方法¶

对于素数n，遍历1~\(\sqrt(n)\) , 判断该数能不能被某个数整除
埃氏筛：从2-n，对于每个素数x，标记2x，3x .....为合数
线性筛：维护一个数x的最小质因子。然后每次将已知素数乘以该质因子获得某合数，并设置改合数的最小质因子

const int MAXN = 1000000; // 筛选范围 1 到 MAXN
std::vector<int> lp(MAXN + 1, 0); // 最小质因子
std::vector<int> primes;          // 存储找到的素数

void linear_sieve(int n) {
    lp[0] = lp[1] = -1; // 标记0和1不是素数，且没有最小质因子
    for (int i = 2; i <= n; ++i) {
        if (lp[i] == 0) { // i 是素数
            lp[i] = i;
            primes.push_back(i);
        }
        // 尝试用已找到的素数 primes[j] (即 p) 去筛掉 i * p
        // 注意这里 primes.size() 是动态变化的
        for (int j = 0; j < primes.size(); ++j) {
            int p = primes[j];
            // 优化点1: 如果 p > i 的最小质因子 lp[i]，则 i*p 的最小质因子是 lp[i] 而不是 p
            //         这个 i*p 应该由 i' = i*p/lp[i] 在后续外循环中通过乘以 lp[i] 筛掉，此处 break
            // 优化点2: 如果 i*p 超出范围，也 break
            if (p > lp[i] || (long long)i * p > n) {
                break;
            }

            // 如果没 break，说明 p <= lp[i]，因此 p 是 i*p 的最小质因子
            lp[i * p] = p;

            // 优化点3 (保证线性的关键): 如果 p == lp[i] (即 i 能被 p 整除)
            // 那么 i*p' (其中 p' 是比 p 更大的素数) 的最小质因子也是 p
            // i*p' = (i/p * p) * p' = (i/p) * p * p'
            // 这个数应该由 (i/p * p') 乘以 p 来筛掉，而不是现在由 i 乘以 p' 筛掉
            // 因此这里必须 break，停止用更大的素数去筛 i 的倍数
            if (p == lp[i]) { // 等价于 i % p == 0
                break;
            }
        }
    }
}

KMP子串匹配¶

基本思想就是计算一个字符串s2的next数组，其代表每个位置的最大前后缀相等的子串长度。这样子后面在s1与s2匹配的时候，失配之后s2不用从头开始，而是可以从next[j-1]处继续与s1匹配。

void kmp(string s1,string s2)//kmp算法
{
    int len1=s1.length();
    int len2=s2.length();
    int i=0,j=0;
    while(i<len1&&j<len2)
    {
        if (s1[i]==s2[j])
        {
            i++;
            j++;
            if (j==len2)//如果j到达了s2的末尾，说明找到了一个匹配
            {
                res.push_back(i-j);//将匹配的下标加入结果
                j=next2[j-1];//j回到next2[j-1]的位置
            }
        }
        else{
            if (j==0) i++;
            else{
                j=next2[j-1];//如果不匹配，j回到next2[j-1]的位置
            }
        }
    }
}
void computeNext(string s2)//计算next数组
{
    int j=0;
    next2[0]=0;
    for (int i=1;i<s2.length();i++)
    {
        while (j>0&&s2[i]!=s2[j])
        {
            j=next2[j-1];
        }
        if (s2[i]==s2[j])
        {
            j++;
        }
        next2[i]=j;
    }
}

并查集模版¶

int find(int x)
{
    if (parents[x]==x) return x;//如果是根节点，返回根节点
    return parents[x]=find(parents[x]);//否则递归查找父节点
}
void merge(int x,int y)
{
    int rootx=find(x);
    int rooty=find(y);//查找x和y的根节点
    if (rootx==rooty) return;//如果x和y的根节点相同，说明已经在同一个集合中
    parents[rootx]=rooty;//将x的根节点指向y的根节点
    size[rooty]+=size[rootx];//将x的大小加到y的大小上
}

带权边邻接矩阵建图¶

#include <vector>
vector<vector<pair<int,int>>>adj;
int main()
{
    int n=5;
    adj.resize(5);
    for (const auto& edge:adj[0])
    {
        cout<<edge.first;
    }
}

二叉树建树模版¶

#include <iostream>
#include <vector>
#include <queue>
#include <cstddef> // For NULL or nullptr

// 定义二叉树节点结构体
struct TreeNode {
    int val;         // 节点的值
    TreeNode *left;  // 左子节点指针
    TreeNode *right; // 右子节点指针

    // 构造函数
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};


TreeNode* buildTree(const std::vector<int>& nums) {
    if (nums.empty() || nums[0] == -1) {
        return nullptr; // 空树
    }

    // 创建根节点
    TreeNode* root = new TreeNode(nums[0]);
    // 使用队列进行层序遍历构建
    std::queue<TreeNode*> q;
    q.push(root);

    int i = 1; // 数组索引，从1开始（0是根节点）
    while (!q.empty() && i < nums.size()) {
        TreeNode* current_node = q.front();
        q.pop();

        // 构建左子节点
        if (nums[i] != -1) { // -1 表示空节点
            current_node->left = new TreeNode(nums[i]);
            q.push(current_node->left);
        }
        i++; // 移动到下一个数组元素

        // 构建右子节点
        if (i < nums.size() && nums[i] != -1) {
            current_node->right = new TreeNode(nums[i]);
            q.push(current_node->right);
        }
        i++; // 移动到下一个数组元素
    }
    return root;
}

线段树算法模版与变体总结¶

线段树（Segment Tree）是一种非常强大的数据结构，用于在给定区间上进行高效的查询和修改操作。它通常用于解决区间和、区间最大/最小值、区间更新等问题。其核心在于分治思想和对区间信息的有效维护。

1. 基本线段树模版¶

线段树的核心思想是将一个大区间不断二分，直到每个叶子节点代表一个单位长度的区间。每个非叶子节点存储其子节点所代表区间的聚合信息。

基本结构与操作：

节点定义： 每个节点通常包含以下信息：
l, r: 表示当前节点所代表的区间范围 [l, r]。
val: 存储该区间 [l, r] 的聚合值（例如，区间和、区间最大值等）。
lazy (可选): 懒惰标记，用于延迟更新操作。
建树 (Build):
递归地将区间 [L, R] 分裂为 [L, Mid] 和 [Mid+1, R]。
叶子节点（L == R）存储原始数组对应位置的值。
非叶子节点的值由其子节点的值合并（pushUp）得到。

void build(int p, int l, int r) {
    tree[p].l = l;
    tree[p].r = r;
    if (l == r) {
        tree[p].val = arr[l]; // 假设arr是原始数组
        return;
    }
    int mid = (l + r) / 2;
    build(2 * p, l, mid);
    build(2 * p + 1, mid + 1, r);
    pushUp(p); // 合并子节点信息
}

更新 (Update):
单点更新： 找到对应的叶子节点，更新其值，然后回溯更新其祖先节点。

void update(int p, int idx, int val) { // 将idx位置更新为val
    if (tree[p].l == tree[p].r) {
        tree[p].val = val;
        return;
    }
    int mid = (tree[p].l + tree[p].r) / 2;
    if (idx <= mid) {
        update(2 * p, idx, val);
    } else {
        update(2 * p + 1, idx, val);
    }
    pushUp(p);
}

区间更新 (带懒惰标记)： 当需要对一个区间进行批量更新时，引入懒惰标记 lazy。
- 如果当前节点的区间完全包含在更新区间内，则更新 lazy 标记，并更新 val，但不立即下推到子节点。
- 否则，先将 lazy 标记下推 (pushDown) 到子节点，然后递归地处理子节点。

void pushDown(int p) { // 将lazy标记下推
    if (tree[p].lazy != 0) { // 假设lazy标记为0表示无延迟操作
        // 根据具体操作更新子节点的val
        // 例如：区间加法
        tree[2 * p].val += tree[p].lazy * (tree[2 * p].r - tree[2 * p].l + 1);
        tree[2 * p + 1].val += tree[p].lazy * (tree[2 * p + 1].r - tree[2 * p + 1].l + 1);
        // 更新子节点的lazy标记
        tree[2 * p].lazy += tree[p].lazy;
        tree[2 * p + 1].lazy += tree[p].lazy;
        tree[p].lazy = 0; // 清除当前节点的lazy标记
    }
}

void updateRange(int p, int L, int R, int val) { // 将区间[L, R]加上val
    if (L <= tree[p].l && tree[p].r <= R) { // 当前节点区间完全包含在更新区间内
        tree[p].val += val * (tree[p].r - tree[p].l + 1); // 更新当前节点的值
        tree[p].lazy += val; // 增加懒惰标记
        return;
    }
    pushDown(p); // 下推懒惰标记
    int mid = (tree[p].l + tree[p].r) / 2;
    if (L <= mid) {
        updateRange(2 * p, L, R, val);
    }
    if (R > mid) {
        updateRange(2 * p + 1, L, R, val);
    }
    pushUp(p);
}

查询 (Query):
查询一个区间的聚合值。
如果当前节点的区间完全包含在查询区间内，则直接返回其 val。
否则，下推 lazy 标记（如果存在），然后递归地查询子节点，并将结果合并。

long long query(int p, int L, int R) { // 查询区间[L, R]的和
    if (L <= tree[p].l && tree[p].r <= R) {
        return tree[p].val;
    }
    pushDown(p); // 下推懒惰标记
    int mid = (tree[p].l + tree[p].r) / 2;
    long long res = 0; // 初始值根据具体操作而定
    if (L <= mid) {
        res += query(2 * p, L, R);
    }
    if (R > mid) {
        res += query(2 * p + 1, L, R);
    }
    return res;
}

pushUp 函数： 根据具体问题定义如何合并子节点信息。
区间和：tree[p].val = tree[2*p].val + tree[2*p+1].val;
区间最大值：tree[p].val = max(tree[2*p].val, tree[2*p+1].val);

2. 线段树的常见变体¶

线段树的灵活性使其能够适应多种复杂问题，以下是一些常见的变体：

动态开点线段树 (Dynamic Segment Tree):
当区间范围非常大，但实际使用的点很少时，可以采用动态开点。
初始时只创建根节点，当需要访问某个子节点时才创建它。
节点不再用数组索引表示，而是用指针或结构体中的左右子节点索引。
适用于坐标离散化后的稀疏区间问题。
主席树 (Persistent Segment Tree / 可持久化线段树):
能够查询历史版本的数据结构。
每次修改操作不会改变原有的树结构，而是创建一条新的路径，共享未修改的部分。
每个历史版本都是一棵完整的线段树。
常用于查询区间第K小/大值等问题。
权值线段树 (Value Segment Tree):
线段树的区间不再是原始数组的索引，而是值的范围。
例如，如果统计数字出现的频率，线段树的叶子节点 [x, x] 可以表示数字 x 的出现次数。
常用于统计区间内满足某个条件元素的个数，或查询第K大/小值。
线段树合并 (Segment Tree Merge):
将两棵线段树合并成一棵新的线段树。
通常用于处理树形结构上的问题，例如统计子树内元素的某种属性。
合并时，如果两棵树都有某个节点，则将它们的值合并；如果只有一棵树有，则直接复制。
扫描线 (Sweep Line with Segment Tree):
将几何问题（如矩形面积并、周长并）转换为一维问题。
通过扫描线从左到右或从下到上扫描，维护一个线段树来记录当前扫描线与图形的交集信息。
线段树的节点通常存储区间覆盖次数、有效长度等信息。
ZKW 线段树 (ZKW Segment Tree):
一种非递归的线段树实现，通常比递归实现更快，常数更小。
通过巧妙的位运算和循环来模拟线段树的建树、查询和更新过程。
理解和实现难度相对较高。

最短路算法¶

下面是经典单源最短路算法dijkstra的模版

#include <iostream>
#include <vector>
#include <queue>
#include <limits> // For numeric_limits

// 定义一个表示边的结构体
struct Edge {
    int to;     // 边的终点
    int weight; // 边的权重
};

struct State {
    int dist; // 从起点到当前节点的距离
    int u;    // 当前节点

    // 重载操作符，使优先队列成为小顶堆（按距离从小到大排序）
    bool operator>(const State& other) const {
        return dist > other.dist;
    }
};

const int INF = std::numeric_limits<int>::max(); // 定义一个表示无穷大的常量

std::vector<int> dijkstra(const std::vector<std::vector<Edge>>& graph, int start, int V) {
    // dist数组存储从起点到各个节点的当前最短距离
    // 初始化所有距离为无穷大，起点距离为0
    std::vector<int> dist(V, INF);
    dist[start] = 0;

    // visited数组标记节点是否已确定最短路径
    std::vector<bool> visited(V, false);

    // 优先队列，用于存储待处理的节点 (距离, 节点编号)
    // 每次取出距离最小的节点
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
    pq.push({0, start}); // 将起点加入优先队列

    while (!pq.empty()) {
        // 取出队列中距离最小的节点
        State current = pq.top();
        pq.pop();

        int u = current.u;
        int d = current.dist;

        // 如果当前节点已经被访问过，或者当前距离比已知的最短距离大，则跳过
        // 这是为了处理优先队列中可能存在的重复（但距离更大）的元素
        if (visited[u]) {
            continue;
        }
        if (d > dist[u]) {
            continue;
        }

        // 标记当前节点为已访问，表示其最短路径已确定
        visited[u] = true;

        // 遍历当前节点u的所有邻居v
        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;

            // 如果通过u到达v的距离比当前已知的到v的距离更短
            // 并且v还没有被访问过（可选优化，即使访问过也可能更新，但通常不必要）
            if (!visited[v] && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight; // 更新到v的最短距离
                pq.push({dist[v], v});      // 将v加入优先队列
            }
        }
    }

    return dist; // 返回从起点到所有节点的最短距离
}

下面是多源最短路floyed算法模版：

#include <iostream>
#include <vector>
#include <limits> // For numeric_limits

const int INF = std::numeric_limits<int>::max(); // 定义一个表示无穷大的常量

/**
 * @brief Floyd-Warshall算法实现
 *
 * @param graph 邻接矩阵表示的图，graph[i][j] 存储从节点i到节点j的权重。
 * 如果i到j没有直接边，则为INF。graph[i][i] 为0。
 * @param V 图中节点的数量
 * @return std::vector<std::vector<int>> 从任意节点到任意其他节点的最短距离矩阵
 */
std::vector<std::vector<int>> floydWarshall(std::vector<std::vector<int>>& graph, int V) {
    // dist 矩阵存储从任意i到任意j的最短距离
    // 初始时，dist 等于输入的 graph 邻接矩阵
    std::vector<std::vector<int>> dist = graph;

    // K 是中间节点
    for (int k = 0; k < V; ++k) {
        // i 是起点
        for (int i = 0; i < V; ++i) {
            // j 是终点
            for (int j = 0; j < V; ++j) {
                // 避免溢出：如果 dist[i][k] 或 dist[k][j] 已经是INF，则相加可能溢出
                // 确保只有当路径可达时才进行更新
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    // 尝试通过中间节点 k 来更新 i 到 j 的最短路径
                    dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // 可选：检测负权环
    // 如果最终 dist[i][i] < 0，则说明存在负权环
    // for (int i = 0; i < V; ++i) {
    //     if (dist[i][i] < 0) {
    //         std::cout << "图中存在负权环！" << std::endl;
    //         // 可以选择返回一个特殊值或抛出异常
    //     }
    // }

    return dist;
}

* 解决负权边的bellman-ford算法模版：

#include <iostream>
#include <vector>
#include <limits> // For numeric_limits

const int INF = std::numeric_limits<int>::max(); // Define a constant for infinity

// Structure to represent an edge in the graph
struct Edge {
    int u, v, weight; // Start node, end node, weight
};

// V代表节点个数
bool bellmanFord(const std::vector<Edge>& edges, int V, int start_node, std::vector<int>& dist) {
    // Initialize distances: start_node to 0, others to infinity
    dist.assign(V, INF);
    dist[start_node] = 0;

    // Relax all edges V-1 times
    // A path can have at most V-1 edges in a graph with V vertices without cycles
    for (int i = 0; i < V - 1; ++i) {
        bool relaxed_in_this_iteration = false; // Flag to check if any relaxation occurred
        for (const Edge& edge : edges) {
            int u = edge.u;
            int v = edge.v;
            int weight = edge.weight;

            // Check for overflow before addition
            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                relaxed_in_this_iteration = true;
            }
        }
        if (!relaxed_in_this_iteration) {
            break;
        }
    }

    // Check for negative cycles
    // After V-1 iterations, if we can still relax any edge,
    // it means there's a negative cycle reachable from the start_node.
    for (const Edge& edge : edges) {
        int u = edge.u;
        int v = edge.v;
        int weight = edge.weight;

        if (dist[u] != INF && dist[u] + weight < dist[v]) {
            // Negative cycle detected
            return false;
        }
    }

    return true; // No negative cycle detected
}