常见算法模板整理

一、基础算法与技巧 (Basic Algorithms)

这是所有高级算法的地基，笔试中最常考的“手速题”都依赖这些。

1. 浮点数二分 (Floating-point Binary Search)

应用场景浮点数二分：解决求方程的根、求平方根等精度问题（区别于整数二分）。

求方程的近似根：当函数是单调的，且无法直接推导公式时（如求解 $x^3 + x = 10$ ）。
计算几何问题：求能覆盖所有点的最小圆半径。
最值问题的转化：如经典的“最大平均值连续子段”问题（二分平均值）。

复杂度分析

时间复杂度：$O(\log(\frac{\text{Range}}{\text{eps}}))$。其中 $\text{Range}$ 是初始区间的长度，$\text{eps}$ 是要求的精度。通常循环几十到上百次即可达到极高精度。
空间复杂度：$O(1)$。

核心代码模板

这里我们以最经典的“求一个数 $N$ 的立方根”为例。由于可能输入负数，且浮点数无法精准判等，所以必须使用 eps（极小值）来控制循环退出。

C++

#include <iostream>
#include <iomanip> // 用于控制输出精度
using namespace std;
int main() {
    // 优化输入输出流
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    double n;
    if (!(cin >> n)) return 0;
    // 1. 确定二分边界
    // 注意：如果是求立方根，边界通常设为一个足够大的范围，如 [-10000, 10000]
    // 绝不能简单设为 L = 0, R = n (如果 n 是负数或者 0 < n < 1 时会出错)
    double L = -10000.0, R = 10000.0; 
    // 2. 确定精度
    // 经验法则：eps 一般取题目要求的精度再往下多两位
    // 例如题目要求保留 6 位小数，eps 就设为 1e-8
    const double eps = 1e-8;
    // 3. 浮点数二分核心逻辑
    while (R - L > eps) {
        double mid = L + (R - L) / 2.0;
        if (mid * mid * mid >= n) {
            R = mid; // 答案在左半区，不能写成 R = mid - 1！
        } else {
            L = mid; // 答案在右半区，不能写成 L = mid + 1！
        }
    }
    // 4. 输出结果
    cout << fixed << setprecision(6) << L << "\n";
    return 0;
}

2. 三分查找 (Ternary Search)

应用场景
物理抛物线问题：求物体抛射的最高点。
计算几何/最优化问题：求一点到线段的最短距离（距离函数通常是一个单谷的凸函数）。
凸/凹代价函数求极值：题目中某些代价（Cost）随着某个参数的变化呈现“先下降后上升”的趋势，求最小代价。
复杂度分析

时间复杂度：$O(\log_{1.5}(\frac{\text{Range}}{\text{eps}}))$。每次迭代将搜索区间缩小三分之一（剩下三分之二），收敛速度略慢于二分，但在常数时间上依然是极快的对数级别。

空间复杂度：$O(1)$。

核心代码模板

以求单谷函数（先减后增，求最小值）为例。
三分的核心思想是：在区间 $[L, R]$ 内取两个等分点 $m1$ 和 $m2$ 。通过比较 $f(m1)$ 和 $f(m2)$ 的大小，必定能淘汰掉左侧三分之一或右侧三分之一的区间。

C++

#include <iostream>
#include <iomanip>

using namespace std;

// 假设要求解的单谷函数 (例如: f(x) = (x - 2)^2 + 3)
// 该函数在 x = 2 时取得最小值 3
double f(double x) {
    return (x - 2.0) * (x - 2.0) + 3.0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    double L = -10000.0, R = 10000.0;
    
    // 依然强烈推荐使用固定迭代次数法，彻底消灭精度死循环问题
    for (int i = 0; i < 100; ++i) {
        // 将区间平分为三段，计算两个内部三等分点
        double m1 = L + (R - L) / 3.0;
        double m2 = R - (R - L) / 3.0;
        
        // 我们要求的是“单谷”的【最小值】
        if (f(m1) < f(m2)) {
            // 说明右侧三分之一区间 [m2, R] 在爬坡，极小值不可能在那里面
            R = m2; 
        } else {
            // 说明左侧三分之一区间 [L, m1] 在下坡，极小值不可能在那里面
            L = m1; 
        }
        
        /* 
         * 💡 如果要求的是“单峰”函数的【最大值】，只需把上面的比较符号反过来：
         * if (f(m1) > f(m2)) R = m2; 
         * else L = m1;
         */
    }

    // 循环结束后，L 和 R 已经极其接近极值点的 x 坐标
    cout << "极小值点的 x 坐标: " << fixed << setprecision(6) << L << "\n";
    cout << "极小值点的 y 值: " << fixed << setprecision(6) << f(L) << "\n";
    
    return 0;
}

双指针 (Two Pointers)：包含同向双指针（滑动窗口）和相向双指针（如两数之和）。

这里为你输出“一、基础算法与技巧”中的第三块基石：双指针 (Two Pointers)，以及它最重要的变体——滑动窗口 (Sliding Window)。

在算法竞赛和面试中，当你看到题目的暴力解法是 $O(N^2)$ （两层 for 循环），且题目具有“单调性”（例如数组有序，或者元素全是正数导致的子数组和单调递增），往往就能用双指针将其降维打击到 $O(N)$ 。

3. 双指针与滑动窗口 (Two Pointers & Sliding Window)

应用场景

相向双指针：已排序数组的“两数之和/三数之和”、回文串判定、接雨水问题、盛最多水的容器。
滑动窗口（同向双指针）：所有关于“连续子数组 (Subarray)”或“连续子串 (Substring)”的最优解问题。例如：长度最小的连续子数组、无重复字符的最长子串。

复杂度分析

时间复杂度：$O(N)$。两个指针虽然在两层循环（或 while）中，但每个指针最多只遍历数组一次（不走回头路），总移动次数不超过 $2N$ 。
空间复杂度：$O(1)$（不考虑用来存储状态的辅助哈希表的情况下）。

核心代码模板 1：相向双指针 (对撞指针)

必须满足：数组有序，或者移动端点时具有明确的大小逻辑关系。

这里以经典的“有序数组两数之和 (Two Sum II)”为例：

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 假设数组已经是升序排列
    vector<int> a = {1, 2, 4, 7, 11, 15};
    int target = 15;

    int L = 0;              // 左指针，指向最小元素
    int R = a.size() - 1;   // 右指针，指向最大元素

    while (L < R) { // 必须是严格小于，两个指针不能重合（同一个数不能用两次）
        int sum = a[L] + a[R];
        
        if (sum == target) {
            cout << "找到答案，索引为: " << L << " 和 " << R << "\n";
            break; // 如果找所有的组合，这里要 L++, R-- 然后继续
        } 
        else if (sum < target) {
            // 当前和太小，左边较小的数不要了，L 往右走寻找更大的数
            L++; 
        } 
        else {
            // 当前和太大，右边较大的数不要了，R 往左走寻找更小的数
            R--; 
        }
    }
    return 0;
}

核心代码模板 2：滑动窗口 (同向双指针)

滑动窗口是笔试中最容易出 Bug 的题型，关键在于什么时候进窗口，什么时候出窗口，什么时候更新答案。

记住这套工业级模板，它可以套用 99% 的滑动窗口问题。

场景 A：求最短的满足条件的子数组（例如：求和 $\ge$ target 的最小长度）

口诀：R 往右无脑扩；满足条件时，试图让 L 往右缩，缩的同时在 while 循环内更新最短答案。

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> nums = {2, 3, 1, 2, 4, 3};
    int target = 7;

    int L = 0;
    int current_sum = 0;
    int min_len = 1e9; // 初始设为无穷大

    // 外层循环：R 无脑向右扩展（进窗口）
    for (int R = 0; R < nums.size(); ++R) {
        current_sum += nums[R]; 

        // 内层循环：当窗口满足条件时，尝试缩小窗口以求得更优的“最短”解
        while (current_sum >= target) {
            // 【关键点】：对于“求最短”问题，答案要在内层 while 循环里面更新！
            min_len = min(min_len, R - L + 1);
            
            current_sum -= nums[L]; // 左边界元素出窗口
            L++;                    // 缩小窗口
        }
    }

    if (min_len == 1e9) cout << "无解\n";
    else cout << "最短长度为: " << min_len << "\n";
    return 0;
}

场景 B：求最长的满足条件的子数组（例如：无重复字符的最长子串）

口诀：R 往右无脑扩；一旦不满足条件，L 往右缩直到重新满足条件；在 while 循环外更新最长答案。

C++

#include <iostream>
#include <string>
#include <unordered_set>
#include <algorithm>

using namespace std;

int main() {
    string s = "abcabcbb";

    int L = 0;
    int max_len = 0;
    unordered_set<char> window;

    // R 无脑向右扩展
    for (int R = 0; R < s.length(); ++R) {
        // 内层循环：如果不满足条件（有重复了），L 开始疯狂向右缩，直到恢复合法状态
        while (window.count(s[R])) {
            window.erase(s[L]); // 左边界元素出窗口
            L++;
        }
        
        window.insert(s[R]); // 当前元素进窗口
        
        // 【关键点】：对于“求最长”问题，答案要在 while 循环外面更新！
        // 因为走到这里时，窗口一定是合法状态
        max_len = max(max_len, R - L + 1);
    }

    cout << "最长无重复子串长度为: " << max_len << "\n";
    return 0;
}

滑动窗口的最值 (Sliding Window)：结合单调队列，求定长窗口内的最大/最小值。

4. 滑动窗口的最值 (单调队列)

应用场景

定长滑动窗口极值：求一个固定长度为 $k$ 的窗口在数组上滑动时，每个窗口内部的最大值或最小值。
DP 优化：在动态规划中，如果状态转移方程长这样 $dp[i] = \max(dp[j]) + cost$ ，且 $i - k \le j < i$ （即依赖前面一段固定距离的最值），必须用单调队列优化，将 $O(N^2)$ 降维到 $O(N)$ （这就是大名鼎鼎的“单调队列优化 DP”）。

复杂度分析

时间复杂度：$O(N)$。很多人看到 for 循环里面套了 while 循环就觉得是 $O(N^2)$ 。其实不然，每个元素最多进队一次，出队一次，所以均摊下来每次操作的复杂度是绝对的 $O(1)$ ，总体 $O(N)$ 。
空间复杂度：$O(K)$。队列中最多同时存在 $K$ 个元素的索引。

核心代码模板

单调队列的本质是一个“双端队列 (std::deque)”。以下是以“求滑动窗口内的最大值”为例。核心思想是：“如果一个选手比你年轻（索引大），还比你强（值大），那你就永远没机会出头了，可以直接退役（从队尾出队）。”

C++

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3; // 窗口大小

    // 存储的是元素的【索引】，而不是具体的【值】
    deque<int> dq; 
    vector<int> ans;

    for (int i = 0; i < nums.size(); ++i) {
        // 1. 维护队头（寿命期检查）：
        // 当队头元素的老去（脱离了当前窗口的范围），必须被无情踢掉
        // 当前窗口的范围是 [i - k + 1, i]，所以如果队头索引 < i - k + 1，即 i - k >= 队头
        if (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // 2. 维护队尾（单调性维护）：
        // 遇到比队尾更强的“后浪”，直接把没用的“前浪”从队尾踢掉
        // （如果是求最小值，这里就把 < 改成 > 即可）
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }

        // 3. 进队：将当前元素索引入队
        dq.push_back(i);

        // 4. 记录答案：
        // 只有当窗口形成了完全体（即 i 走到了第 k-1 个位置以后），才开始输出结果
        if (i >= k - 1) {
            // 队头永远是当前窗口的最强者（最大值）
            ans.push_back(nums[dq.front()]);
        }
    }

    // 输出答案: [3, 3, 5, 5, 6, 7]
    for (int x : ans) cout << x << " ";
    cout << "\n";

    return 0;
}

前缀和与差分 (1D & 2D)：$O(1)$ 查询区间和，$O(1)$ 批量修改区间。

5. 前缀和与差分 (Prefix Sum & Difference Array)

核心心法

前缀和是用来优化“高频查询”的：一次预处理，以后每次查询区间和都是 $O(1)$ 。
差分是用来优化“高频修改”的：每次修改区间只需改端点 $O(1)$ ，最后统一计算。
它们互为逆运算：差分数组的前缀和，就是原数组；原数组的前缀和，就是前缀和数组。

复杂度分析

前缀和：预处理 $O(N)$ （二维 $O(N \times M)$ ），单次查询 $O(1)$ 。
差分：单次区间修改 $O(1)$ ，最后还原数组 $O(N)$ （二维 $O(N \times M)$ ）。

核心代码模板 1：一维与二维前缀和 (极速查询)

绝密技巧：写前缀和时，永远、绝对、必须把数组下标从 1 开始算！ 这样 $S[0] = 0$ ，查询 $[L, R]$ 时的公式 $S[R] - S[L-1]$ 遇到 $L=1$ 时才不会越界，省去了无数个恶心的 if 特判。

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // ==========================================
    // 1. 一维前缀和
    // ==========================================
    int n = 5;
    vector<long long> a = {0, 1, 2, 3, 4, 5}; // 强行补一个 0，让有效数据从索引 1 开始
    vector<long long> S(n + 1, 0);

    // 预处理一维前缀和
    for (int i = 1; i <= n; ++i) {
        S[i] = S[i - 1] + a[i];
    }
    // 查询区间 [L, R] = [2, 4] 的和
    int L = 2, R = 4;
    cout << "1D区间和: " << S[R] - S[L - 1] << "\n"; // 输出: 9 (2+3+4)


    // ==========================================
    // 2. 二维前缀和
    // ==========================================
    int N = 3, M = 4;
    // 构造一个 3x4 的矩阵，同样补 0，让下标从 1 开始
    vector<vector<long long>> matrix = {
        {0, 0, 0, 0, 0},
        {0, 1, 5, 6, 8},
        {0, 9, 6, 7, 3},
        {0, 5, 3, 2, 4}
    };
    vector<vector<long long>> S2D(N + 1, vector<long long>(M + 1, 0));

    // 预处理二维前缀和 (容斥原理)
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            S2D[i][j] = S2D[i - 1][j] + S2D[i][j - 1] - S2D[i - 1][j - 1] + matrix[i][j];
        }
    }

    // 查询左上角 (x1, y1) 到右下角 (x2, y2) 的子矩阵和
    int x1 = 2, y1 = 2, x2 = 3, y2 = 4;
    long long sub_sum = S2D[x2][y2] - S2D[x1 - 1][y2] - S2D[x2][y1 - 1] + S2D[x1 - 1][y1 - 1];
    
    cout << "2D矩阵和: " << sub_sum << "\n"; // 计算区域为原矩阵右下角 2x3 的块
    return 0;
}

核心代码模板 2：一维与二维差分 (极速修改)

应用场景：比如游戏里，法师放一个暴风雪（给一个矩形范围内的敌人全体扣 50 滴血），放了 10000 次，最后问每个敌人剩多少血。如果你用 for 循环一个个扣血必超时，用差分数组，放法术只需改 4 个点。

C++

#include <iostream>
#include <vector>

using namespace std;

// 辅助函数：一维差分区间加值
void add_1D(vector<long long>& D, int L, int R, long long v) {
    D[L] += v;
    D[R + 1] -= v; // 核心：因为 L 开始都加了 v，但在 R 之后并没有加，所以要在 R+1 的地方减掉
}

// 辅助函数：二维差分矩阵加值
void add_2D(vector<vector<long long>>& D, int x1, int y1, int x2, int y2, long long v) {
    D[x1][y1] += v;
    D[x1][y2 + 1] -= v;
    D[x2 + 1][y1] -= v;
    D[x2 + 1][y2 + 1] += v;
}

int main() {
    // ==========================================
    // 1. 一维差分实战
    // ==========================================
    int n = 5;
    // ⚠️ 易错点：差分数组必须要开 n + 2 的大小！因为修改 R 时会访问 R + 1
    vector<long long> D1(n + 2, 0); 
    
    // 进行 10000 次区间修改中的一次：给区间 [2, 4] 加上 10
    add_1D(D1, 2, 4, 10);
    
    // 所有修改结束后，通过计算 D1 的前缀和，还原出最终的原数组
    vector<long long> a1(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        a1[i] = a1[i - 1] + D1[i];
    }
    // a1 此时就是 [0, 0, 10, 10, 10, 0]


    // ==========================================
    // 2. 二维差分实战
    // ==========================================
    int N = 3, M = 4;
    // 同样，二维差分数组的边界也要多开一点，防溢出
    vector<vector<long long>> D2(N + 2, vector<long long>(M + 2, 0));

    // 给左上角 (1,1) 到右下角 (2,3) 的矩阵全体加上 100
    add_2D(D2, 1, 1, 2, 3, 100);

    // 所有修改结束后，通过求二维前缀和，还原出完整的二维矩阵
    vector<vector<long long>> final_matrix(N + 1, vector<long long>(M + 1, 0));
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            final_matrix[i][j] = final_matrix[i - 1][j] + final_matrix[i][j - 1] 
                                 - final_matrix[i - 1][j - 1] + D2[i][j];
        }
    }
    // final_matrix 就是经历了无数次技能轰炸后的最终状态

    return 0;
}

6. 离散化 (Discretization)

应用场景

配合高级数据结构：树状数组 (BIT) 或线段树 (Segment Tree) 的底层是普通数组，下标必须紧凑。离散化是它们处理大值域数据的绝对前提。
坐标压缩：二维矩形面积并/周长并（扫描线算法）。

复杂度分析

预处理时间复杂度：$O(N \log N)$（主要耗时在排序）。
单次查询时间复杂度：$O(\log N)$（使用二分查找获取新坐标）。
空间复杂度：$O(N)$（只需存储实际出现过的坐标）。

核心代码模板

这段模板浓缩了 C++ STL 的精华。请务必把 sort + unique + erase 这套连招练成肌肉记忆。

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 假设这些是题目给出的稀疏且极大的坐标点
    // 包含重复元素，以及负数和极大的正数
    vector<int> raw_coords = {10, 200000000, 10, 5000, 999999999, -100};

    // 1. 收集所有需要离散化的值
    vector<int> vals = raw_coords; // 实际做题时，可能还要把查询的边界坐标也塞进来

    // 2. 核心三连击：排序 + 去重 + 删除
    sort(vals.begin(), vals.end());
    // unique 会把重复的元素移到末尾，并返回去重后有效元素的结束迭代器
    // erase 会把这些移到末尾的垃圾元素彻底从 vector 中物理删除
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    // 3. 编写离散化映射函数 (利用二分查找)
    // 传入一个原始极大的真实坐标，返回它离散化后极其紧凑的相对坐标
    auto get_id = [&](int x) {
        // lower_bound 找到元素位置
        // distance 计算它距离首元素的偏移量
        // ⚠️ 极其重要：最后必须 +1。让离散化后的坐标从 1 开始！
        return distance(vals.begin(), lower_bound(vals.begin(), vals.end(), x)) + 1;
    };

    // 4. 见证奇迹的时刻
    cout << "--- 离散化映射结果 ---\n";
    for (int x : raw_coords) {
        cout << "原坐标: " << x << " \t-> 离散化后新坐标: " << get_id(x) << "\n";
    }
    
    /* 输出预期：
       原坐标: 10         -> 离散化后新坐标: 2
       原坐标: 200000000  -> 离散化后新坐标: 4
       原坐标: 10         -> 离散化后新坐标: 2
       原坐标: 5000       -> 离散化后新坐标: 3
       原坐标: 999999999  -> 离散化后新坐标: 5
       原坐标: -100       -> 离散化后新坐标: 1
    */

    return 0;
}

7. 位运算子集枚举 (Bitwise Subset Enumeration)

应用场景

暴力穷举组合：数据量 $N \le 20$ 的背包问题、凑数问题（不需要写繁琐的递归 DFS，几行循环搞定）。
状态压缩 DP (状压 DP) 的基石：旅行商问题 (TSP)、哈密顿路径。利用整数代表状态，作为 DP 数组的维度（如 $dp[state][i]$ ）。
子集的子集枚举：在一些极难的状压 DP 中，需要枚举当前状态的所有有效子状态。

复杂度分析

全子集枚举时间复杂度：$O(N \cdot 2^N)$。外层循环 $2^N$ 种状态，内层循环 $N$ 次提取位。
子集的子集枚举时间复杂度：$O(3^N)$。这是一个极其震撼的数学结论，而不是直觉上的 $O(4^N)$ 。
空间复杂度：$O(1)$。没有任何递归调用栈的开销。

核心代码模板 1：常规子集枚举 ($O(2^N)$)

思想：一个大小为 $N$ 的数组，有 $2^N$ 种组合方式。我们直接让一个整数 mask 从 $0$ 循环到 $2^N - 1$ 。

例如 $N=3$ ，mask = 5（二进制 101），就代表选中了第 0 个和第 2 个元素。

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<string> items = {"苹果", "香蕉", "橘子"};
    int n = items.size();

    // 1 << n 相当于 2^n。对于 n=3，1<<3 就是 8，循环区间 [0, 7]
    int total_states = 1 << n; 

    // 外层循环：遍历所有 2^n 种状态
    for (int mask = 0; mask < total_states; ++mask) {
        cout << "状态 " << mask << " (二进制组合): { ";
        
        // 内层循环：检查当前状态 mask 的第 i 位是否为 1
        for (int i = 0; i < n; ++i) {
            // (mask >> i) & 1 可以提取出 mask 的第 i 位
            if ((mask >> i) & 1) {
                cout << items[i] << " ";
            }
        }
        cout << "}\n";
    }
    
    /* 输出预期：
       状态 0 (二进制组合): { }
       状态 1 (二进制组合): { 苹果 }
       状态 2 (二进制组合): { 香蕉 }
       状态 3 (二进制组合): { 苹果 香蕉 }
       状态 4 (二进制组合): { 橘子 }
       状态 5 (二进制组合): { 苹果 橘子 }
       ...
    */
    return 0;
}

核心代码模板 2：子集的子集枚举 ($O(3^N)$) —— 竞赛高级神技

应用场景：假设你当前拥有一个状态 mask（比如 101，拥有苹果和橘子），你需要高效地枚举出它的所有子状态（即 101, 100, 001）。

如果从 $0$ 遍历到 mask 去逐个判断，包含大量无效状态；利用下面这行魔法位运算，可以精准且毫无冗余地跳过所有无效状态。

C++

#include <iostream>
#include <bitset>

using namespace std;

int main() {
    int mask = 0b1010; // 当前状态（十进制 10）：假设只拥有第 1 位和第 3 位
    
    cout << "原状态: " << bitset<4>(mask) << "\n";

    // 魔法公式：sub = (sub - 1) & mask
    // 这个公式会极其巧妙地向下“借位”，精准命中下一个有效的子集，绝对不会遍历多余的 0！
    for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
        cout << "有效子集: " << bitset<4>(sub) << "\n";
    }
    
    // 注意：上述循环会漏掉空集 (0000)。如果业务逻辑需要空集，可以在循环外单独处理。
    
    /* 输出预期：
       有效子集: 1010
       有效子集: 1000
       有效子集: 0010
    */
    return 0;
}

二、高级数据结构 (Advanced Data Structures)

STL 无法直接提供，必须自己手写的“大杀器”。

8. 单调栈 (Monotonic Stack)

应用场景

Next Greater Element (下一个更大元素)：例如“每日温度”问题，求还要等几天才能碰到比今天更高的温度。
最大矩形面积 (Largest Rectangle in Histogram)：以当前柱子为高，能向左右两边延展多远（即找左右两边第一个比它矮的柱子）。
接雨水 (Trapping Rain Water)：找左右两边第一个比当前凹陷处高的墙壁。

复杂度分析

时间复杂度：$O(N)$。别看 for 循环里套了个 while，每个元素在整个遍历过程中最多入栈一次、出栈一次，均摊下来的时间复杂度是绝对的线性的 $O(1)$ 。
空间复杂度：$O(N)$。最坏情况下（例如数组完全单调），所有元素都压在栈里。

核心代码模板：正向遍历法 (推荐，适用性极强)

对于寻找“右边第一个比它大”的问题，有两种遍历思路：逆向遍历和正向遍历。

强烈推荐“正向遍历存索引”的写法，因为这符合人类从左往右阅读的直觉，且能够同时求出“目标值”和“距离差”。

核心心法：栈里存放的是那些“还没有找到下一个更大元素”的倒霉蛋。

当一个新的元素到来时，如果它比栈顶元素大，那么它就是栈顶元素苦苦寻找的那个“更大元素”。栈顶元素得救，弹出；继续比较下一个栈顶，直到栈顶比它大，或者栈为空，然后把当前元素压入栈底，成为新的倒霉蛋。

C++

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 题目：找出数组中每个元素【右边第一个比它大的元素】
    // 如果找不到，则结果为 -1。
    vector<int> nums = {2, 1, 5, 6, 2, 3};
    int n = nums.size();
    
    // 初始化答案数组，全部默认填上 -1，极其优雅，省去了后续处理找不到情况的麻烦
    vector<int> ans(n, -1);
    
    // 单调栈：⚠️ 永远存【索引】，而不是存值！
    // 维护一个单调递减的栈
    stack<int> st;

    for (int i = 0; i < n; ++i) {
        // 当前元素 nums[i] 就像一个来踢馆的强者
        // 只要栈不为空，且当前元素大于栈顶元素（说明栈顶元素遇到了比它大的目标）
        while (!st.empty() && nums[i] > nums[st.top()]) {
            // 记录答案：栈顶元素右侧第一个比它大的值就是 nums[i]
            int top_index = st.top();
            ans[top_index] = nums[i]; 
            
            // 如果题目问的是“距离”（比如还要等几天），写成：ans[top_index] = i - top_index;
            
            // 栈顶元素已经找到了答案，功成身退
            st.pop();
        }
        
        // 当前元素入栈，等待未来比它更大的元素来拯救它
        st.push(i);
    }

    // 此时还在栈里的元素，说明它们右边根本没有比它们更大的数，保持默认的 -1 即可。
    
    for (int x : ans) {
        cout << x << " "; 
    }
    // 输出预期: 5 5 6 -1 3 -1
    cout << "\n";

    return 0;
}

9. 并查集 (Disjoint Set Union, DSU)

应用场景

动态连通性问题：判断无向图中有几个连通块，或者查询图中任意两点是否连通（如社交网络中的好友关系）。
最小生成树 (MST)：Kruskal 算法的核心，用于在加边时快速判断是否产生环。
图的判环：在无向图中，如果一条边的两个端点已经属于同一个集合，再连边必产生环。
高级扩展：种类并查集（解决“敌人的敌人是朋友”的阵营问题）、带权并查集（解决带有距离/数值传递关系的连通性问题）。

复杂度分析

时间复杂度：单次查询 find 和合并 unite 的均摊时间复杂度为 $O(\alpha(N))$ 。这里的 $\alpha$ 是反阿克曼函数，在宇宙中任何可观测的数据规模下，$\alpha(N) \le 4$。因此，时间复杂度可以视作绝对的 $O(1)$ 。
空间复杂度：$O(N)$，需要数组来存储每个节点的“上级”以及集合的“大小”。

核心代码模板：面向对象封装版 (竞赛与面试首选)

早期写 C 语言时，大家喜欢开几个全局数组 fa[]，但在现代 C++ 中，极其强烈建议把并查集封装成一个 struct 或 class。

这样不仅避免了全局变量污染，而且在面对“一张图里需要多个并查集”的毒瘤题时可以直接实例化，降维打击。

这个模板同时包含了“路径压缩 (Path Compression)”和“按秩/按大小合并 (Union by Size)”双重优化。

C++

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

// 封装的并查集结构体
struct DSU {
    vector<int> parent; // 记录每个节点的上级（父节点）
    vector<int> size;   // 记录每个集合的大小（只有根节点的 size 有效）
    int count;          // 记录当前共有多少个连通块

    // 构造函数：初始化并查集
    DSU(int n) {
        parent.resize(n);
        size.assign(n, 1); // 初始时，每个节点自成一派，大小为 1
        count = n;         // 初始有 n 个连通块
        
        // C++ 神器 iota：用 0, 1, 2... n-1 填满 parent 数组
        // 即初始时，每个人的老大都是自己
        iota(parent.begin(), parent.end(), 0); 
    }

    // 核心 1：查找操作 (带路径压缩)
    int find(int x) {
        if (parent[x] != x) {
            // 递归寻找根节点，并在回溯时直接把自己的上级改为“最顶层的老大”
            // 这就是路径压缩，下次再查直接 O(1)
            parent[x] = find(parent[x]); 
        }
        return parent[x];
    }

    // 核心 2：合并操作 (按大小合并)
    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return false; // 两人本来就是一伙的，合并失败（说明产生了环）
        }

        // 按大小合并优化：永远把小帮派合并到大帮派里，防止树退化成链表
        if (size[rootX] < size[rootY]) {
            swap(rootX, rootY); // 保证 rootX 是大帮派
        }

        parent[rootY] = rootX;      // 小帮派的老大拜大帮派的老大为师
        size[rootX] += size[rootY]; // 大帮派吸收小帮派的人数
        count--;                    // 连通块总数减一

        return true; // 合并成功
    }

    // 附加功能：查询两个节点是否连通
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    int n = 5; // 假设有 5 个人，编号 0 到 4
    DSU dsu(n);

    dsu.unite(0, 1);
    dsu.unite(1, 2);

    cout << "0 和 2 是一伙的吗？ " << (dsu.isConnected(0, 2) ? "Yes" : "No") << "\n";
    cout << "0 和 3 是一伙的吗？ " << (dsu.isConnected(0, 3) ? "Yes" : "No") << "\n";
    cout << "当前共有几个帮派？ " << dsu.count << "\n";
    
    /* 输出预期：
       0 和 2 是一伙的吗？ Yes
       0 和 3 是一伙的吗？ No
       当前共有几个帮派？ 3
    */
    return 0;
}

10. 树状数组 (Fenwick Tree / BIT)

应用场景

动态前缀和：原生的前缀和数组一旦建立，如果修改原数组的一个值，更新前缀和需要 $O(N)$ 。树状数组能让“修改单个值”和“查询前缀和”全部变成极速的 $O(\log N)$ 。
逆序对统计 (Inversions)：在一个数组中，找有多少对 $(i, j)$ 满足 $i < j$ 且 $nums[i] > nums[j]$ 。这是各大厂笔试的必考经典题。
区间修改 + 单点查询：利用我们在基础算法中学的差分数组，把树状数组套在差分数组上，就能反向实现这个功能。

复杂度分析

时间复杂度：单点修改 add 和区间查询 query 均为 $O(\log N)$ 。常数极小，比线段树快至少 3 倍。建树可以连续调用 add，总时间 $O(N \log N)$ （也有 $O(N)$ 的建树魔法，但竞赛中很少用，因为 $N \log N$ 已经够快了）。
空间复杂度：$O(N)$。只需要一个和原数组一样大的数组。

核心代码模板：面向对象封装版

树状数组的核心全在一个被称为 lowbit 的位运算公式里：x & (-x)。

它能提取出一个数字二进制表示中，最低位的那个 1 及其后面的 0。通过不断加减 lowbit，我们就能在巨大的数轴上像跳远一样快速定位区间。

C++

#include <iostream>
#include <vector>

using namespace std;

// 封装的树状数组结构体
// ⚠️ 树状数组的管辖范围必须从 1 开始！绝对不能传入下标 0！
struct BIT {
    int n;
    vector<long long> tree;

    // 构造函数：初始化大小，注意多开一位，因为下标必须从 1 开始
    BIT(int n) {
        this->n = n;
        tree.assign(n + 1, 0); 
    }

    // 魔法神技：提取二进制最低位的 1
    int lowbit(int x) {
        return x & (-x);
    }

    // 核心 1：单点修改 (在原数组的第 i 个位置加上 v)
    // 逻辑：一人升职，所有直接/间接管辖他的“上级”都要跟着加薪
    void add(int i, long long v) {
        while (i <= n) {
            tree[i] += v;
            i += lowbit(i); // i 不断往右上方跳，寻找上级
        }
    }

    // 核心 2：前缀和查询 (求原数组区间 [1, i] 的累加和)
    // 逻辑：把当前区域拆分成几个独立的“大区块”，逐个拼凑起来
    long long query(int i) {
        long long sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowbit(i); // i 不断往左下方跳，寻找拼图块
        }
        return sum;
    }

    // 衍生技能：区间查询 (求原数组区间 [L, R] 的累加和)
    // 逻辑：利用前缀和的相减性质
    long long queryRange(int L, int R) {
        return query(R) - query(L - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 原数组（我们默认索引从 1 开始）：[空, 10, 20, 30, 40, 50]
    int n = 5;
    BIT bit(n);

    // 建树：把初始值一个个加进去
    vector<int> nums = {0, 10, 20, 30, 40, 50}; // 第 0 个不用
    for (int i = 1; i <= n; ++i) {
        bit.add(i, nums[i]);
    }

    // 查询区间 [2, 4] 的和 (应为 20+30+40 = 90)
    cout << "初始区间 [2, 4] 的和: " << bit.queryRange(2, 4) << "\n";

    // 发生修改：将第 3 个位置的数加 5 (30 变成 35)
    bit.add(3, 5);

    // 再次查询区间 [2, 4] 的和 (应为 20+35+40 = 95)
    cout << "修改后区间 [2, 4] 的和: " << bit.queryRange(2, 4) << "\n";

    return 0;
}

11.线段树 (Segment Tree) 附 Lazy Tag 懒标记

核心心法：懒标记 (Lazy Tag) —— 拖延症的艺术

如果你要给区间 $[1, 10000]$ 里的所有数字加上 $5$ ，难道要修改 $10000$ 个叶子节点吗？绝不！

懒标记的核心思想是：“只要你当前不查询这部分的数据，我就先把要加的数字记在父节点的小本本（懒标记）上，绝不往下发任务。” 只有当未来某次查询或修改被迫要进入子区间时，父节点才会把小本本上的任务“推”给两个儿子（这叫 push_down 操作）。这就把原本 $O(N)$ 的区间修改，硬生生压成了 $O(\log N)$ ！

应用场景

高频区间修改 + 区间查询：给某个大区间加上一个数/乘上一个数/全部重置为一个数，然后查询另一个大区间的和/极值。
扫描线算法：计算二维平面上多个矩形交集的面积或周长。

复杂度分析

时间复杂度：建树 $O(N)$ ；单次区间修改和区间查询均为 $O(\log N)$ 。
空间复杂度：$O(N)$，但必须开 $4N$ 的数组大小！

核心代码模板：面向对象封装版 (区间加法 + 区间求和)

这是一个工业级、防越界、纯封装的线段树模板。请把 push_up 和 push_down 的逻辑当成艺术品一样反复品鉴。

C++

#include <iostream>
#include <vector>

using namespace std;

// 封装的线段树结构体 (以维护区间和为例)
struct SegmentTree {
    int n;
    vector<long long> tree; // 存储线段树节点的值 (区间和)
    vector<long long> lazy; // 存储懒标记 (延迟更新的值)

    // 构造函数：⚠️ 线段树的数组大小必须开到 4 * N！
    SegmentTree(int n) {
        this->n = n;
        tree.assign(4 * n + 1, 0);
        lazy.assign(4 * n + 1, 0);
    }

    // 核心 1：向上合并 (Push Up)
    // 根据两个儿子的值，更新父亲的值
    void push_up(int p) {
        tree[p] = tree[p * 2] + tree[p * 2 + 1];
    }

    // 核心 2：向下传递懒标记 (Push Down) - 【全树最精髓的地方】
    // p: 当前节点编号; l: 当前区间左端点; r: 当前区间右端点
    void push_down(int p, int l, int r) {
        if (lazy[p] != 0) {
            int mid = l + (r - l) / 2;
            int left_child = p * 2;
            int right_child = p * 2 + 1;

            // 1. 把懒标记传递给左右儿子
            lazy[left_child] += lazy[p];
            lazy[right_child] += lazy[p];

            // 2. 更新左右儿子的真实值 
            // 区间和 = 原来的和 + 增加的值 * 区间的长度！
            tree[left_child] += lazy[p] * (mid - l + 1);
            tree[right_child] += lazy[p] * (r - mid);

            // 3. 父亲的任务已经下达，清空自己的小本本
            lazy[p] = 0;
        }
    }

    // 核心 3：建树 (Build)
    void build(int p, int l, int r, const vector<int>& arr) {
        if (l == r) {
            tree[p] = arr[l];
            return;
        }
        int mid = l + (r - l) / 2;
        build(p * 2, l, mid, arr);         // 建左子树
        build(p * 2 + 1, mid + 1, r, arr); // 建右子树
        push_up(p);                        // 儿子建好了，更新父亲
    }

    // 核心 4：区间修改 (Update)
    // 将区间 [ql, qr] 里的每个数都加上 val
    void update(int p, int l, int r, int ql, int qr, long long val) {
        // 场景 A：当前区间被完全包含在目标区间内，直接打标记，绝对不往下走了！(拖延症发作)
        if (ql <= l && r <= qr) {
            tree[p] += val * (r - l + 1); // 维护区间和
            lazy[p] += val;               // 记在小本本上
            return;
        }

        // 场景 B：当前区间与目标区间有交集，但没有完全包含，必须被迫往下走
        push_down(p, l, r); // ⚠️ 往下走之前，必须先把以前积压的懒标记发下去！

        int mid = l + (r - l) / 2;
        if (ql <= mid) update(p * 2, l, mid, ql, qr, val);         // 左边有交集
        if (qr > mid)  update(p * 2 + 1, mid + 1, r, ql, qr, val); // 右边有交集

        push_up(p); // 儿子更新完了，最后更新一下父亲
    }

    // 核心 5：区间查询 (Query)
    // 查询区间 [ql, qr] 的总和
    long long query(int p, int l, int r, int ql, int qr) {
        // 场景 A：完全包含，直接返回节点存的现成答案
        if (ql <= l && r <= qr) {
            return tree[p];
        }

        // 场景 B：被迫分裂查询
        push_down(p, l, r); // ⚠️ 往下查之前，如果有历史积压任务，必须先结清！

        int mid = l + (r - l) / 2;
        long long res = 0;
        if (ql <= mid) res += query(p * 2, l, mid, ql, qr);
        if (qr > mid)  res += query(p * 2 + 1, mid + 1, r, ql, qr);
        
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 原数组（依然默认下标从 1 开始）
    vector<int> arr = {0, 10, 11, 12, 13, 14}; 
    int n = 5;

    SegmentTree seg(n);
    // 根节点编号永远是 1，管辖区间是 [1, n]
    seg.build(1, 1, n, arr); 

    // 查询初始区间 [2, 4] 的和 (11 + 12 + 13 = 36)
    cout << "初始 [2, 4] 区间和: " << seg.query(1, 1, n, 2, 4) << "\n";

    // 给区间 [1, 3] 全体加上 5
    seg.update(1, 1, n, 1, 3, 5);

    // 再次查询区间 [2, 4] 的和
    // 现在数组变成了: [15, 16, 17, 13, 14]
    // 区间 [2, 4] 的和应该是 16 + 17 + 13 = 46
    cout << "修改后 [2, 4] 区间和: " << seg.query(1, 1, n, 2, 4) << "\n";

    return 0;
}

12. ST 表 (Sparse Table)

应用场景

静态区间最值查询 (Static RMQ)：在固定不变的数组中，疯狂查询任意区间的最大值或最小值。
静态区间 GCD (最大公约数)：查询任意区间的 GCD。
结合树上问题：将树上的 LCA (最近公共祖先) 问题通过欧拉序转化为 RMQ 问题，使用 ST 表实现 $O(1)$ 极速查询。

核心心法：倍增思想 (Binary Lifting)

ST 表的本质是动态规划（DP）。我们预处理出从每个位置 $i$ 开始，长度为 $2^j$ 的区间内的最值。

查询时，如果要查长度为 $len$ 的区间，我们找到一个最大的 $k$ 使得 $2^k \le len$ 。然后把目标区间分成两块长度为 $2^k$ 的区间：一块紧贴左端点，一块紧贴右端点。这两块可能会重叠，但因为求的是“最值”，重叠完全不影响结果！这就是 $O(1)$ 极速查询的奥秘。

复杂度分析

时间复杂度：预处理 $O(N \log N)$ ；单次查询 $O(1)$ 。
空间复杂度：$O(N \log N)$（因为需要开一个两维数组）。

核心代码模板：面向对象封装版 (以区间最大值为例)

这段代码采用了现代 C++ 风格（下标从 0 开始），并且在查询时使用了 GCC 编译器的隐藏神技 __lg()，达到了极致的性能。

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct SparseTable {
    int n;
    int max_log;
    vector<vector<int>> st;

    // 构造函数：传入原始数组，完成 O(N log N) 的预处理
    SparseTable(const vector<int>& a) {
        n = a.size();
        // 计算最大可能需要的 2^k 中的 k
        // 32 - __builtin_clz(n) 就是 log2(n) 的高效写法，或者直接写 20
        max_log = 32 - __builtin_clz(n); 
        
        // st[i][j] 表示从索引 i 开始，长度为 2^j 的区间内的最大值
        st.assign(n, vector<int>(max_log, 0));

        // 1. 初始化长度为 2^0 (即长度为 1) 的区间
        for (int i = 0; i < n; ++i) {
            st[i][0] = a[i];
        }

        // 2. 动态规划预处理 (倍增递推)
        // ⚠️ 极其重要的循环顺序：必须先循环 j (区间长度)，再循环 i (起点)！
        for (int j = 1; j < max_log; ++j) {
            for (int i = 0; i + (1 << j) - 1 < n; ++i) {
                // 状态转移方程：
                // 长度为 2^j 的区间，可以拆分成两个相邻的长度为 2^(j-1) 的区间
                // 前一半：起点是 i
                // 后一半：起点是 i + 2^(j-1)
                st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    // O(1) 极速查询区间 [L, R] 的最大值 (闭区间，包含 L 和 R)
    int query(int L, int R) {
        if (L > R) swap(L, R); // 容错处理
        
        int len = R - L + 1;
        
        // __lg(len) 是 GCC 编译器自带的极速求以 2 为底的对数 (向下取整)
        // 相当于 floor(log2(len))
        int k = __lg(len); 
        
        // 取“靠左的长度为 2^k 的区间”和“靠右的长度为 2^k 的区间”两者的最大值
        return max(st[L][k], st[R - (1 << k) + 1][k]);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 原数组 (索引 0 开始): 0, 1, 2, 3, 4, 5, 6
    vector<int> nums = {5, 2, 4, 7, 3, 9, 1}; 
    
    // O(N log N) 建表
    SparseTable st(nums);

    // O(1) 查询区间 [1, 4] 的最大值 -> (2, 4, 7, 3) 里的最大值应为 7
    cout << "区间 [1, 4] 的最大值: " << st.query(1, 4) << "\n";

    // O(1) 查询区间 [4, 6] 的最大值 -> (3, 9, 1) 里的最大值应为 9
    cout << "区间 [4, 6] 的最大值: " << st.query(4, 6) << "\n";

    return 0;
}

13. 字典树 (Trie) 与 01-Trie

应用场景

字符串 Trie：搜索引擎的自动补全（前缀匹配）、敏感词过滤、大量字符串的快速查重、多模式串匹配（AC 自动机的前置基础）。
01-Trie：解决极其棘手的“最大异或和 (Maximum XOR)”问题。只要题目里出现“从数组中选两个数，使它们的异或值最大”，毫无疑问，直接上 01-Trie。

复杂度分析

时间复杂度：插入与查询均为 $O(L)$ 。其中 $L$ 是字符串的长度，或者数字的二进制位数（通常为 31）。与数组总共有多少个元素毫无关系！速度极快。
空间复杂度：$O(\text{字符集大小} \times \text{总节点数})$。对于小写字母是 $26 \times N$ ，对于 01-Trie 是 $2 \times 32N$ 。属于典型的空间换时间。

核心代码模板 1：经典字符串 Trie (数组静态分配法)

核心心法：把二维数组 nxt[p][c] 想象成一个巨大的迷宫。p 是你当前所在的房间号，c 是你要走的门（比如字母 'a' 就是 0 号门），nxt[p][c] 存的就是你推开这扇门后到达的下一个房间号。如果门后是 0，说明这是一条死路（该前缀不存在）。

C++

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 假设题目所有字符串的总长度不超过 100000
const int MAX_NODE = 100005;

struct Trie {
    // nxt[i][j] 表示节点 i 的第 j 个儿子的节点编号
    int nxt[MAX_NODE][26]; 
    // cnt[i] 表示以节点 i 结尾的字符串有多少个
    int cnt[MAX_NODE];     
    // idx 记录当前用到了第几个节点 (0 号节点永远是根节点)
    int idx;               

    Trie() {
        idx = 0; 
        // 在实际竞赛中，通常不写构造函数清空，而是靠多次测试用例间手动 clear
    }

    // 1. 插入字符串
    void insert(const string& s) {
        int p = 0; // 从根节点 (0 房间) 开始走
        for (char ch : s) {
            int c = ch - 'a'; // 将字母映射到 0~25 的门号
            
            // 如果这扇门后面没有房间 (值为 0)，我们就新建一个房间 (++idx)
            if (!nxt[p][c]) {
                nxt[p][c] = ++idx;
            }
            // 走到下一个房间
            p = nxt[p][c];
        }
        // 走完全部字符，在最终停下的房间里做一个标记
        cnt[p]++; 
    }

    // 2. 查找字符串精确匹配的个数
    int search(const string& s) {
        int p = 0;
        for (char ch : s) {
            int c = ch - 'a';
            // 如果中途没路了，说明这个字符串根本不存在
            if (!nxt[p][c]) return 0;
            p = nxt[p][c];
        }
        // 返回最终停下房间里的计数标记
        return cnt[p]; 
    }

    // 3. 查找是否包含某个前缀
    bool startsWith(const string& prefix) {
        int p = 0;
        for (char ch : prefix) {
            int c = ch - 'a';
            if (!nxt[p][c]) return false;
            p = nxt[p][c];
        }
        // 只要能走完，就说明前缀存在
        return true; 
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    
    cout << "查找 apple: " << trie.search("apple") << "\n";   // 1
    cout << "查找 app: " << trie.search("app") << "\n";       // 1
    cout << "查找 appl: " << trie.search("appl") << "\n";     // 0 (虽然是前缀，但不是一个完整的单词)
    cout << "是否有 app 前缀: " << trie.startsWith("app") << "\n"; // 1 (true)
    
    return 0;
}

核心代码模板 2：01-Trie (降维打击异或最值问题)

核心心法：把数字当成一个长度为 31 的二进制字符串插入字典树（高位在前）。

异或运算的规则是“不同为 1”。所以为了让异或和最大，在查询时，我们采用“贪心法则”：从最高位开始，尽量往与当前位相反的方向走！ 如果有相反的路，就一定走相反的路（能赚到一个高位的 1，比低位所有的 1 加起来都要大）；如果实在没路，再勉强走相同的路。

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_NODE = 100000 * 32; // N 个数字，每个数字最多 31 位

struct Trie01 {
    int nxt[MAX_NODE][2]; // 只有 0 和 1 两扇门
    int idx = 0;

    // 插入一个整数
    void insert(int x) {
        int p = 0;
        // ⚠️ 必须从最高位 (第 30 位) 往最低位 (第 0 位) 插入
        for (int i = 30; i >= 0; i--) {
            int u = (x >> i) & 1; // 提取第 i 位是 0 还是 1
            if (!nxt[p][u]) nxt[p][u] = ++idx;
            p = nxt[p][u];
        }
    }

    // 查询树中与 x 异或结果最大的数字，并返回这个最大异或和
    int query_max_xor(int x) {
        int p = 0;
        int max_res = 0;
        
        for (int i = 30; i >= 0; i--) {
            int u = (x >> i) & 1;
            int opposite = u ^ 1; // 渴望走的那条相反的路
            
            // 如果相反的路存在，果断走相反的路！
            if (nxt[p][opposite]) {
                max_res |= (1 << i); // 这一位异或结果变成了 1，计入答案
                p = nxt[p][opposite];
            } 
            // 否则只能被迫走相同的路，异或结果为 0，不产生增益
            else {
                p = nxt[p][u];
            }
        }
        return max_res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 经典题目：给定一个数组，求其中任意两个数异或的最大值
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    Trie01 trie;
    
    int max_xor_sum = 0;
    
    // 技巧：一边遍历，一边查询当前数字与前面已插入数字的最大异或和，然后再把自己插进去
    // 这能完美避免“自己异或自己”的陷阱
    trie.insert(nums[0]);
    for (int i = 1; i < nums.size(); ++i) {
        max_xor_sum = max(max_xor_sum, trie.query_max_xor(nums[i]));
        trie.insert(nums[i]);
    }

    cout << "数组中任意两数最大异或和: " << max_xor_sum << "\n"; // 输出 28 (5 ^ 25 = 28)
    
    return 0;
}

三、图论算法 (Graph Theory)

图论是区分选手水平的分水岭，需要极其稳定的模板。

最短路系列：

14. Dijkstra (堆优化版)

应用场景

GPS 导航/网络路由：求两点之间的物理最短路线、耗时最短网络节点。
状态空间的最少代价转移：很多隐式图问题（比如在网格图里带权重的上下左右移动），本质上也是求单源最短路。

复杂度分析

时间复杂度：$O(E \log V)$。其中 $E$ 是边数，$V$ 是节点数。普通的 Dijkstra 是 $O(V^2)$ ，在面对 $V = 10^5$ 的稀疏图时必死无疑；而加入优先队列（堆）后，我们能以 $O(\log V)$ 的速度瞬间找到当前离起点最近的节点。
空间复杂度：$O(V + E)$。邻接表存图需要 $O(V + E)$ ，距离数组和堆最多占用 $O(V)$ 或 $O(E)$ 。

核心代码模板：竞赛级邻接表 + priority_queue

这段模板极其标准，直接套用了 long long 防溢出，以及 C++ 的 pair 和 greater 语法来构建小顶堆。

C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 定义无穷大：使用 1e18 防止任何两个极大值相加导致 long long 溢出为负数
const long long INF = 1e18;

// 定义图的边结构体 (可读性远超单纯的 pair)
struct Edge {
    int to;
    long long weight;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 5; // 节点总数，编号 1 到 n
    
    // 邻接表建图：graph[u] 存储从 u 出发的所有边
    // 注意：节点编号从 1 开始，所以数组开 n + 1
    vector<vector<Edge>> graph(n + 1);

    // 假设添加几条有向边 (u -> v, 权重 w)
    graph[1].push_back({2, 10});
    graph[1].push_back({3, 3});
    graph[3].push_back({2, 4});
    graph[2].push_back({4, 2});
    graph[3].push_back({4, 8});
    graph[4].push_back({5, 7});

    /* ⚠️ 如果是【无向图】，千万别忘了正反建两次边！
       graph[u].push_back({v, w});
       graph[v].push_back({u, w}); 
    */

    int start = 1; // 设定起点

    // 1. 初始化距离数组，全部设为 INF
    vector<long long> dist(n + 1, INF);
    dist[start] = 0; // 起点到自己的距离是 0

    // 2. 初始化优先队列 (小顶堆)
    // 堆里存储 pair<当前最短距离, 节点编号>
    // ⚠️ 重点：pair 默认按第一个元素排序，所以必须把“距离”放前面！
    priority_queue<pair<long long, int>, 
                   vector<pair<long long, int>>, 
                   greater<pair<long long, int>>> pq;

    pq.push({0, start});

    // 3. Dijkstra 核心扩散过程
    while (!pq.empty()) {
        // 取出当前离起点最近的节点
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        // ⚠️ 极其关键的“延迟删除”优化 (懒惰删除)
        // 如果从堆里取出的距离，比记录的真实距离还要大，说明这是一个过时的、被淘汰的状态，直接丢弃！
        if (d > dist[u]) continue;

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

            // 松弛操作 (Relaxation)：如果绕道 u 能让到达 v 的距离更短，就更新
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                // 将更新后的更优状态压入堆中
                pq.push({dist[v], v}); 
            }
        }
    }

    // 4. 输出结果
    for (int i = 1; i <= n; ++i) {
        if (dist[i] == INF) cout << "节点 " << i << " 无法到达\n";
        else cout << "起点到节点 " << i << " 的最短距离为: " << dist[i] << "\n";
    }
    
    return 0;
}

15. SPFA (最短路快速算法 / 处理负权与判环)

应用场景

带有负权边的最短路：某些游戏或业务逻辑中，走某条路不仅不消耗体力，反而会“回血”（权重为负），求最终最大血量/最小消耗。
检测负权回路 (Negative Cycle)：如果图中存在一个圈，转一圈的总权重是负数，那意味着可以无限转圈来无限刷分/降低成本。SPFA 能敏锐地揪出这种“系统漏洞”。
费用流 (MCMF)：在高级图论网络流中，寻找增广路通常强依赖 SPFA。

复杂度分析

时间复杂度：平均情况 $O(k \cdot E)$ ，其中 $E$ 是边数，$k$ 是一个小常数（通常 $\le 2$ ）。最坏情况（被网格图/特殊图卡）：$O(V \cdot E)$，直接退化成毫无优化的 Bellman-Ford。
空间复杂度：$O(V + E)$（邻接表存图 + 队列 + 几个辅助数组）。

核心代码模板：SPFA 单源最短路与负环检测

这个模板包含了一个极其关键的辅助数组 cnt。它记录的是“从起点到节点 i 的最短路径上，一共包含了几条边”。利用这个数组，我们可以优雅地判断负环。

C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const long long INF = 1e18;

struct Edge {
    int to;
    long long weight;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 5; // 节点数 1~n
    vector<vector<Edge>> graph(n + 1);

    // 假设存在负权边
    graph[1].push_back({2, 2});
    graph[1].push_back({3, 4});
    graph[2].push_back({3, -5}); // 负权边！
    graph[3].push_back({4, 2});
    graph[4].push_back({5, 3});
    // 如果把上面某条边改成产生循环且和为负数，比如 graph[4].push_back({2, -10})，就会触发负环警报

    int start = 1;

    vector<long long> dist(n + 1, INF);
    vector<bool> in_queue(n + 1, false); // 核心标记：节点当前是否在队列中？
    vector<int> cnt(n + 1, 0);           // 记录到达某个节点的最短路包含的【边数】

    queue<int> q;

    // 1. 初始化起点
    dist[start] = 0;
    q.push(start);
    in_queue[start] = true; // 起点入队

    bool has_negative_cycle = false;

    // 2. SPFA 核心扩散
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false; // 出队后立刻解除标记，因为它未来可能被再次更新并重新入队！

        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            long long w = edge.weight;

            // 松弛操作
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                
                // ⚠️ 判环核心逻辑：到达 v 的边数 = 到达 u 的边数 + 1
                cnt[v] = cnt[u] + 1;
                
                // 鸽巢原理：一条简单路径最多包含 n-1 条边。
                // 如果边数 >= n，说明路上一定经过了超过 n 个点，必然存在负权回路！
                if (cnt[v] >= n) {
                    has_negative_cycle = true;
                    break;
                }

                // 如果 v 被更新了，且 v 目前不在队列里，就把 v 塞进队列去更新别人
                if (!in_queue[v]) {
                    q.push(v);
                    in_queue[v] = true;
                }
            }
        }
        if (has_negative_cycle) break;
    }

    // 3. 结果输出
    if (has_negative_cycle) {
        cout << "警告：图中存在负权回路，最短路不存在 (可以无限减小)！\n";
    } else {
        for (int i = 1; i <= n; ++i) {
            if (dist[i] == INF) cout << "节点 " << i << " 无法到达\n";
            else cout << "起点到节点 " << i << " 的最短距离为: " << dist[i] << "\n";
        }
    }

    return 0;
}

Floyd-Warshall：多源最短路，极其优美的三重循环。

16.Floyd-Warshall (多源最短路)

应用场景

多源最短路径：当题目不仅问你 $A$ 到 $B$ 的距离，还频繁询问任意点 $X$ 到任意点 $Y$ 的距离时（例如在一张小型地图上任意两城市间的物流成本查询）。
传递闭包 (Transitive Closure)：给定一些人与人之间的连通关系（比如 A 认识 B，B 认识 C），求任意两人最终是否能间接认识。
极小图的万能解药：当图中节点数 $N \le 400$ ，且带有负权边时，与其写长篇大论的 SPFA，不如直接花 30 秒敲一个 Floyd。

复杂度分析

时间复杂度：绝对死板的 $O(N^3)$ 。由于常数极小，现代计算机在一秒内大约能承受 $N = 400$ 左右的数据规模。如果 $N \ge 1000$ ，请立刻放弃 Floyd。
空间复杂度：$O(N^2)$。只需一个二维邻接矩阵存图。

核心代码模板：图论最美三重循环

Floyd 的本质是动态规划 (DP)。状态转移方程的核心思想是：“能否通过允许引入节点 $k$ 作为中转站，让节点 $i$ 到节点 $j$ 的距离变得更短？”

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 使用 1e18 作为 INF 防止溢出，如果是 int 类型可用 1e9
const long long INF = 1e18; 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 4; // 节点数 1 到 4
    
    // 初始化二维邻接矩阵
    vector<vector<long long>> dist(n + 1, vector<long long>(n + 1, INF));

    // 1. 初始化基础状态：自己到自己的距离为 0
    for (int i = 1; i <= n; ++i) {
        dist[i][i] = 0;
    }

    // 2. 读入题目给定的有向边/无向边
    // 假设读入了以下三条边：
    dist[1][2] = 2; // 1 -> 2，权重 2
    dist[2][3] = 3; // 2 -> 3，权重 3
    dist[1][4] = 8; // 1 -> 4，权重 8
    
    // 如果是无向图，别忘了加上反向边：dist[v][u] = w;
    // ⚠️ 易错点：如果有重边（两个节点间有多条边），读入时要取最小值！
    // 比如：dist[u][v] = min(dist[u][v], w);

    // ==========================================
    // 3. Floyd 核心魔法：三重循环
    // ==========================================
    // 最外层循环 k：允许作为【中转站】的节点
    for (int k = 1; k <= n; ++k) {
        // 内层双重循环 i, j：遍历图中的每一对【起点】和【终点】
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                // 安全防线：如果 i 到 k 或者 k 到 j 根本不通，就不要强行相加
                // 这能防止图中有负权边时，INF + (-5) 变成一个略小于 INF 的伪合法值
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    // 状态转移：i 到 j 的最短路 = min(不经过 k, 经过 k 中转)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // 4. 查询任意两点的最短路
    if (dist[1][3] == INF) cout << "1 和 3 不连通\n";
    else cout << "1 到 3 的最短距离: " << dist[1][3] << "\n"; // 输出 5 (1->2->3)

    return 0;
}

最小生成树 (MST)：

17. 最小生成树 (Kruskal 算法)

应用场景

网络/公路/管道铺设规划：保证全图连通的前提下，使得总施工成本最小。
聚类算法 (Clustering)：在机器学习中，Kruskal 算法的中间过程可以用来实现基于距离的层次聚类（断开 MST 中最长的 $K-1$ 条边，即可得到 $K$ 个聚类）。

复杂度分析

时间复杂度：$O(E \log E)$ 或 $O(E \log V)$ 。算法的瓶颈完全在于对所有边进行排序，而后面并查集的查询和合并操作是近乎 $O(1)$ 的。在边数 $E$ 不是极度稠密的图中，Kruskal 跑得飞快。
空间复杂度：$O(V + E)$。需要存储所有的边，以及开辟大小为 $V$ 的并查集数组。

核心代码模板：贪心排序 + 并查集

写 Kruskal 算法最大的乐趣在于：你完全不需要复杂的邻接表（vector<vector>），只需要一个最朴素的一维边集数组即可。我们将刚才学过的“并查集”无缝衔接进来，作为判断“是否产生环”的完美裁判。

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

// ==========================================
// 1. 搬来我们之前封装好的并查集 (精简版)
// ==========================================
struct DSU {
    vector<int> parent;
    DSU(int n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0); // 初始化，各自为王
    }
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false; // 属于同一个集合，连边会产生环！
        parent[rootY] = rootX;            // 合并
        return true;
    }
};

// ==========================================
// 2. 定义边结构体，并重载 < 运算符
// ==========================================
struct Edge {
    int u, v;
    long long weight;

    // 核心贪心逻辑：让 sort() 函数按权重从小到大排序
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 4; // 节点数 (假设编号 1 到 4)
    vector<Edge> edges;

    // 随便塞几条无向边进去 (起点, 终点, 权重)
    edges.push_back({1, 2, 2});
    edges.push_back({1, 3, 4});
    edges.push_back({1, 4, 1});
    edges.push_back({2, 3, 3});
    edges.push_back({3, 4, 5});

    // 3. 第一步：将所有边按权重【从小到大】排序 (O(E log E))
    sort(edges.begin(), edges.end());

    // 4. 第二步：初始化并查集与统计变量
    DSU dsu(n);
    long long mst_cost = 0; // 记录最小生成树的总权重
    int edge_count = 0;     // 记录成功连接的边数

    // 5. 第三步：贪心挑边
    for (const Edge& edge : edges) {
        // 如果 u 和 v 还没连通，就将它们连通
        if (dsu.unite(edge.u, edge.v)) {
            mst_cost += edge.weight; // 计入总成本
            edge_count++;            // 成功连接的边数 +1
            
            // 💡 优化：一棵有 N 个节点的树，必然只有 N - 1 条边
            // 一旦凑齐了 N - 1 条边，直接提前下班！
            if (edge_count == n - 1) {
                break;
            }
        }
    }

    // 6. 结果判定：图是否真的连通？
    if (edge_count == n - 1) {
        cout << "构建最小生成树成功！总造价为: " << mst_cost << "\n";
    } else {
        // 如果挑出来的边数不足 n - 1，说明图中存在“孤岛”，根本无法全图连通
        cout << "构建失败：图不连通，无法生成生成树！\n";
    }

    return 0;
}

18. 拓扑排序 (Topological Sort - Kahn 算法)

应用场景

任务调度与课程安排：如 LeetCode 极其经典的“课程表”系列问题（先修课规划）。
工程编译顺序：比如 Make/CMake 等构建工具，通过拓扑排序决定先编译哪个库、后编译哪个可执行文件。
有向图判环：这是判断一个有向图是否存在“死锁（环）”的最快、最直观的方法。
DAG（有向无环图）上的动态规划：在图上跑 DP 前，必须先得到拓扑序，以保证状态转移时，依赖的前置状态都已经计算完毕。

复杂度分析

时间复杂度：$O(V + E)$。其中 $V$ 是节点数，$E$ 是边数。每个节点最多入队一次、出队一次，每条边最多被遍历一次，速度极快。
空间复杂度：$O(V + E)$。邻接表存图需要 $O(V + E)$ ，入度数组和队列需要 $O(V)$ 。

核心代码模板：Kahn 算法 (基于 BFS 与入度表)

Kahn 算法的核心思想极其符合人类直觉：

每次都从图里挑出那些“没有任何前置依赖（入度为 0）”的节点执行；执行完之后，把它们对后续节点的“依赖封锁”解除（子节点的入度减 1）。一直重复，直到所有节点都被执行完毕。

C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 5; // 假设有 5 个任务，编号 1 到 5
    
    // 邻接表建图：graph[u] 存储 u 执行完后，解锁了哪些后续节点
    vector<vector<int>> graph(n + 1);
    
    // 入度数组：in_degree[i] 表示任务 i 还有几个前置任务没完成
    vector<int> in_degree(n + 1, 0);

    // 假设读入一些依赖关系 (u -> v, 意味着 u 是 v 的前置条件)
    // 任务 1 解锁 2 和 3；2 和 3 解锁 4；4 解锁 5
    vector<pair<int, int>> edges = {{1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5}};
    
    for (auto edge : edges) {
        int u = edge.first;
        int v = edge.second;
        graph[u].push_back(v);
        in_degree[v]++; // 被指向的节点，入度 + 1
    }

    // 1. 初始化：把所有【没有任何前置依赖（入度为 0）】的节点全部扔进队列
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    // 存储最终的通关顺序列
    vector<int> topo_order;

    // 2. BFS 核心扩散
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        topo_order.push_back(u); // 任务 u 执行完毕，加入通关列表

        // 遍历 u 解锁的所有后续任务 v
        for (int v : graph[u]) {
            in_degree[v]--; // 解除一层依赖限制
            
            // 如果 v 的所有前置任务都已经干掉了 (入度归零)
            if (in_degree[v] == 0) {
                q.push(v); // 恭喜，任务 v 可以开始执行了，入队！
            }
        }
    }

    // 3. 终极审判：是否通关了所有任务？(有向图判环)
    // 如果图中存在环 (例如 A 依赖 B，B 依赖 C，C 依赖 A)
    // 那么这几个节点的入度永远不可能减到 0，也就永远进不了队列
    if (topo_order.size() == n) {
        cout << "拓扑排序成功，通关顺序为: ";
        for (int task : topo_order) cout << task << " ";
        cout << "\n";
    } else {
        cout << "死锁警告：图中存在环，存在无法完成的任务！\n";
    }

    return 0;
}

19.强连通分量与双连通分量 (Tarjan)：

求有向图的强连通分量 (SCC) 并缩点。
求无向图的割点 (Articulation Points) 和桥 (Bridges)。

1. 有向图：求强连通分量 (SCC) 并缩点

应用场景：一张错综复杂的有向图由于存在环，无法进行拓扑排序或动态规划。通过 Tarjan 找出所有环，把每个环“打包”成一个超级节点。整张图瞬间变成有向无环图 (DAG)。

C++

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

const int MAXN = 100005;

// 原图与缩点后的新图
vector<int> graph[MAXN];
vector<int> dag_graph[MAXN]; 

// Tarjan 核心数组
int dfn[MAXN], low[MAXN], timestamp = 0;
stack<int> stk;
bool in_stk[MAXN]; // 判断节点是否在栈中（有向图防错核心）

// 缩点后信息
int scc_cnt = 0;       // 强连通分量的总数
int scc_id[MAXN];      // scc_id[u] 表示原节点 u 属于哪个超级节点
int scc_size[MAXN];    // scc_size[i] 表示第 i 个超级节点包含了几个原节点

void tarjan_scc(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    in_stk[u] = true;

    for (int v : graph[u]) {
        if (!dfn[v]) {
            // 没访问过，深入搜索，回溯时用 v 的最古老追溯值更新 u
            tarjan_scc(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v]) {
            // v 访问过且还在栈里，说明遇到了一条指向祖先的“返祖边”，发现环！
            // ⚠️ 极其重要的细节：这里必须用 dfn[v] 更新，不能用 low[v]
            low[u] = min(low[u], dfn[v]);
        }
    }

    // 终极审判：u 的追溯值等于自身时间戳，u 就是这个强连通分量的根
    if (dfn[u] == low[u]) {
        scc_cnt++;
        int v;
        do {
            v = stk.top();
            stk.pop();
            in_stk[v] = false;
            
            scc_id[v] = scc_cnt; // 贴上超级节点的标签
            scc_size[scc_cnt]++; // 超级节点体积 +1
        } while (v != u); // 直到把根节点自己也弹出来
    }
}

int main() {
    int n = 5; // 假设有 5 个节点
    // 假设读入了边，建好了 graph ...
    
    // 1. 找所有 SCC
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) tarjan_scc(i); // 图可能不连通，必须遍历每个点
    }

    // 2. 缩点魔法：重新建一张 DAG
    for (int u = 1; u <= n; ++u) {
        for (int v : graph[u]) {
            // 如果 u 和 v 不属于同一个强连通分量，才给两个超级节点连边
            if (scc_id[u] != scc_id[v]) {
                dag_graph[scc_id[u]].push_back(scc_id[v]);
            }
        }
    }
    // 此时 dag_graph 是一张完美的有向无环图
    return 0;
}

20. 无向图：求割点 (Articulation Points) 和桥 (Bridges)

核心判定逻辑：

桥 (割边)：断开这条边，图会被一分为二。判定条件：low[v] > dfn[u]。即节点 v 拼了老命往下走，也找不到任何一条暗道能回到 u 或 u 之上的节点。那 u-v 就是唯一的生命线。
割点：删掉这个点及其所有连边，图会被一分为二。判定条件：low[v] >= dfn[u]。即 v 往下走，最多只能回到 u，无法跨越 u 到达更上面。那么 u 就是扼住 v 命运咽喉的枢纽。

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;

vector<int> graph[MAXN];
int dfn[MAXN], low[MAXN], timestamp = 0;

// 记录结果
bool is_cut[MAXN]; // is_cut[u] == true 表示节点 u 是割点
vector<pair<int, int>> bridges; // 记录所有的桥

// ⚠️ 无向图无需维护栈和 in_stk 数组！但必须传父节点 parent 防原路返回。
void tarjan_undirected(int u, int parent) {
    dfn[u] = low[u] = ++timestamp;
    int child_cnt = 0; // 记录在 DFS 树中的实际子树分支数量 (专门为根节点判割点准备)

    for (int v : graph[u]) {
        // 无向图中，防范原路返回，直接跳过父节点
        if (v == parent) continue; 

        if (!dfn[v]) {
            child_cnt++;
            tarjan_undirected(v, u);
            low[u] = min(low[u], low[v]);

            // 【判定 1：找桥】
            // 如果 v 的追溯值严格大于 u 的时间戳，说明没这条边 v 绝对回不去
            if (low[v] > dfn[u]) {
                bridges.push_back({u, v});
            }

            // 【判定 2：找割点】
            // 如果 u 不是 DFS 的起始根节点，且 v 最多只能回到 u，那么 u 就是割点
            if (parent != 0 && low[v] >= dfn[u]) {
                is_cut[u] = true;
            }
        } else {
            // v 已经被访问过 (且不是 u 的父节点)，说明遇到了一条返回祖先的边
            low[u] = min(low[u], dfn[v]); 
        }
    }

    // 【判定 2 补丁：根节点的特殊情况】
    // DFS 遍历的起点 (根节点) 没有父节点，上面的逻辑判断不了它。
    // 如果根节点在 DFS 树中有 >= 2 棵互不相通的子树，那根节点一没，这几棵子树必断联。
    if (parent == 0 && child_cnt >= 2) {
        is_cut[u] = true;
    }
}

int main() {
    int n = 5;
    // 构建图的边 ...
    // 无向图建边：graph[u].push_back(v); graph[v].push_back(u);

    // 执行 Tarjan，初始父节点传 0
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) tarjan_undirected(i, 0); 
    }

    cout << "图中的桥有：\n";
    for (auto edge : bridges) cout << edge.first << " - " << edge.second << "\n";
    
    return 0;
}

二分图匹配：

21. 染色法判定二分图 (Bipartite Graph Check)

应用场景

阵营划分问题：LeetCode 极其经典的“可能的最坏连通性/划分两组”问题。只要题目暗示“敌人的敌人是朋友”、“分两组且组内互不侵犯”，直接无脑上染色法。
奇环检测：图论中有一个极其重要的充要条件——一个图是二分图，当且仅当图中不存在奇数长度的环 (Odd Cycle)。染色法是检测奇环最快的方式。

复杂度分析

时间复杂度：$O(V + E)$。无论是用 DFS 还是 BFS，每个节点最多被染一次色，每条边最多被遍历一次。
空间复杂度：$O(V + E)$。邻接表存图，以及一个大小为 $V$ 的颜色数组。

核心代码模板：DFS 优雅染色

染色法的核心逻辑是连坐机制：“我如果是黑色，跟我相连的所有邻居都必须强制染成白色。”

在顺藤摸瓜的 DFS 过程中，如果碰到了一个已经被染过色的邻居，而且它的颜色竟然和我一模一样，这就说明图中出现了奇环，划分阵营的计划彻底破产，该图绝对不是二分图。

C++

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100005;

// 邻接表存图
vector<int> graph[MAXN];

// color 数组：
// 0 表示未染色，1 表示阵营 A (黑色)，2 表示阵营 B (白色)
int color[MAXN];

// DFS 染色函数
// u: 当前节点; c: 当前节点应该被染成的颜色 (1 或 2)
bool dfs(int u, int c) {
    color[u] = c; // 给当前节点染色

    // 遍历当前节点的所有邻居
    for (int v : graph[u]) {
        // 场景 A：邻居还没被染色，强制将它染成另一种颜色并继续 DFS
        if (color[v] == 0) {
            // 💡 神仙技巧：3 - c。如果当前 c 是 1，邻居就是 2；如果 c 是 2，邻居就是 1。
            if (!dfs(v, 3 - c)) {
                return false; // 如果子树染色失败，直接逐层上报失败
            }
        } 
        // 场景 B：邻居已经被染色了，且颜色跟我一模一样！发生阵营冲突！
        else if (color[v] == c) {
            return false;
        }
    }
    
    // 如果所有邻居都和平相处，返回成功
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 4; // 节点总数 1~n
    // 假设读入无向边：1-2, 2-3, 3-4, 4-1
    graph[1].push_back(2); graph[2].push_back(1);
    graph[2].push_back(3); graph[3].push_back(2);
    graph[3].push_back(4); graph[4].push_back(3);
    graph[4].push_back(1); graph[1].push_back(4);

    bool is_bipartite = true;

    // ⚠️ 极其关键的一步：图可能是不连通的（包含多个独立的小圈子）
    // 必须遍历所有的节点，确保每个连通块都被成功染色
    for (int i = 1; i <= n; ++i) {
        if (color[i] == 0) {
            // 如果这个连通块还没被探索过，从节点 i 开始，默认先染成颜色 1
            if (!dfs(i, 1)) {
                is_bipartite = false;
                break; // 一旦发现有一个部分不是二分图，全盘皆输，直接退出
            }
        }
    }

    if (is_bipartite) {
        cout << "鉴定为二分图：可以完美划分为两个互不侵犯的阵营。\n";
    } else {
        cout << "鉴定失败：图中存在奇数长度的环，发生阵营冲突！\n";
    }

    return 0;
}

匈牙利算法求二分图最大匹配。

22. 匈牙利算法 (二分图最大匹配)

应用场景

任务分配/相亲问题：$N$ 个工人和 $M$ 个任务，每个工人只能做特定的几个任务，一个工人只能接一个任务，一个任务只能分配给一个人。问最多能完成几个任务？
棋盘覆盖问题：在带有障碍物的网格棋盘上，放置最多数量的、互不攻击的骨牌或棋子。
图论定理基石：二分图中，最大匹配数 = 最小点覆盖数；最大独立集 = 总节点数 - 最大匹配数（Kőnig 定理）。掌握它，你能秒杀一整套极难的组合数学衍生题。

复杂度分析

时间复杂度：$O(V \cdot E)$。在二分图中，实际运行速度快得惊人，远远达不到理论上限。对于 $N \le 500$ 的数据规模，瞬间秒杀。
空间复杂度：$O(V + E)$。一个邻接表和两个一维数组。

核心代码模板：基于 DFS 找增广路

在代码实现中，我们不需要建立一张完整的无向图。我们只需要站在左半边阵营的视角，记录每个人对右半边阵营的“心动列表”即可。

C++

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 505; // 假设左半部和右半部最多各 500 个节点

// graph[u] 存的是【左侧节点 u】能够匹配的所有【右侧节点】
vector<int> graph[MAXN]; 

// match[v] = u：表示【右侧节点 v】目前已经被【左侧节点 u】成功牵手了
int match[MAXN];         

// vis[v] = true：表示在【当前这一轮】交涉中，【右侧节点 v】已经被访问过，防止死循环
bool vis[MAXN];          

// DFS 寻找增广路 (尝试给左侧节点 u 找对象)
bool dfs(int u) {
    // 遍历左侧节点 u 心仪的所有右侧节点 v
    for (int v : graph[u]) {
        if (!vis[v]) {
            vis[v] = true; // 标记 v 在这一轮已经被交涉过，别的人（或递归分支）不要再来碰它了
            
            // 核心“腾位置”逻辑：
            // 场景 A：如果右侧节点 v 目前还是单身 (match[v] == 0) -> 直接牵手成功！
            // 场景 B：如果 v 名花有主，我们就去找 v 的原配 (match[v]) 谈话，
            //         让他再执行一次 dfs，看他能不能腾出位置去找个别的备胎。
            if (match[v] == 0 || dfs(match[v])) {
                match[v] = u; // 成功牵手，或者原配成功腾出位置让给了 u
                return true;
            }
        }
    }
    return false; // 找了一圈，所有心仪对象死死抓着原配不放，u 注定单身
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n_left = 4;  // 左侧节点数量 (1 到 4)
    int n_right = 4; // 右侧节点数量 (1 到 4)

    // 假设读入关系 (左侧工人可以做的任务)：
    graph[1].push_back(1);
    graph[1].push_back(2);
    graph[2].push_back(2);
    graph[2].push_back(3);
    graph[3].push_back(1);
    graph[4].push_back(3);

    int max_match = 0; // 记录最大匹配对数

    // 遍历每一个左侧节点，尝试给他们发分配对象
    for (int i = 1; i <= n_left; ++i) {
        // ⚠️ 极其致命：每一次给新的人找对象，都必须把访问标记清空！
        // 因为对于新的人来说，所有的右侧节点都是可以尝试去“交涉”的。
        memset(vis, 0, sizeof(vis)); 
        
        // 如果 dfs(i) 返回 true，说明成功找到了一条增广路，匹配对数 +1
        if (dfs(i)) {
            max_match++;
        }
    }

    cout << "二分图的最大匹配数为: " << max_match << "\n";

    // 如果想看具体的匹配结果，只需遍历 match 数组
    for (int v = 1; v <= n_right; ++v) {
        if (match[v] != 0) {
            cout << "右侧节点 " << v << " 匹配了 左侧节点 " << match[v] << "\n";
        }
    }

    return 0;
}

四、树上问题 (Tree Algorithms)

很多公司的压轴题喜欢出树上的变种。

23. 树的直径 (Diameter of a Tree)

复杂度分析

时间复杂度：两种方法均为绝对的 $O(N)$ 。每条边最多被遍历两次。
空间复杂度：$O(N)$，用于邻接表存图和递归调用栈。

核心代码模板 1：两次 DFS/BFS 寻找法 (最符合直觉)

核心心法：敌进我退的极限拉扯

随便找一个节点（比如节点 1）作为起点，跑一次 DFS，找到全图离它最远的节点，记为 $A$ 。
从节点 $A$ 开始，再跑一次 DFS，找到离 $A$ 最远的节点，记为 $B$ 。
$A$ 到 $B$ 的路径，就是这棵树的直径！ （这是一个极具几何美感的图论定理，可以通过反证法严格证明）。

优点：能够非常方便地记录直径的具体路径（到底经过了哪些点）。

缺点：遇到图中存在负权边时，此方法会直接失效（因为负权边破坏了最远距离的贪心性质）。

C++

#include <iostream>
#include <vector>

using namespace std;

struct Edge {
    int to;
    long long weight;
};

const int MAXN = 100005;
vector<Edge> tree[MAXN];

int furthest_node = 0;      // 记录找到的最远节点
long long max_dist = -1;    // 记录最远距离

// 简单的 DFS：u 是当前节点，fa 是父节点（防止原路返回），dist 是当前累计距离
void dfs(int u, int fa, long long dist) {
    // 每次到达一个新节点，打擂台更新最大距离
    if (dist > max_dist) {
        max_dist = dist;
        furthest_node = u;
    }

    // 遍历所有的邻居
    for (const Edge& edge : tree[u]) {
        int v = edge.to;
        if (v != fa) { // 树上遍历防止死循环的终极技巧：不走回头路
            dfs(v, u, dist + edge.weight);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 6;
    // 构建一棵树 (假设读入无向边)
    tree[1].push_back({2, 3}); tree[2].push_back({1, 3});
    tree[1].push_back({3, 2}); tree[3].push_back({1, 2});
    tree[2].push_back({4, 4}); tree[4].push_back({2, 4});
    tree[2].push_back({5, 5}); tree[5].push_back({2, 5});
    tree[3].push_back({6, 6}); tree[6].push_back({3, 6});

    // 第一次 DFS：从随便一个点 (1 号点) 出发，寻找端点 A
    max_dist = -1;
    dfs(1, 0, 0); 
    int node_A = furthest_node;

    // 第二次 DFS：从端点 A 出发，寻找端点 B
    max_dist = -1;
    dfs(node_A, 0, 0); 
    int node_B = furthest_node;

    cout << "树的直径两端点为: " << node_A << " 和 " << node_B << "\n";
    cout << "树的直径长度为: " << max_dist << "\n"; // 输出应为 14 (5-2-1-3-6)

    return 0;
}

核心代码模板 2：树形 DP 法 (降维打击)

核心心法：把路径在“最高点”处折断

任意一条树上的路径，必然像一个“人”字形，有一个最高点（深度最浅的节点，也就是这条路径的最近公共祖先）。

那么，穿过节点 $u$ 的最长路径，等于：$u$ 的子树中，第一长的链 + 第二长的链。

我们在后序遍历（树形 DP）的过程中，让每个节点把自己的“第一长链”和“第二长链”加起来去挑战全局最大值，同时把“第一长链”返回给自己的父节点继续用。

优点：只要一次 DFS 即可出结果，代码极短！且完美免疫负权边。

缺点：如果要输出直径的具体路径，代码会变得极其恶心，不如两次 DFS 方便。

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int to;
    long long weight;
};

const int MAXN = 100005;
vector<Edge> tree[MAXN];

long long max_diameter = 0; // 全局变量，记录树的直径

// 树形 DP 函数：返回以 u 为根的子树中，从 u 出发往下的【单链最大长度】
long long dfs_dp(int u, int fa) {
    long long max1 = 0; // 第一长链 (必须初始化为 0，因为边权不为负时，最差可以不走)
    long long max2 = 0; // 第二长链

    for (const Edge& edge : tree[u]) {
        int v = edge.to;
        if (v != fa) {
            // 递归获取子节点的最长链，并加上当前边的权重
            long long cur_len = dfs_dp(v, u) + edge.weight;
            
            // 经典的找最大值与次大值逻辑
            if (cur_len > max1) {
                max2 = max1;       // 第一名退居第二
                max1 = cur_len;    // 新的记录霸占第一
            } else if (cur_len > max2) {
                max2 = cur_len;    // 仅仅比第二名大，替换第二名
            }
        }
    }

    // 在 u 这个节点“折返”的路径长度为 max1 + max2
    // 挑战全局直径记录
    max_diameter = max(max_diameter, max1 + max2);

    // 返回给父节点：要想把路径接上去，只能挑最长的那一条链 (max1)
    return max1;
}

int main() {
    // 建树过程省略 (同上)
    
    max_diameter = 0;
    // 只需要从任意节点 (如 1 号节点) 跑一次 DP 即可
    dfs_dp(1, 0);

    cout << "树的直径长度为 (Tree DP): " << max_diameter << "\n";

    return 0;
}

24. 树的重心 (Centroid of a Tree)

应用场景
- 点分治 (Point Divide and Conquer)：处理“树上距离为 $K$ 的点对数量”等大规模全树路径统计问题。每次在当前连通块中找到重心并将其切断，能保证递归深度严格限制在 $\log N$ 层。
- 网络节点部署/选址问题：把服务器建在重心上，到所有其他节点的距离之和是整棵树中最小的。
复杂度分析
- 时间复杂度：$O(N)$。仅仅需要一次极其轻量的后序遍历 DFS 即可算出。
- 空间复杂度：$O(N)$。用于邻接表存图和递归调用栈，以及一个记录子树大小的数组。
核心代码模板：一次 DFS 极限打擂
核心心法：上帝视角的三分天下
当我们要评估节点 $u$ 是不是重心时，假设我们一刀把 $u$ 砍掉，整棵树会被分成几个部分？
1. 向下的部分：$u$ 的每一个子树，各自成为一个独立的连通块。
向上的部分：$u$ 的父节点往上连着的那一大坨，也会成为一个独立的连通块。它的节点数等于 树的总节点数 $N$ 减去以 $u$ 为根的子树总节点数。

我们只需找出这几块中的最大值（即“最大残骸”），然后看哪个节点留下的最大残骸最小，它就是树的重心！

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
vector<int> tree[MAXN];

int n;                      // 树的节点总数 (极其重要，计算上方连通块时必须用到)
int sz[MAXN];               // sz[u] 表示以 u 为根的子树的节点总数
int centroid[2];            // 记录树的重心（一棵树最多可能有两个重心）
int centroid_cnt = 0;       // 当前找到的重心个数
int min_max_part = 1e9;     // 记录全局最小的“最大连通块大小”

// u: 当前节点, fa: 父节点
void get_centroid(int u, int fa) {
    sz[u] = 1; // 初始时，自己算一个节点
    int max_part = 0; // 记录如果删除 u 后，分裂出的各个残骸中最大的那个的大小

    // 遍历所有子节点
    for (int v : tree[u]) {
        if (v != fa) {
            get_centroid(v, u); // 递归计算子树
            sz[u] += sz[v];     // 累加子树的人口
            
            // 残骸 1：向下的各个子树
            max_part = max(max_part, sz[v]); 
        }
    }

    // 残骸 2：向上的父节点所在的那一大坨（极易漏掉）
    // 大小 = 整棵树的总人数 - 以 u 为根的子树总人数
    max_part = max(max_part, n - sz[u]);

    // 终极打擂台：试图更新全局最小的最大连通块
    if (max_part < min_max_part) {
        // 发现了一个更平衡的节点，之前的重心全部作废
        min_max_part = max_part;
        centroid[0] = u;
        centroid_cnt = 1;
    } else if (max_part == min_max_part) {
        // 如果恰好相等，说明找到了第二个重心
        centroid[1] = u;
        centroid_cnt = 2;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    n = 7; 
    // 构建一棵树 1-2, 1-3, 2-4, 2-5, 3-6, 3-7
    tree[1].push_back(2); tree[2].push_back(1);
    tree[1].push_back(3); tree[3].push_back(1);
    tree[2].push_back(4); tree[4].push_back(2);
    tree[2].push_back(5); tree[5].push_back(2);
    tree[3].push_back(6); tree[6].push_back(3);
    tree[3].push_back(7); tree[7].push_back(3);

    // 从任意节点 (如 1 号) 开始寻找
    min_max_part = 1e9;
    centroid_cnt = 0;
    get_centroid(1, 0);

    cout << "树的重心数量为: " << centroid_cnt << "\n";
    cout << "树的重心是: ";
    for (int i = 0; i < centroid_cnt; ++i) {
        cout << centroid[i] << " ";
    }
    cout << "\n";
    // 预期输出重心为 1，因为砍掉 1 之后，最大的残骸大小只有 3 (节点2及其子树)
    // 砍掉其他任何点，产生的最大残骸都会大于等于 4

    return 0;
}

25. 最近公共祖先 (LCA) - 倍增法 (Binary Lifting)

应用场景

求树上任意两点的距离：在一棵带有边权的树中，节点 $u$ 到节点 $v$ 的最短距离存在一个极其优美的公式：Dist(u, v) = DistToRoot(u) + DistToRoot(v) - 2 * DistToRoot(LCA(u, v))。
树上差分 (Tree Difference)：用于解决“频繁给树上 $u$ 到 $v$ 的路径上的所有节点/边加上某个值”的操作。
网络连通性分析：寻找两个子网通信必须经过的核心路由节点。

复杂度分析

时间复杂度：预处理 $O(N \log N)$ ；单次查询 $O(\log N)$ 。
空间复杂度：$O(N \log N)$。需要开一个 fa[N][20] 的二维数组来记录跳跃的祖先。

核心代码模板：DFS 预处理 + 二进制对齐跳跃

核心心法：不要一步一步走，要按 $2^k$ 步来“空间跳跃”

就像玩游戏一样，我们要找 $u$ 和 $v$ 的共同祖先。

对齐起跑线：如果 $u$ 比 $v$ 深，就让 $u$ 先往上跳，直到两人处于同一深度。
并排往上跳：两人同时往上跳。从大跨度（跳 $2^{19}$ 步）开始尝试，如果发现跳完之后两人相遇了（或者跳出界了），说明跳过头了，不跳；如果跳完发现两人还没相遇（祖先不同），说明还在 LCA 的下方，果断跳上去。
最后，两人一定会停在 LCA 的正下方。再往上走 1 步 (fa[u][0]) 就是终点！

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
const int LOG = 20; // 2^20 > 100000，足够覆盖 10 万个节点的深度

struct Edge {
    int to;
    long long weight;
};

vector<Edge> tree[MAXN];

// 倍增核心数组
int depth[MAXN];        // 记录每个节点的深度
int fa[MAXN][LOG];      // fa[u][i] 表示节点 u 向上跳 2^i 步到达的祖先节点
long long dist[MAXN];   // dist[u] 表示节点 u 到根节点 (1号点) 的总距离

// 1. 一次 DFS 搞定所有预处理 (极其优雅的写法)
void dfs(int u, int parent, long long d) {
    depth[u] = depth[parent] + 1; // 深度是父亲深度 + 1
    fa[u][0] = parent;            // u 向上跳 2^0 (1步) 就是直接父节点
    dist[u] = d;                  // 记录到根的距离

    // 💡 动态规划状态转移：u 向上跳 2^i 步，等于先向上跳 2^(i-1) 步，再向上跳 2^(i-1) 步
    for (int i = 1; i < LOG; ++i) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }

    // 遍历子节点
    for (const Edge& edge : tree[u]) {
        int v = edge.to;
        if (v != parent) {
            dfs(v, u, d + edge.weight);
        }
    }
}

// 2. O(log N) 极速查询 LCA
int get_lca(int u, int v) {
    // 强制让 u 成为深度更深的那一个节点 (方便操作)
    if (depth[u] < depth[v]) {
        swap(u, v);
    }

    // 步骤 A：先让 u 向上跳，跳到和 v 同一个深度
    for (int i = LOG - 1; i >= 0; --i) {
        // 如果 u 跳 2^i 步之后的深度，仍然 >= v 的深度，就果断跳上去
        if (depth[fa[u][i]] >= depth[v]) {
            u = fa[u][i];
        }
    }

    // 如果起跑线对齐后，发现两人重合了，说明 v 本来就是 u 的祖先！直接返回
    if (u == v) return u;

    // 步骤 B：u 和 v 步调一致，同时向上跳，逼近 LCA
    // ⚠️ 核心逻辑：从大跨度往下试，如果祖先不同，才跳；如果祖先相同，说明越界了，不跳。
    for (int i = LOG - 1; i >= 0; --i) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i];
            v = fa[v][i];
        }
    }

    // 循环结束后，u 和 v 一定停在 LCA 的直接子节点位置
    // 此时再往上走一步 (fa[u][0]) 就是我们要找的 LCA！
    return fa[u][0];
}

// 3. 极速计算任意两点距离
long long get_distance(int u, int v) {
    int lca_node = get_lca(u, v);
    // 魔法公式
    return dist[u] + dist[v] - 2 * dist[lca_node];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 5;
    // 构造一棵带权树
    tree[1].push_back({2, 10}); tree[2].push_back({1, 10});
    tree[1].push_back({3, 20}); tree[3].push_back({1, 20});
    tree[2].push_back({4, 5});  tree[4].push_back({2, 5});
    tree[2].push_back({5, 8});  tree[5].push_back({2, 8});

    // 初始化 0 号节点 (虚拟边界) 的深度为 0
    depth[0] = 0; 
    
    // 从根节点 1 出发预处理，父节点设为 0，初始距离设为 0
    dfs(1, 0, 0); 

    // 查询节点 4 和 5 的 LCA 和距离
    cout << "4 和 5 的 LCA 是: " << get_lca(4, 5) << "\n";            // 输出 2
    cout << "4 和 5 的最短距离是: " << get_distance(4, 5) << "\n";    // 输出 13 (5 + 8)

    // 查询节点 4 和 3 的 LCA 和距离
    cout << "4 和 3 的 LCA 是: " << get_lca(4, 3) << "\n";            // 输出 1
    cout << "4 和 3 的最短距离是: " << get_distance(4, 3) << "\n";    // 输出 35 (5 + 10 + 20)

    return 0;
}

26. 树链剖分 (Heavy-Light Decomposition)

应用场景

树上路径的批量修改/查询：频繁修改或查询任意两点间路径的节点和、最大值等。
树的子树批量修改/查询：以 $u$ 为根的整棵子树全部加 $K$ 。
LCA 的常数级优化：树剖求 LCA 的常数极小，很多时候比倍增法还要快。

核心心法：重儿子与重链

重儿子：一个节点的所有子节点中，包含子树节点数最多的那个儿子。
轻儿子：除了重儿子之外的其他所有儿子。
重链：由一连串重儿子首尾相接拼成的一条垂直的链。
最伟大的切分定理：如果我们优先遍历重儿子，那么同一条重链上的所有节点，在 DFS 序 (时间戳) 中一定是完全连续的！这就是我们可以用线段树来维护它的根本原因。

复杂度分析

时间复杂度：预处理（两次 DFS）$O(N)$；树上路径查询/修改，由于最多跨越 $\log N$ 条轻边，配合线段树的 $O(\log N)$ ，总单次操作复杂度为极其稳定的 $O(\log^2 N)$ 。
空间复杂度：$O(N)$，需要维护多个记录结构的辅助数组。

核心代码模板：两次 DFS 与路径狂飙

树剖的代码长，但逻辑极其工整。你需要提前准备好一个普通的线段树模板（此处省略线段树的具体实现，仅展示树剖与线段树的联动逻辑）。

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
vector<int> tree[MAXN];

// ==========================================
// 树剖核心数组
// ==========================================
int sz[MAXN];     // sz[u]: 以 u 为根的子树大小
int depth[MAXN];  // depth[u]: 节点 u 的深度
int fa[MAXN];     // fa[u]: 节点 u 的父节点
int son[MAXN];    // son[u]: 节点 u 的【重儿子】

int top[MAXN];    // top[u]: 节点 u 所在重链的【顶端节点】
int dfn[MAXN];    // dfn[u]: 节点 u 重新分配的连续时间戳 (线段树数组的新下标)
int rnk[MAXN];    // rnk[id]: dfn 时间戳对应的原节点编号 (用于线段树建树初始化)
int timer = 0;    // 时间戳计数器

// 假设这是一个封装好的线段树，只处理 [1, N] 的一维线性区间
struct SegmentTree {
    void update(int l, int r, long long val) { /* ... */ }
    long long query(int l, int r) { return 0; /* ... */ }
} seg;

// ==========================================
// DFS 1：获取每个节点的深度、父节点、子树大小和最重要的【重儿子】
// ==========================================
void dfs1(int u, int parent, int d) {
    sz[u] = 1;
    fa[u] = parent;
    depth[u] = d;
    son[u] = 0;

    int max_sub_size = -1; // 寻找重儿子的打擂台变量
    
    for (int v : tree[u]) {
        if (v == parent) continue;
        dfs1(v, u, d + 1);
        sz[u] += sz[v];
        
        // 谁的子树人多，谁就是重儿子
        if (sz[v] > max_sub_size) {
            max_sub_size = sz[v];
            son[u] = v;
        }
    }
}

// ==========================================
// DFS 2：剖分重链，打上连续的时间戳 (dfn)
// ==========================================
// u: 当前节点, t: u 所在重链的顶端节点
void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++timer;
    rnk[timer] = u; // 记录线段树第 timer 个位置装的是原树的谁

    // 必须【优先】递归重儿子！这样才能保证一条重链上的所有节点 dfn 是连续的！
    if (son[u]) {
        dfs2(son[u], t); // 重儿子的顶端节点和自己一样
    }

    // 处理完重儿子，再去处理轻儿子
    for (int v : tree[u]) {
        if (v != fa[u] && v != son[u]) {
            // 轻儿子就是一条全新重链的开端！它的顶端节点就是它自己！
            dfs2(v, v); 
        }
    }
}

// ==========================================
// 核心魔法：查询树上路径 u 到 v 的总和 (或最大值)
// ==========================================
long long query_path(int u, int v) {
    long long res = 0;
    
    // 如果 u 和 v 不在同一条重链上，就得“跳链”
    while (top[u] != top[v]) {
        // 永远让顶端更深的那个节点往上跳 (防错核心)
        if (depth[top[u]] < depth[top[v]]) {
            swap(u, v);
        }
        
        // u 从自己的重链顶端 (top[u]) 到自己 (u) 这一段是绝对连续的！
        // 直接砸给线段树查区间 [dfn[top[u]], dfn[u]]
        res += seg.query(dfn[top[u]], dfn[u]);
        
        // u 往上跳到顶端节点的上方 (跨越轻边，进入上一层重链)
        u = fa[top[u]];
    }

    // 循环结束时，u 和 v 已经来到了同一条重链上！
    // 此时它们之间的路径在 dfn 数组里也是连续的，最后查一次即可
    if (depth[u] > depth[v]) swap(u, v);
    res += seg.query(dfn[u], dfn[v]);
    
    return res;
}

// ==========================================
// 附加魔法：子树的批量操作
// ==========================================
// 以 u 为根的子树，在 dfn 数组中完美对应了 [dfn[u], dfn[u] + sz[u] - 1] 这段区间
void update_subtree(int u, long long val) {
    seg.update(dfn[u], dfn[u] + sz[u] - 1, val);
}

int main() {
    // 1. 建图...
    // 2. dfs1(1, 0, 1);
    // 3. dfs2(1, 1);
    // 4. 根据 rnk 数组初始化线段树...
    // 5. 快乐地 query_path / update_path
    return 0;
}

五、动态规划核心模型 (Dynamic Programming)

DP 没有死板的代码模板，但有固定的“状态设计模板”。

背包问题系列：01背包（一维空间优化）、完全背包、多重背包（二进制拆分优化）。

27. 01背包 (0/1 Knapsack)

应用场景

每个物品只能选一次，求在容量限制下的最大价值。
等和子集划分：能否选出若干数使总和为 target。
最小代价装满背包：求达到某容量时的最小物品数。
二维费用背包：同时限制体积与重量（多加一维即可）。

复杂度分析

朴素二维 DP：时间 O(N⋅M)O(N⋅M)，空间 O(N⋅M)O(N⋅M)（NN 为物品数，MM 为容量）。
空间优化（滚动数组/一维）：时间仍为 O(N⋅M)O(N⋅M)，空间降为 O(M)O(M)。

核心代码模板：一维空间优化版

核心心法：dp[j] 表示容量为 jj 时的最大价值。
遍历物品时，容量必须从大到小逆序循环，这样才能保证每个物品只被用一次（不会反复叠加）。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N = 4;                     // 物品个数
    int M = 10;                    // 背包容量
    vector<int> weight = {0, 2, 3, 4, 5}; // 体积，下标从1开始
    vector<int> value  = {0, 3, 4, 5, 6}; // 价值

    // dp[j] 表示容量为 j 时能获得的最大价值，初始化为 0
    vector<long long> dp(M + 1, 0);

    // 依次考虑每个物品
    for (int i = 1; i <= N; ++i) {
        // ⚠️ 极其关键：容量 j 必须从大到小逆序遍历
        for (int j = M; j >= weight[i]; --j) {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

    cout << "最大价值: " << dp[M] << "\n"; // 输出 11 (物品2+3)
    return 0;
}

易错点与变体

若要求恰好装满背包：初始化时 dp[0] = 0，其余 dp[j] 设为 -INF；答案需判断 dp[M] 是否合法。
若要求方案数：将 max 改为累加，初始化 dp[0] = 1，转移 dp[j] += dp[j - w]（同样需要逆序容量）。
二维费用：加一维变成 dp[j][k]，两维均需逆序。

28. 完全背包 (Unbounded Knapsack)

应用场景

每种物品可以无限制地选取。
硬币找零问题（求最少硬币数 / 求组合方案数）。
整数拆分、平方数分解等（相当于物品体积为 12,22,32,…12,22,32,…）。

复杂度分析

时间 O(N⋅M)O(N⋅M)，空间优化为 O(M)O(M)。

核心代码模板：一维正序版

与 01 背包的唯一区别：容量 jj 的遍历方向从大到小改为从小到大。
因为正序遍历允许同一物品在“刚刚更新过的状态”上再次被使用，正好满足无限次选取的语义。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N = 4, M = 10;
    vector<int> weight = {0, 2, 3, 4, 5};
    vector<int> value  = {0, 3, 4, 5, 6};

    vector<long long> dp(M + 1, 0);

    for (int i = 1; i <= N; ++i) {
        // 完全背包的唯一区别：容量 j 从小到大正序循环
        for (int j = weight[i]; j <= M; ++j) {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

    cout << "完全背包最大价值: " << dp[M] << "\n"; // 可以无限拿，价值更大
    return 0;
}

变体提示

若求恰好装满，同样将初始 dp 设为 -INF，dp[0] = 0。
若求最少硬币数（找零），将 max 改为 min，dp[j] = min(dp[j], dp[j - coin] + 1)，初始 dp[0] = 0，其余设为一个大数（如 1e9）。

29. 多重背包 (Multiple Knapsack) – 二进制拆分优化

应用场景

每种物品有固定数量 cnt[i]，介于 01 与完全之间。
资源分配、库存管理等问题。

复杂度分析

朴素做法（将每个物品拆成 cnt[i] 个单独的 01 背包物品）：时间 O(M⋅∑cnt[i])O(M⋅∑cnt[i])，数量大时直接爆炸。
二进制拆分优化：将 cnt[i] 拆成 1,2,4,…1,2,4,… 的若干个“打包物品”，剩余零头单独成一个物品。
总物品数从 ∑cnt[i]∑cnt[i] 降为 ∑log⁡cnt[i]∑logcnt[i]，时间 O(M⋅∑log⁡cnt[i])O(M⋅∑logcnt[i])。
进阶：单调队列优化可将时间压至 O(N⋅M)O(N⋅M)，但二进制拆分已足够应对绝大多数题目。

核心代码模板：二进制拆分 + 01 背包

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N = 3, M = 12;
    vector<int> weight = {0, 3, 4, 5};   // 体积
    vector<int> value  = {0, 2, 3, 4};   // 价值
    vector<int> cnt    = {0, 4, 3, 2};   // 每种物品的数量

    vector<long long> dp(M + 1, 0);

    for (int i = 1; i <= N; ++i) {
        int w = weight[i];
        int v = value[i];
        int c = cnt[i];

        // 二进制拆分：打包成 1, 2, 4, 8, ... 个
        for (int k = 1; k <= c; k <<= 1) {   // k 取 1, 2, 4, ...
            int pack_w = k * w;
            int pack_v = k * v;

            // 对打包后的物品做 01 背包（容量逆序）
            for (int j = M; j >= pack_w; --j) {
                dp[j] = max(dp[j], dp[j - pack_w] + pack_v);
            }
            c -= k;   // 减去已打包的数量
        }

        // 如果还有剩余的零头，再打一个包
        if (c > 0) {
            int pack_w = c * w;
            int pack_v = c * v;
            for (int j = M; j >= pack_w; --j) {
                dp[j] = max(dp[j], dp[j - pack_w] + pack_v);
            }
        }
    }

    cout << "多重背包最大价值: " << dp[M] << "\n";
    return 0;
}

线性 DP 经典：最长递增子序列 (LIS) 的 $O(N \log N)$ 二分+贪心模板、最长公共子序列 (LCS)。

30. 最长递增子序列 (LIS) – 二分贪心模板

应用场景

求一个序列中严格递增（或非严格递减）的最长子序列长度。
套娃信封问题、任务调度中的可延迟序列、数组最少划分成多少个递减子序列（Dilworth 定理对偶问题）。
将序列问题转化为“维护一个单调的候选尾数组”。

复杂度分析

朴素 DP：时间 O(N2)O(N2)，空间 O(N)O(N)。定义 dp[i] 表示以第 i 个元素结尾的 LIS 长度，转移需遍历 j < i。
二分贪心优化：时间 O(Nlog⁡N)O(NlogN)，空间 O(N)O(N)。用一个数组 tails 记录“当前所有长度下，最小的结尾值”。

核心心法：耐心排序 (Patience Sorting)

我们维护一个数组 tails，其中 tails[k] 表示：长度为 k+1 的所有递增子序列中，结尾元素的最小可能值。
遍历原数组时，对每个元素 x：

若 x 比 tails 中所有元素都大，可以接在任何子序列后面，形成一个更长的序列，tails 扩容一位。
否则，找到第一个 >= x 的位置 pos，把该位置的尾数替换成更小的 x，这样相当于“为未来的扩展降低门槛”，但不改变当前最长长度。

最终 tails 的长度就是 LIS 的长度。注意这个 tails 数组并不是真正的 LIS 序列，只是用来求长度。

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 求严格递增的最长子序列长度（LIS）
int lengthOfLIS(const vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;

    // tails[i]：长度为 i+1 的递增子序列的最小结尾值
    vector<int> tails;
    tails.reserve(n);

    for (int x : nums) {
        // 在 tails 中查找第一个 >= x 的位置
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) {
            // x 比所有尾巴都大，可以接在后面，序列长度 +1
            tails.push_back(x);
        } else {
            // 否则，替换掉那个位置的尾值，让该长度的子序列结尾更小
            *it = x;
        }
    }

    return tails.size(); // 最大长度
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "LIS 长度: " << lengthOfLIS(nums) << "\n"; // 输出 4（[2,3,7,101] 或 [2,5,7,101]）
    return 0;
}

变体说明

若要求非严格递增（不下降）子序列：将 lower_bound 改为 upper_bound，即找第一个 > x 的位置。
若要求输出具体的 LIS 序列：需要额外记录每个元素在 tails 中被替换/添加的位置，然后反向追踪，不能直接从 tails 得到。
若要求最长递减子序列：将原数组取反或逆向遍历，转化为递增问题。

31. 最长公共子序列 (LCS)

应用场景

求两个字符串/序列的最长公共子序列（不要求连续）。
版本对比、DNA 序列比对、文本相似度。
编辑距离的前置问题（LCS 是删除操作最少化的特殊情况）。

复杂度分析

经典 DP：时间 O(N⋅M)O(N⋅M)，空间 O(N⋅M)O(N⋅M)（N,MN,M 为两序列长度）。
空间优化：用滚动数组可将空间压缩到 O(min⁡(N,M))O(min(N,M))，但无法回溯输出具体序列。
特殊情况下：若字符集有限且其中一个串元素独特，可转化为 LIS（O(Nlog⁡N)O(NlogN)），但此处讲通用解法。

核心代码模板：二维 DP + 滚动数组优化

定义 dp[i][j] 表示字符串 A 的前 i 个字符与字符串 B 的前 j 个字符的最长公共子序列长度。

转移：

若 A[i] == B[j]，则 dp[i][j] = dp[i-1][j-1] + 1；
否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int longestCommonSubsequence(string A, string B) {
    int n = A.size(), m = B.size();
    // 使用滚动数组：dp[j] 表示上一行的状态，new_dp[j] 表示当前行
    vector<int> dp(m + 1, 0);

    for (int i = 1; i <= n; ++i) {
        vector<int> new_dp(m + 1, 0);
        for (int j = 1; j <= m; ++j) {
            if (A[i - 1] == B[j - 1]) {
                new_dp[j] = dp[j - 1] + 1;
            } else {
                new_dp[j] = max(dp[j], new_dp[j - 1]);
            }
        }
        dp = move(new_dp); // 滚动到下一行
    }
    return dp[m];
}

// 如果不需要空间极度压缩，直接用二维 vector 更直观：
int LCS_2D(string A, string B) {
    int n = A.size(), m = B.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (A[i - 1] == B[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[n][m];
}

int main() {
    string A = "abcde", B = "ace";
    cout << "LCS 长度: " << longestCommonSubsequence(A, B) << "\n"; // 输出 3 ("ace")
    return 0;
}

输出具体序列的方法

若需要回溯输出 LCS 字符串，需保留完整的二维 DP 表格（不用滚动数组），然后从 dp[n][m] 反向追溯：

若 A[i-1] == B[j-1]，该字符属于 LCS，记录后向左上移动；
否则，比较 dp[i-1][j] 与 dp[i][j-1]，往较大方向移动。

cpp

// 回溯输出 LCS 序列（需要二维 dp 表）
string getLCS(const string& A, const string& B, const vector<vector<int>>& dp) {
    int i = A.size(), j = B.size();
    string lcs;
    while (i > 0 && j > 0) {
        if (A[i - 1] == B[j - 1]) {
            lcs.push_back(A[i - 1]);
            i--; j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    reverse(lcs.begin(), lcs.end());
    return lcs;
}

易错提示

字符串下标与 DP 下标偏移：A[i-1] 对应 dp[i][j] 的当前字符。
滚动数组优化时，当前行 new_dp[j] 可能依赖上一行的 dp[j-1] 和当前行的 new_dp[j-1]，必须用两个数组，不能直接在原数组上修改（会覆盖未使用的旧值）。
更优的技巧：使用两个一维数组 pre 和 cur，或使用单数组配合临时变量保存左上角值（需小心更新顺序）。

32. 区间 DP – 石子合并问题

应用场景

最经典的区间动态规划模型：有若干堆石子排成一排（或环形），每次只能合并相邻的两堆，合并的代价是两堆石子总数，求将所有石子合并成一堆的最小总代价（或最大总代价）。
矩阵连乘问题、多边形三角剖分、最优二叉搜索树等，都是类似的“合并相邻元素”模型。
任何在区间上递归合并的 DP 都可套用此模板。

复杂度分析

时间复杂度：O(N3)O(N3)，三重循环（长度、起点、分割点）。对于 N≤300N≤300 的题目够用。
空间复杂度：O(N2)O(N2)，存储二维 DP 表。
可选优化：用四边形不等式将决策点单调性优化到 O(N2)O(N2)（竞赛中偶尔用到，但 O(N3)O(N3) 模板最稳定）。

核心心法：定义 dp[i][j] 为合并区间 [i, j] 的最小（或最大）代价

转移方程：
dp[i][j]=min⁡i≤k<j(dp[i][k]+dp[k+1][j]+cost(i,j))
其中 cost(i,j)cost(i,j) 通常是区间 [i,j][i,j] 的石子总数（因为最后两堆合并的代价是整段的和）。
前缀和快速求区间和：定义 sum[i] 为前 ii 堆的总数，则区间和 =sum[j]−sum[i−1]=sum[j]−sum[i−1]。
循环顺序必须按区间长度递增，因为大区间的状态依赖更短的子区间。
模板固定为：
1. 外层循环 len = 2 .. n
2. 内层枚举左端点 i
3. 最内层枚举分割点 k
初始化：dp[i][i] = 0，单个石子堆无需合并，代价为 0。

环形问题的通用处理方式

若石子堆是环形摆放（最后和第一个也算相邻），只需将数组复制一遍接在末尾（长度变为 2N），然后在所有长度为 N 的连续区间中取最优值。这样任意断开点都被自然枚举到了。

核心代码模板（含最小与最大代价，环形处理）

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;                       // 石子堆数
    cin >> n;
    vector<int> a(2 * n + 1);    // 下标从 1 开始，2n 长度支持环形
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i + n] = a[i];         // 复制一倍
    }

    // 前缀和
    vector<int> sum(2 * n + 1, 0);
    for (int i = 1; i <= 2 * n; ++i) {
        sum[i] = sum[i - 1] + a[i];
    }

    // dp_min[i][j] / dp_max[i][j] 表示合并区间 [i, j] 的最小/最大代价
    vector<vector<int>> dp_min(2 * n + 1, vector<int>(2 * n + 1, 0));
    vector<vector<int>> dp_max(2 * n + 1, vector<int>(2 * n + 1, 0));

    // ⚠️ 区间 DP 经典三重循环：长度 -> 左端点 -> 分割点
    for (int len = 2; len <= n; ++len) {                     // 枚举区间长度
        for (int i = 1; i + len - 1 <= 2 * n; ++i) {        // 左端点
            int j = i + len - 1;
            dp_min[i][j] = INT_MAX;
            dp_max[i][j] = INT_MIN;

            int cost = sum[j] - sum[i - 1];                 // 合并整段的代价（区间和）

            for (int k = i; k < j; ++k) {                   // 枚举分割点
                dp_min[i][j] = min(dp_min[i][j],
                                   dp_min[i][k] + dp_min[k + 1][j] + cost);
                dp_max[i][j] = max(dp_max[i][j],
                                   dp_max[i][k] + dp_max[k + 1][j] + cost);
            }
        }
    }

    // 在长度为 n 的所有环形区间中取最优答案
    int ans_min = INT_MAX;
    int ans_max = INT_MIN;
    for (int i = 1; i <= n; ++i) {
        ans_min = min(ans_min, dp_min[i][i + n - 1]);
        ans_max = max(ans_max, dp_max[i][i + n - 1]);
    }

    cout << "合并的最小总代价: " << ans_min << "\n";
    cout << "合并的最大总代价: " << ans_max << "\n";

    return 0;
}

易错点总结

必须先算前缀和，内层循环直接 sum[j] - sum[i-1] 获得区间和，不要临时累加（会多一层循环变成 O(N4)O(N4)）。
环形题目数组长度要开到 2n + 1，前缀和同样开到 2n + 1。
枚举分割点 k 时，范围是 [i, j-1]，不能等于 j，否则右半区间为空。
求最小值时，初始化用 INT_MAX；求最大值用 INT_MIN（或 0 也可以，因为石子数非负时代价不会为负）。
对于只有一堆石子的情况（len=1），代价为 0，循环从 len=2 开始是正确的。

33. 状态压缩 DP – 旅行商问题 (TSP) 模板

应用场景

经典的旅行商问题 (TSP, Traveling Salesman Problem)：给定 NN 个城市及其两两间的距离，求从起点出发，恰好访问每个城市一次，最后回到起点的最短总路程。若不需要回到起点，则称为哈密顿路径。
任务分配、生产排程、芯片布线与机器人路径规划等一切“全排列最小代价”问题均可转化为 TSP。
很多棋盘类 DP（如铺砖问题）也依赖状压表示某一行的覆盖状态。

复杂度分析

状态总数：2N⋅N，转移枚举下一个城市 O(N)，总体时间 O(N2⋅2N)。
空间复杂度：O(N⋅2N)O(N⋅2N)，存储 DP 表。
极限数据范围：在 1 秒内，N≤20 可以稳过，N≤22 可能需要常数优化（例如去掉无用状态、用循环代替递归）。

核心心法：二进制集合 + 当前停留城市

定义 dp[mask][i]：

mask 是一个 NN 位二进制数，第 jj 位为 11 表示城市 jj 已经被访问过（集合）。
i 表示当前正处在城市 ii（0≤i<N0≤i<N）。
该值表示从起点出发，已经走过的城市集合为 mask，且最后停在城市 i 的最短路径长度。

转移公式：
dp[mask][i]=j∈/maskmin(dp[mask∖{i}][j]+dist[j][i])
或正向转移更方便：
dp[mask∪{j}][j]=min(dp[mask∪{j}][j], dp[mask][i]+dist[i][j])，其中 j∉maskj∈/mask。

初始化：假设起点为 00，则 dp[1 << 0][0] = 0，其余为正无穷。
最终答案：若需要回到起点，答案是 mini(dp[(1≪N)−1][i]+dist[i][0])；若只需到达所有点，答案是 minidp[(1≪N)−1][i]。

核心代码模板：经典 TSP（含回到起点）

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

const int INF = 1e9; // 1e9 在 N<=20 时足够大且不会溢出

int tsp(const vector<vector<int>>& dist) {
    int N = dist.size();
    int max_mask = 1 << N;

    // dp[mask][i]: 已经访问过 mask 中的城市，当前在城市 i 的最短路径
    vector<vector<int>> dp(max_mask, vector<int>(N, INF));

    // 假设从城市 0 出发
    dp[1 << 0][0] = 0;

    // 枚举所有状态
    for (int mask = 0; mask < max_mask; ++mask) {
        // ⚠️ 起点 0 必须已经在 mask 中，否则跳过（避免无意义状态）
        if (!(mask & 1)) continue;

        for (int i = 0; i < N; ++i) {
            // 如果当前城市 i 不在 mask 中，状态无效
            if (!(mask & (1 << i))) continue;
            if (dp[mask][i] == INF) continue;

            // 尝试前往下一个未访问的城市 j
            for (int j = 0; j < N; ++j) {
                // j 已经在集合中，跳过
                if (mask & (1 << j)) continue;

                int next_mask = mask | (1 << j);
                dp[next_mask][j] = min(dp[next_mask][j],
                                       dp[mask][i] + dist[i][j]);
            }
        }
    }

    // 最终答案：访问了所有城市，最后从某个城市 i 回到起点 0
    int ans = INF;
    int full_mask = (1 << N) - 1;
    for (int i = 0; i < N; ++i) {
        if (dp[full_mask][i] == INF) continue;
        ans = min(ans, dp[full_mask][i] + dist[i][0]);
    }

    return ans;
}

int main() {
    // 示例：4 个城市，邻接矩阵给出距离
    vector<vector<int>> dist = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };

    cout << "TSP 最短回路长度: " << tsp(dist) << "\n"; // 输出 80
    return 0;
}

易错点与优化技巧

起点约束：循环中加 if (!(mask & 1)) continue; 可以剪掉大量不可能包含起点的无效状态，常数优化明显。
距离矩阵不完整：若某些城市间不可直达，可将距离设为 INF，转移时自然跳过。
回到起点：最终答案一定要加上最后一段返回起点的距离，这是 TSP 与哈密顿路径的差别。
对称性剪枝：如果图是无向的（距离对称），可以利用对称性减少状态或提前终止，但通常不必要。
循环顺序：上面使用正向转移（从当前状态推出下一状态），也可以逆序枚举（从 mask 中去掉 i 找前驱），本质上相同，正向枚举更符合直觉。
空间优化：可用 vector<int> dp[2] 滚动数组？不现实，因为 mask 的前后依赖复杂。更常见的优化是使用一维数组，dp[mask][i] 可以直接用 dp[mask] 数组的 i 位信息？不行。只能二维。如果 N=20，2^20 * 20 约 2000 万 int，空间约 80 MB，尚可接受；若 N=22 内存会翻 4 倍，需要谨慎。

扩展：不回到起点的哈密顿路径

只需将最终答案计算改为：

cpp

int ans = INF;
for (int i = 0; i < N; ++i) {
    ans = min(ans, dp[full_mask][i]);
}

扩展：多起点或随机起点

如果需要求“从任意点出发”的最佳 TSP，可以将初始化改为 for (int i=0;i<N;i++) dp[1<<i][i] = 0;，然后在答案中不再加回起点的距离。但注意复杂度会升高，一般题目会固定起点。

状压 DP 的其他经典形态

子集枚举式 DP：dp[mask] 只表示集合的最优值，转移枚举子集 sub = (mask-1) & mask 等（常见于任务分配或匹配问题）。
轮廓线 DP：在棋盘覆盖问题中，使用“轮廓线”的二进制状态表示当前处理到哪一行的哪些格子已被覆盖，结合滚动数组，复杂度通常 O(N⋅M⋅2M)O(N⋅M⋅2M)。

34. 数位 DP (Digit DP) – 记忆化搜索模板

应用场景

统计某个区间 [L,R][L,R] 内满足特定数字规律的数的个数，例如：
- 不含数字 4 的数；
- 不含连续 "13" 或 "62" 的数；
- 各位数字之和等于某个值的数；
- 能被某数整除，且每位数位存在某种限制；
- 相邻数字差至少为 2 的“Windy 数”等。
所有“统计区间内符合某些数字限制的个数”问题，几乎都可以套用数位 DP 的记忆化搜索框架。

复杂度分析

状态数约为位数×状态空间位数×状态空间，例如统计数位和等于 target 时状态为 pos×sumpos×sum。
每次转移最多枚举当前位数字 0∼90∼9，总时间 O(10×位数×状态空间)O(10×位数×状态空间)，对于最大 19 位（long long 范围）完全无压力。
空间复杂度同状态数，通常用数组 dp[pos][state] 存储记忆化结果。

核心心法：DFS + 记忆化

将数字按位拆开（十进制），从最高位向下深度优先搜索。
DFS 的参数通常包含：

pos：当前处理到哪一位（从高位向低位）。
state：当前累积的“状态”（例如当前数位和、前一位数字、是否出现了某个模式等）。
limit：是否被原数字的当前位“紧逼”。若为 true，当前位只能填 0∼digit[pos]0∼digit[pos]；否则可取 0∼90∼9。
lead：是否还在前导零阶段。前导零不影响真正的数字属性（如数位和、是否出现某数字等），通常需要特殊处理。

记忆化技巧：
只记录那些 不受限制 (limit = false) 且已经脱离了前导零 (lead = false) 的状态，因为这些状态是通用且可复用的。如果在受限或前导零情况下强行记忆，会因依赖具体数字而导致结果错误。

通用解题步骤：

写一个 dfs(pos, state, limit, lead) 函数。
当 pos == 0（处理完所有位）时，返回当前状态是否满足条件（通常返回 0 或 1）。
如果 !limit && !lead && dp[pos][state] != -1，直接返回已计算的值。
根据 limit 和 digit[pos] 确定当前位能填的数字上界 up。
枚举当前位数字 i，更新 state、limit 和 lead 标志，累加结果。
若可记忆，将结果存入 dp[pos][state]。
主函数中对 [0,R][0,R] 和 [0,L−1][0,L−1] 分别求值，相减得答案。

核心代码模板：统计区间 [L,R][L,R] 内各位数字之和等于 target 的个数

cpp

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

// dp[pos][sum] 记录非限制、非前导零时，从 pos 位开始，当前数位和为 sum 的方案数
int dp[20][200]; // 19 位足够 long long，sum 上限 9*18=162

// digit 数组从高位到低位存储（索引 1 ~ len）
vector<int> digit;

// pos: 当前位, sum: 当前累积的数位和, target: 目标和
// limit: 是否被原数压紧, lead: 是否仍在前导零
int dfs(int pos, int sum, int target, bool limit, bool lead) {
    // 所有位处理完毕，若当前和等于目标则计 1，否则 0
    if (pos == 0) return sum == target;

    // 状态可复用（无限制、已出前导零）时，直接返回记忆化值
    if (!limit && !lead && dp[pos][sum] != -1) return dp[pos][sum];

    int up = limit ? digit[pos] : 9;
    int ans = 0;

    for (int i = 0; i <= up; ++i) {
        // 若仍在前导零，且当前位填 0，则继续处于前导零状态，且不计入数位和
        int next_sum = sum;
        if (!(lead && i == 0)) next_sum += i; // 脱离前导零后才累加数字

        ans += dfs(pos - 1,
                   next_sum,
                   target,
                   limit && (i == up),     // 之前受限且当前填到上界，下一位继续受限
                   lead && (i == 0));      // 之前是前导零且当前还是 0，则继续前导零
    }

    // 仅在通用状态下才记忆化
    if (!limit && !lead) dp[pos][sum] = ans;

    return ans;
}

// 求 [0, x] 中数位和等于 target 的数的个数
int solve(int x, int target) {
    if (x < 0) return 0;
    digit.clear();
    digit.push_back(0); // 占位，让下标从 1 开始
    while (x > 0) {
        digit.push_back(x % 10);
        x /= 10;
    }
    // digit[1..len] 是从低位到高位，但 dfs 时 pos 从 len 往下走，正好是高位到低位
    memset(dp, -1, sizeof(dp));
    return dfs(digit.size() - 1, 0, target, true, true);
}

int main() {
    int L = 100, R = 999, target = 15;
    int ans = solve(R, target) - solve(L - 1, target);
    cout << "区间 [" << L << ", " << R << "] 内数位和等于 "
         << target << " 的数有 " << ans << " 个\n";
    return 0;
}

易错点与变体

前导零处理：只有当 lead == true 且当前填 0 时，才继续维持前导零，且该 0 不应当参与状态的更新（如数位和、出现数字统计等）。如果前导零问题处理不当，会导致统计结果偏多（例如将 "005" 视为三位数，实际只是 5）。
记忆化范围：必须严格在 !limit && !lead 时记录，因为受限制的状态会随具体数字变化，无法复用；前导零的状态同样无法复用（脱离前导零的时刻依赖原数字的长度）。
多次查询复用：如果只是 target 变化，可以不清空 dp，直接在 solve 外 memset(dp, -1, sizeof(dp)) 一次即可。如果状态除了 sum 还有别的维度（如前一位数字），且这些维度的限制随查询改变，则每次查询前需清空 dp。
limit 标记：下一位是否受限，取决于当前位是否受限，且当前位是否填到了上界 up，即 limit && (i == up)。
其他常见变体：
- 要求数字模 MOD 等于某值：state 增加一维记录当前余数。
- 不允许出现某个数字 d：若 !lead 且 i == d 则直接跳过。
- 不允许出现连续相同数字或特定模式：state 记录上一位数字或更复杂的自动机状态。
- 求平方和、数字乘积等：需要在 state 中维护相应的累积信息。

数位 DP 的核心在于状态设计与记忆化剪枝，这套 DFS 模板几乎可以一劳永逸地解决所有区间数字统计问题。

六、数学与数论 (Mathematics & Number Theory)

不需要证明，但比赛时必须要会默写的数学公式转换代码。

快速幂与矩阵快速幂：$O(\log N)$ 求 $A^B \pmod M$ ；矩阵快速幂用于 $O(\log N)$ 求解线性递推数列（如斐波那契数列第 $10^9$ 项）。

35. 快速幂 (Binary Exponentiation)

应用场景

求 ab mod pabmodp（bb 可能极大，如 109109 甚至 10181018）。
模意义下的乘法逆元：a−1≡ap−2(modp)a−1≡ap−2(modp)（费马小定理，pp 为质数）。
所有涉及大指数幂的场景（组合数逆元、哈希、多项式等）。

复杂度分析

时间复杂度：O(log⁡b)O(logb)，每次循环指数折半。
空间复杂度：O(1)O(1) 迭代版，O(log⁡b)O(logb) 递归版（调用栈）。

核心模板：迭代版（推荐）与递归版

核心原理：将指数 bb 按二进制拆解，ab=a2k1⋅a2k2⋯ab=a2k1⋅a2k2⋯，通过不断平方底数并检查当前二进制位是否为 1 来累积结果。

cpp

#include <iostream>
using namespace std;

// 迭代快速幂：求 (a^b) % mod
long long qpow(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod; // 先取模防止溢出
    while (b > 0) {
        // 如果当前二进制位为 1，累乘上对应的底数幂
        if (b & 1) res = (res * a) % mod;
        // 底数平方，指数右移
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

// 递归版（简洁，但栈开销稍大）
long long qpow_rec(long long a, long long b, long long mod) {
    if (b == 0) return 1;
    long long half = qpow_rec(a, b / 2, mod);
    half = (half * half) % mod;
    if (b % 2) half = (half * (a % mod)) % mod;
    return half;
}

注意事项

mod 通常为质数（如 109+7109+7），但函数对任意模数有效。
指数 bb 可能是 long long，循环时注意 b 的类型。

36. 矩阵快速幂 (Matrix Exponentiation)

应用场景

线性递推数列第 n 项：如斐波那契数列 Fn=Fn−1+Fn−2，计算Fnmodp（n 可达 10181018）。
图上路径计数：求两点间长度恰好为 k 的路径数。
任何可以写成“向量 × 矩阵的幂”形式的 DP 优化。

复杂度分析

矩阵乘法 O(m3)（mm 为矩阵大小）。
矩阵快速幂整体复杂度：O(m3logn)，通常 m≤100，nn 极大。

核心模板：封装矩阵结构体 + 快速幂

cpp

#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1e9 + 7;

struct Matrix {
    int n; // 矩阵大小 n x n
    vector<vector<long long>> mat;

    // 初始化为 n x n 的零矩阵
    Matrix(int n) : n(n), mat(n, vector<long long>(n, 0)) {}

    // 单位矩阵
    static Matrix identity(int n) {
        Matrix I(n);
        for (int i = 0; i < n; ++i) I.mat[i][i] = 1;
        return I;
    }

    // 矩阵乘法
    Matrix operator*(const Matrix& other) const {
        Matrix res(n);
        for (int i = 0; i < n; ++i) {
            for (int k = 0; k < n; ++k) {
                if (mat[i][k] == 0) continue; // 常数优化
                for (int j = 0; j < n; ++j) {
                    res.mat[i][j] = (res.mat[i][j] + mat[i][k] * other.mat[k][j]) % MOD;
                }
            }
        }
        return res;
    }

    // 矩阵快速幂
    Matrix pow(long long k) const {
        Matrix res = identity(n);
        Matrix base = *this;
        while (k > 0) {
            if (k & 1) res = res * base;
            base = base * base;
            k >>= 1;
        }
        return res;
    }
};

实战示例：求斐波那契数列第 n 项

(FnFn−1)=(1110)(Fn−1Fn−2)

所以：

(FnFn−1)=(1110)n−1(F1F0)

cpp

long long fib(long long n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    Matrix T(2);
    T.mat = {{1, 1}, {1, 0}};
    Matrix T_pow = T.pow(n - 1);

    // 初始向量 [F1, F0]
    long long F1 = 1, F0 = 0;
    // 结果 Fn = T_pow[0][0]*F1 + T_pow[0][1]*F0
    long long Fn = (T_pow.mat[0][0] * F1 + T_pow.mat[0][1] * F0) % MOD;
    return Fn;
}

37. 素数筛法 – 埃氏筛与欧拉线性筛

应用场景

在 O(N)O(N) 或 O(Nlog⁡log⁡N)O(NloglogN) 时间内生成 [1,N][1,N] 内的所有素数，是数论问题的基础预处理。
质因数分解加速：配合线性筛记录每个数的最小质因子，可将单次分解复杂度降至 O(log⁡N)O(logN)。
批量求解积性函数：如欧拉函数 φ(n)φ(n)、莫比乌斯函数 μ(n)μ(n)、约数个数 d(n)d(n) 等，均可在筛素数时一并计算。
判断大范围内数字的素数性质、区间筛、素数密度统计等。

复杂度分析

埃氏筛 (Sieve of Eratosthenes)
时间：O(Nlog⁡log⁡N)O(NloglogN)，空间：O(N)O(N)（一个布尔数组）。
实现极简单，常数小，在 N≤107N≤107 时非常高效，是绝大多数题目的首选。
欧拉线性筛 (Linear Sieve)
时间：O(N)O(N)，空间：O(N)O(N)（需要素数列表 primes 和最小质因子数组 min_factor）。
严格线性，并能顺便维护积性函数，是所有需要“最小质因子”或批量求积性函数值时的标配。

核心代码模板 1：埃氏筛（最简版）

cpp

#include <iostream>
#include <vector>
using namespace std;

// 返回 [1, n] 内的所有素数（n >= 2）
vector<int> sieve_eratosthenes(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false; // 0 和 1 不是素数
    for (int i = 2; i * i <= n; ++i) {
        if (is_prime[i]) {
            // 从 i*i 开始标记，因为 2*i, 3*i, ..., (i-1)*i 已经被更小的素数筛过
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) primes.push_back(i);
    }
    return primes;
}

优化细节：内层循环从 i * i 开始避免了重复标记，且复杂度自然达到 O(Nlog⁡log⁡N)O(NloglogN)。

核心代码模板 2：欧拉线性筛（标准版）

核心思想：每个合数只被它的最小质因子筛掉一次，从而实现绝对线性。
遍历 i = 2..n，对于每个素数 p <= i 且 p * i <= n，标记 p * i 为合数，且当 i % p == 0 时停止，因为此时 p 是 i 的最小质因子，若继续枚举更大的素数 p'，则 p' * i 的最小质因子将是 p 而非 p'，会破坏唯一性。

cpp

#include <iostream>
#include <vector>
using namespace std;

vector<int> sieve_linear(int n) {
    vector<bool> is_composite(n + 1, false); // 合数标记
    vector<int> primes;
    primes.reserve(n / log(n)); // 粗略预留空间

    for (int i = 2; i <= n; ++i) {
        if (!is_composite[i]) {
            primes.push_back(i); // i 是素数
        }
        // 用 i 和已存的素数去筛合数
        for (int p : primes) {
            if (1LL * p * i > n) break;       // 越界则停止
            is_composite[p * i] = true;
            if (i % p == 0) break;            // 关键：p 是 i 的最小质因子时停止
        }
    }
    return primes;
}

同时获取最小质因子的扩展版（极其常用）：

cpp

vector<int> min_factor;
vector<int> primes;

void linear_sieve_with_min_factor(int n) {
    min_factor.assign(n + 1, 0);
    primes.clear();
    for (int i = 2; i <= n; ++i) {
        if (min_factor[i] == 0) {
            min_factor[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > min_factor[i] || 1LL * p * i > n) break;
            min_factor[p * i] = p; // p 是 p*i 的最小质因子
        }
    }
}

基于 min_factor 可以在 O(log⁡N)O(logN) 内分解质因数，也可以快速计算各类积性函数。

38. 扩展欧几里得算法 (Extended Euclidean Algorithm)

应用场景

求解二元一次不定方程 ax+by=gcd⁡(a,b)ax+by=gcd(a,b) 的一组整数解。
求解线性同余方程 ax≡b(modm)ax≡b(modm)（求 xx 或判断无解）。
求模意义下的乘法逆元：当 gcd⁡(a,m)=1gcd(a,m)=1 时，a−1 mod ma−1modm 即方程 ax≡1(modm)ax≡1(modm) 的解。
中国剩余定理 (CRT) 的合并步骤、解模线性方程组的基础工具。
几乎所有需要“模除法”且模数不是质数时的核心算法。

复杂度分析

时间复杂度：O(log⁡max⁡(a,b))O(logmax(a,b))，与辗转相除法 (欧几里得算法) 完全同阶，常数极小。
空间复杂度：递归版本 O(log⁡max⁡(a,b))O(logmax(a,b))（调用栈深度），迭代版本可做到 O(1)O(1)，但递归版足以应对所有常见数据范围。

核心代码模板：递归版 exGCD

设 exgcd(a, b, x, y) 返回 d=gcd⁡(a,b)d=gcd(a,b)，并通过引用传递得到一组解 (x,y)(x,y) 满足 ax+by=dax+by=d。
递归式基于：
ax+by=gcd⁡(a,b)=gcd⁡(b,a mod b)=bx′+(a mod b)y′ax+by=gcd(a,b)=gcd(b,amodb)=bx′+(amodb)y′，
其中 a mod b=a−⌊a/b⌋⋅bamodb=a−⌊a/b⌋⋅b。
整理后得到 x=y′x=y′，y=x′−⌊a/b⌋⋅y′y=x′−⌊a/b⌋⋅y′。

cpp

#include <iostream>
#include <algorithm>
using namespace std;

// 扩展欧几里得：返回 gcd(a,b)，并求出 ax + by = gcd(a,b) 的一组解 (x, y)
long long exgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = exgcd(b, a % b, y, x); // 注意参数位置：交换 x 和 y
    // 此时 x 是原来的 y'，y 是原来的 x'（递归调用后已被更新）
    y -= (a / b) * x;  // y = x' - (a/b) * y'
    return d;
}

使用例：求解 ax+by=cax+by=c 的整数解

调用 exgcd(a, b, x0, y0) 得到 d=gcd⁡(a,b)d=gcd(a,b) 及 ax0+by0=dax0+by0=d。
若 c mod d≠0cmodd=0，则原方程无整数解。
否则，一组特解为 x=x0⋅(c/d)x=x0⋅(c/d)，y=y0⋅(c/d)y=y0⋅(c/d)。
通解形式：x=x+bd⋅tx=x+db⋅t，y=y−ad⋅ty=y−da⋅t（t∈Zt∈Z）。

求解线性同余方程 ax≡b(modm)ax≡b(modm)

该方程等价于 ax+my=bax+my=b，有解当且仅当 gcd⁡(a,m)∣bgcd(a,m)∣b。
算法步骤：

令 d=gcd⁡(a,m)d=gcd(a,m)，若 b mod d≠0bmodd=0，无解。
调用 exgcd(a, m, x0, y0) 得到 ax0+my0=dax0+my0=d 的特解。
原方程特解：x=x0⋅(b/d) mod mx=x0⋅(b/d)modm。
通解：在模 m/dm/d 意义下共有 dd 个不同的解，即 x≡x+k⋅(m/d)(modm)x≡x+k⋅(m/d)(modm)，k=0,1,…,d−1k=0,1,…,d−1。

cpp

// 求解 ax ≡ b (mod m)，返回是否有解，并将一个特解存入 x
bool solve_congruence(long long a, long long b, long long m, long long &x) {
    long long d, y;
    d = exgcd(a, m, x, y);
    if (b % d != 0) return false;    // 无解
    x = x * (b / d) % m;
    // 调整为最小非负解（模 m/d）
    long long mod = m / d;
    x = (x % mod + mod) % mod;
    return true;
}

求乘法逆元：a−1 mod ma−1modm（gcd⁡(a,m)=1gcd(a,m)=1）

即求 ax≡1(modm)ax≡1(modm) 的解。调用 exgcd(a, m, x, y) 后，得到的 xx 可能为负，需取模调整。

cpp

// 返回 a 在模 m 下的逆元，若不存在则返回 -1（仅当 gcd(a,m)!=1 时不存在）
long long mod_inverse(long long a, long long m) {
    long long x, y;
    long long d = exgcd(a, m, x, y);
    if (d != 1) return -1;           // 逆元不存在
    return (x % m + m) % m;          // 调整为正
}

示例
求 3x≡2(mod7)3x≡2(mod7) 的解：

cpp

long long x;
if (solve_congruence(3, 2, 7, x))
    cout << "x = " << x << "\n";     // 输出 x = 3 (因为 3*3=9 ≡ 2 mod 7)

39. 乘法逆元与模除法

应用场景

在模运算中，除法不能直接进行：(A/B)(modM) 不能简单地写成 AmodM 除以 BmodM。必须将“除以 B”转化为“乘以 B 的逆元”。
分数取模：计算期望值、概率、几何级数等含有除法的表达式时，答案通常要求对质数取模（如 109+7109+7）。
组合数取模：C(n,k)=k!(n−k)!n!modp，需要预处理阶乘和阶乘的逆元，实现 O(1) 查询。
除法操作的批量加速：当大量除法均对同一模数时，预处理好逆元可以做到 O(1) 查询。

两种核心方法对比

方法	适用条件	时间复杂度	原理
费马小定理 + 快速幂	模数 MM 为质数	O(logM)	B−1≡BM−2(modM)
扩展欧几里得 (exGCD)	gcd⁡(B,M)=1gcd(B,M)=1（即 MM 不必为质数）	O(logM)	解 Bx+My=1 得 x≡B−1(modM)

在竞赛中，模数通常是质数（109+7109+7 或 998244353998244353），因此费马小定理版本使用频率极高，代码也最短。

复杂度分析

单次求逆元：O(logM)。
批量预处理 1∼N 所有数的逆元：O(N)（利用递推公式），通常配合阶乘表一起使用。

核心代码模板 1：费马小定理求逆元（模数为质数）

cpp

#include <iostream>
using namespace std;

const long long MOD = 1e9 + 7; // 必须是质数

// 快速幂（复用之前的模板）
long long qpow(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

// 求 B 在模 MOD 下的逆元（MOD 为质数）
long long mod_inverse(long long B) {
    return qpow(B, MOD - 2, MOD);  // B^{MOD-2} mod MOD
}

// 计算 (A / B) % MOD
long long mod_div(long long A, long long B) {
    return (A % MOD) * mod_inverse(B) % MOD;
}

示例：计算 100/3 mod (109+7)100/3mod(109+7)：

cpp

cout << mod_div(100, 3) << "\n";  
// 3 * 333333336 ≡ 1 (mod 1e9+7)，所以 100 * 333333336 mod 1e9+7

核心代码模板 2：批量求逆元 + 组合数预处理

如果需要频繁计算组合数 C(n,k)modp（n,k≤106），可预先计算阶乘和逆阶乘。

cpp

#include <vector>

// 全局变量或结构体封装
vector<long long> fact, inv_fact;
long long MOD = 1e9 + 7;

// 预处理阶乘和阶乘逆元
void precompute(int n) {
    fact.resize(n + 1);
    inv_fact.resize(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    // 先求最大阶乘的逆元，然后倒推
    inv_fact[n] = mod_inverse(fact[n]);
    for (int i = n - 1; i >= 0; --i) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;  // 关键递推
    }
}

// O(1) 查询组合数
long long nCr(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

递推逆元公式（可选）：若不需要阶乘，只需 1∼N 每个数的逆元，可使用：

cpp

vector<long long> inv(n + 1);
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
    inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
}

扩展：模数为非质数时的处理

若 MM 不是质数，但 gcd⁡(B,M)=1gcd(B,M)=1，可使用扩展欧几里得求逆元：

cpp

long long mod_inverse_exgcd(long long B, long long M) {
    long long x, y;
    exgcd(B, M, x, y);
    return (x % M + M) % M;
}

若 gcd⁡(B,M)≠1gcd(B,M)=1，除法在模 MM 下没有定义，需要将分母中的因子与分子约分后再计算，或者使用其他技巧（如组合数对任意模数取模的 Lucas 定理等）。

40. 组合数取模 – 阶乘与逆元预处理

应用场景

在模质数意义下快速计算二项式系数 C(n,k)=k!(n−k)!n!modp。
各类计数问题：路径条数、放球方案、多项式系数、概率与期望中的组合项。
配合动态规划、容斥原理、二项式反演等，频繁查询组合数。

复杂度分析

预处理阶乘与阶乘逆元：时间 O(N)，空间 O(N)（N 为需要预处理的 n 的最大值）。
单次查询组合数：O(1)。

适用范围

模数 p 必须为质数，通常取 109+7 或 998244353998244353，确保逆元存在。
预处理的 n 上限取决于内存，一般 N≤106 毫无压力，N≤107 也可承受（约 80 MB）。

核心代码模板

cpp

#include <iostream>
#include <vector>
using namespace std;

const long long MOD = 1e9 + 7; // 必须为质数

vector<long long> fact, inv_fact;

// 快速幂（求逆元用）
long long qpow(long long a, long long b) {
    long long res = 1;
    a %= MOD;
    while (b) {
        if (b & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

// 预处理阶乘和阶乘逆元，需保证 n < MOD
void precompute(int n) {
    fact.resize(n + 1);
    inv_fact.resize(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    // 利用费马小定理求最大阶乘的逆元
    inv_fact[n] = qpow(fact[n], MOD - 2);
    // 倒推出所有阶乘逆元
    for (int i = n - 1; i >= 0; --i) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
    }
}

// O(1) 查询组合数 C(n, k)
long long nCr(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

// 如果需要排列数 A(n, k)
long long nPr(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[n - k] % MOD;
}

示例

cpp

int main() {
    precompute(1000000); // 预处理至 10^6
    cout << "C(5, 2) = " << nCr(5, 2) << "\n"; // 输出 10
    cout << "C(1000, 500) mod 1e9+7 = " << nCr(1000, 500) << "\n";
    return 0;
}

易错点与注意事项

模数必须为质数，否则逆元不存在。若模数非质数但为小质数的幂，可用 Lucas 定理的扩展；若为任意合数，需用质因数分解 + CRT 合并，但较复杂。
预处理范围：必须保证 n≤precompute 的 Nn≤precompute 的 N，且通常要求 N<MOD，否则 n! 在模 MOD 下为 0，inv_factinv_fact 将无法计算。若 n≥MOD 且 MOD 为质数，可用 Lucas 定理。
逆元递推公式：inv_fact[i] = inv_fact[i+1] * (i+1) % MOD 的正确性基于 (i+1)!−1⋅(i+1)≡i!−1，注意不要写反。
组合数定义域：务必检查 k < 0 或 k > n 返回 0，否则访问数组越界。
常数优化：多次查询时，预处理好阶乘表和逆元表是最高效的，避免每次使用 qpow 求逆元。

七、字符串高级算法 (String Algorithms)

41. 字符串哈希 (String Hashing) – 双哈希模板

应用场景

字符串匹配：判断两个字符串是否相等、快速比较任意两段子串（如回文判定、最长公共前缀 LCP）。
字符串去重：统计不同子串数量、后缀排序的前置步骤（结合二分比较字典序）。
滚动哈希：在滑动窗口问题中维护窗口内字符串的哈希值，实现 O(1)O(1) 增删。
字典树替代方案：某些仅需前缀查询的场景可直接用哈希表 + 前缀哈希。
二维哈希：将矩阵字符串映射为整数，快速比较矩阵区域。

复杂度分析

预处理：O(N)O(N)，构建前缀哈希数组与幂次数组。
查询任意子串哈希值：O(1)O(1)。
比较两个子串的字典序（结合二分）：O(log⁡N)O(logN)。
空间：O(N)O(N) 存储哈希数组和幂数组（双哈希则 ×2×2）。

核心心法：双哈希防冲突

单一哈希（尤其自然溢出 unsigned long long）在竞赛中容易被卡（构造冲突数据）。使用两个不同的模数（如 109+7109+7 和 109+9109+9）或一个自然溢出 + 一个大质数，可几乎完全避免哈希碰撞，做到真正的“降维打击”。

核心代码模板：双哈希（推荐）

cpp

#include <iostream>
#include <string>
#include <vector>
#include <utility>
using namespace std;

// 双哈希所使用的两个模数（均为质数）
const long long MOD1 = 1e9 + 7;
const long long MOD2 = 1e9 + 9;
const int BASE = 131; // 基数，大于字符集大小，常用 131 或 13331

// 用 pair 表示一个双哈希值
using HashVal = pair<long long, long long>;

class StringHasher {
public:
    int n;
    vector<long long> h1, h2;    // 前缀哈希
    vector<long long> p1, p2;    // 幂数组 BASE^i mod MOD

    StringHasher(const string& s) {
        n = s.size();
        h1.assign(n + 1, 0);
        h2.assign(n + 1, 0);
        p1.assign(n + 1, 0);
        p2.assign(n + 1, 0);
        p1[0] = p2[0] = 1;

        for (int i = 0; i < n; ++i) {
            // 注意：通常将字符映射为 1 ~ 26，避免 'a' 映射为 0 导致前缀歧义
            int c = s[i] - 'a' + 1;
            h1[i + 1] = (h1[i] * BASE + c) % MOD1;
            h2[i + 1] = (h2[i] * BASE + c) % MOD2;
            p1[i + 1] = (p1[i] * BASE) % MOD1;
            p2[i + 1] = (p2[i] * BASE) % MOD2;
        }
    }

    // 获取子串 [l, r] 的双哈希值，下标从 0 开始，闭区间
    HashVal getHash(int l, int r) {
        long long v1 = (h1[r + 1] - h1[l] * p1[r - l + 1]) % MOD1;
        if (v1 < 0) v1 += MOD1;
        long long v2 = (h2[r + 1] - h2[l] * p2[r - l + 1]) % MOD2;
        if (v2 < 0) v2 += MOD2;
        return {v1, v2};
    }

    // 获取整个字符串的哈希值
    HashVal getWholeHash() {
        return getHash(0, n - 1);
    }
};

使用示例：判子串相等

cpp

int main() {
    string s = "abacaba";
    StringHasher hasher(s);

    // 判断子串 s[0..2] 与 s[4..6] 是否相等 ("aba" == "aba")
    if (hasher.getHash(0, 2) == hasher.getHash(4, 6)) {
        cout << "Equal\n";
    } else {
        cout << "Not equal\n";
    }
    return 0;
}

易错点与优化细节

字符映射不要从 0 开始：若 'a' 映射为 0，则字符串 "a" 和 "" 的哈希值都会是 0，无法区分。通常将 'a' 映射为 1，或者使用 ASCII 码（但要确保基数足够大）。
取模运算中的负数处理：减法后可能得到负数，要用 (x + MOD) % MOD 调整。
双哈希比较：直接用 pair 的 == 运算符，简单安全。
模数选择：常用 1e9+7, 1e9+9, 998244353 等大质数。自然溢出 (unsigned long long) 速度最快但易被卡，双哈希已足够安全。
二维哈希扩展：以矩阵为例，可先对每一行做一维哈希，再对列方向再做一次哈希，得到二维前缀哈希。

42. KMP 字符串匹配算法 (Knuth-Morris-Pratt)

应用场景

单模式串匹配：在文本串 SS 中找出模式串 PP 出现的所有位置，时间复杂度严格 O(∣S∣+∣P∣)O(∣S∣+∣P∣)。
最小循环节：利用 next 数组的性质，快速求出一个字符串的最小循环节长度。
前缀与后缀匹配问题：所有需要在字符串内部“自我比较”的场景（例如求字符串的 border、前缀函数是 AC 自动机的基础）。
扩展应用：循环同构判断、重复子串统计、与其他 DP 结合处理字符串上的状态转移。

复杂度分析

构建 next 数组（前缀函数）：时间 O(M)O(M)，M=∣P∣M=∣P∣。
匹配过程：时间 O(N)O(N)，N=∣S∣N=∣S∣。
总体：O(N+M)O(N+M)，空间 O(M)O(M)（存储 next 数组）。

核心心法：next 数组与失配回退

KMP 的精髓在于“利用之前已经匹配的部分，避免文本串指针回退”。

定义 next[i]：在模式串 PP 的前缀 P[0..i]P[0..i] 中，最长的相等真前缀与真后缀的长度。换一种说法：如果 P[i]P[i] 位置失配，模式串可以跳转到 next[i-1] 继续尝试匹配，而文本串指针 i 不用动。
匹配时：i 遍历文本串，j 遍历模式串。当 S[i]≠P[j]S[i]=P[j] 时，j 跳回 next[j-1]（若 j>0），否则 i++。若 j == M，说明找到一个完整匹配，记录位置后继续失配处理（视需求决定是否继续匹配）。

标准实现中，常用前缀函数 pi 表示：pi[i] 为子串 P[0..i]P[0..i] 的最长相等真前后缀长度，等价于常见的 next 概念。匹配时使用 pi 数组加速。

代码模板：0-index 标准版（前缀函数 + 匹配）

cpp

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 构建前缀函数 pi（即 next 数组）
vector<int> build_pi(const string& p) {
    int m = p.size();
    vector<int> pi(m, 0);
    // j 指向当前最长匹配前缀的下一个位置（同时也是长度）
    for (int i = 1; i < m; ++i) {
        int j = pi[i - 1];
        while (j > 0 && p[i] != p[j]) {
            j = pi[j - 1];    // 回退
        }
        if (p[i] == p[j]) {
            j++;
        }
        pi[i] = j;
    }
    return pi;
}

// 返回模式串 p 在文本串 s 中所有匹配的起始下标（0-index）
vector<int> kmp_search(const string& s, const string& p) {
    vector<int> ans;
    if (p.empty()) return ans;
    auto pi = build_pi(p);
    int n = s.size(), m = p.size();
    int j = 0; // 模式串指针
    for (int i = 0; i < n; ++i) {
        while (j > 0 && s[i] != p[j]) {
            j = pi[j - 1];    // 失配时跳转
        }
        if (s[i] == p[j]) {
            j++;
        }
        if (j == m) {
            ans.push_back(i - m + 1); // 匹配成功，记录起始位置
            j = pi[j - 1];           // 继续匹配下一个（允许重叠）
        }
    }
    return ans;
}

int main() {
    string s = "ababacabab";
    string p = "abab";
    auto pos = kmp_search(s, p);
    for (int idx : pos) cout << idx << " "; // 输出 0 4 6（重叠匹配）
    return 0;
}

易错点与注意事项

pi 数组的定义：pi[i] 是子串 p[0..i]p[0..i] 的最长相等真前后缀长度，匹配时失配回退用 pi[j-1]，而不是 pi[j]。代码中先 j = pi[j-1] 再比较 s[i] == p[j]。
回退循环：while (j > 0 && p[i] != p[j]) 中条件不能写成 while (j >= 0 && ...)，因为 j=0 时无法再回退。
边界情况：模式串为空时应该处理，通常返回空匹配。
重叠匹配：找到一次匹配后，可将 j = pi[j-1] 继续匹配，如果不需要重叠匹配，则 j = 0 重新开始（视题目而定）。
下标区别：有些旧教材使用 next[1..m] 的形式，注意不要混淆。现代写法统一使用 pi 数组更加简洁。

马拉车算法 (Manacher)：$O(N)$ 极速求解最长回文子串。

43. 马拉车算法 (Manacher) – 最长回文子串

应用场景

在 O(N)O(N) 时间内求出一个字符串的最长回文子串（长度与具体内容均可）。
统计字符串中所有回文子串的个数（以每个位置为中心的回文半径直接可得）。
回文性质判定、回文分割、与 DP 结合处理回文相关问题。

复杂度分析

时间复杂度：O(N)O(N)。虽然有两层循环，但内层 while 的扩张总次数受到最右边界扩大的限制，每个字符被暴力比较的次数均摊为 O(1)O(1)。
空间复杂度：O(N)O(N)。需要一个长度为 2N+12N+1 的辅助字符串以及臂长数组。

核心心法：统一奇偶回文 + 最右边界加速

插入分隔符：在原始字符串每个字符间以及首尾插入 #（或其他不存在于原串的字符），将奇回文和偶回文统一成奇回文处理。
例如 "aba" → "#a#b#a#"，"aa" → "#a#a#"。变换后的字符串长度恒为 2n+12n+1。
维护三个核心变量：
- C：当前最右回文边界的中心。
- R：最右回文边界（即 C 能覆盖到的最右侧下标，且 R = C + radius[C]，其中 radius 是变换后字符串的臂长）。
- radius[i]：以 i 为中心的最大回文半径（包括中心自身）。在原串中的实际回文长度为 radius[i] - 1。
算法流程：从左到右计算 radius[i]。
- 若 i < R，则 radius[i] 至少为 min(radius[2*C - i], R - i)（利用对称性）。
- 然后暴力向两边扩展尝试增大半径。
- 若扩展后的 i + radius[i] > R，则更新 C = i，R = i + radius[i]。

最终，遍历 radius 数组找到最大值，即可得到最长回文子串的长度和位置。

核心代码模板

cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 返回原字符串的最长回文子串
string longestPalindrome(const string& s) {
    if (s.empty()) return "";

    // 1. 构建变换串 T，首尾和中间插入 '#'
    string T = "#";
    for (char ch : s) {
        T.push_back(ch);
        T.push_back('#');
    }
    int n = T.size();
    vector<int> radius(n, 0);

    int C = 0, R = 0;            // 最右回文的中心和右边界
    int max_len = 0, center = 0; // 记录原串中最长回文的信息

    for (int i = 0; i < n; ++i) {
        // 2. 利用对称性初始化半径
        if (i < R) {
            int mirror = 2 * C - i;
            radius[i] = min(radius[mirror], R - i);
        } else {
            radius[i] = 1; // 至少自身为一个回文中心
        }

        // 3. 暴力扩展
        while (i - radius[i] >= 0 && i + radius[i] < n &&
               T[i - radius[i]] == T[i + radius[i]]) {
            radius[i]++;
        }

        // 4. 更新最右边界
        if (i + radius[i] - 1 > R) {
            C = i;
            R = i + radius[i] - 1;
        }

        // 5. 记录最长回文（原串中的长度 = radius[i] - 1）
        int cur_len = radius[i] - 1;
        if (cur_len > max_len) {
            max_len = cur_len;
            center = i;
        }
    }

    // 6. 从变换串的位置还原原串中的起始下标
    int start = (center - max_len) / 2;
    return s.substr(start, max_len);
}

// 若只需要最长回文长度，可简化
int longestPalindromeLength(const string& s) {
    if (s.empty()) return 0;
    string T = "#";
    for (char ch : s) { T.push_back(ch); T.push_back('#'); }
    int n = T.size();
    vector<int> radius(n, 0);
    int C = 0, R = 0, max_len = 0;
    for (int i = 0; i < n; ++i) {
        radius[i] = (i < R) ? min(radius[2*C - i], R - i) : 1;
        while (i - radius[i] >= 0 && i + radius[i] < n &&
               T[i - radius[i]] == T[i + radius[i]]) {
            radius[i]++;
        }
        if (i + radius[i] - 1 > R) {
            C = i;
            R = i + radius[i] - 1;
        }
        max_len = max(max_len, radius[i] - 1);
    }
    return max_len;
}

int main() {
    string s = "babad";
    cout << "最长回文子串: " << longestPalindrome(s) << endl; // 输出 "bab" 或 "aba"
    cout << "长度: " << longestPalindromeLength(s) << endl;     // 3
    return 0;
}

44. AC 自动机 (Aho-Corasick Automaton) – 多模式串匹配

应用场景

从一段文本中同时查找多个模式串（敏感词过滤、搜索引擎的多关键词匹配、病毒特征码扫描）。
统计每个模式串在文本中的出现次数（配合 fail 树的拓扑累加，避免暴力跳转）。
自动机上的 DP：求解不含某些模式串的字符串个数、构造最小修改避开模式串等（与数位 DP 思路类似，在自动机上转移状态）。
后缀自动机 (SAM) 的前置基础，AC 自动机的 fail 树是许多字符串高级算法的核心结构。

复杂度分析

构建 Trie + 构建 fail 指针：O(∑∣Pi∣)O(∑∣Pi∣)，即所有模式串的总长度。
匹配文本串 SS：均摊 O(∣S∣+匹配总次数)O(∣S∣+匹配总次数)。若使用 fail 树拓扑优化统计出现次数，额外 O(∑∣Pi∣)O(∑∣Pi∣)。
空间复杂度：O(∑∣Pi∣×∣Σ∣)O(∑∣Pi∣×∣Σ∣)，其中 ∣Σ∣∣Σ∣ 为字符集大小（通常 26）。可用数组或 vector 动态开点优化。

核心心法：Trie 上的 KMP 思想

在 Trie 上，每个节点代表一个前缀。
fail 指针 指向当前节点所代表字符串的 最长真后缀，且该后缀也是某个模式串的前缀（即存在于 Trie 中）。这与 KMP 的 next 数组含义完全一致。
构造 fail 使用 BFS：对于节点 u 的每个子节点 v（字符 c），fail[v] 指向 fail[u] 沿着字符 c 能走到的节点。
为匹配方便，通常对 Trie 进行 Trie 图优化：将不存在的子节点直接指向 fail 节点的对应子节点，这样匹配时无需判空，直接转移。

核心代码模板：静态数组版（含出现次数统计）

cpp

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

const int MAXN = 500005;   // 所有模式串总长度
const int MAXC = 26;       // 字符集大小（小写字母）

struct AC {
    int nxt[MAXN][MAXC];   // Trie 树 / Trie 图
    int fail[MAXN];        // fail 指针
    int cnt[MAXN];         // 以该节点结尾的模式串数量
    int node_cnt;          // 当前节点总数，根为 0

    // 构造函数：初始化根节点
    AC() {
        node_cnt = 0;
        for (int i = 0; i < MAXC; ++i) nxt[0][i] = 0;
        fail[0] = 0;
        cnt[0] = 0;
    }

    // 插入一个模式串
    void insert(const string& s) {
        int u = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (!nxt[u][c]) {
                nxt[u][c] = ++node_cnt;
                for (int i = 0; i < MAXC; ++i) nxt[node_cnt][i] = 0;
                fail[node_cnt] = 0;
                cnt[node_cnt] = 0;
            }
            u = nxt[u][c];
        }
        cnt[u]++;   // 模式串结束标记
    }

    // 构建 fail 指针（BFS 生成 Trie 图）
    void build() {
        queue<int> q;
        for (int c = 0; c < MAXC; ++c) {
            int v = nxt[0][c];
            if (v) {
                fail[v] = 0;
                q.push(v);
            } else {
                nxt[0][c] = 0; // 根的不存在的边指向自己（保持 Trie 图完整）
            }
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int c = 0; c < MAXC; ++c) {
                int v = nxt[u][c];
                if (v) {
                    // 子节点存在：其 fail 指向 fail[u] 的对应字符子节点
                    fail[v] = nxt[fail[u]][c];
                    q.push(v);
                } else {
                    // 子节点不存在：直接指向 fail[u] 的子节点（Trie 图优化）
                    nxt[u][c] = nxt[fail[u]][c];
                }
            }
        }
    }

    // 在文本串 s 中匹配，返回每个模式串的出现次数（需配合 fail 树统计）
    vector<int> query(const string& s, int pattern_cnt) {
        vector<int> node_vis(node_cnt + 1, 0); // 每个节点被访问的次数
        int u = 0;
        for (char ch : s) {
            int c = ch - 'a';
            u = nxt[u][c];             // 直接转移（Trie 图）
            node_vis[u]++;             // 记录当前节点访问次数
        }

        // 因为 fail 指针构成了树，需要按 BFS 逆序（拓扑序）累加计数
        // 这里先获得 BFS 序（即节点在队列中被访问的顺序）
        vector<int> bfs_order;
        queue<int> q;
        for (int c = 0; c < MAXC; ++c) {
            if (nxt[0][c]) q.push(nxt[0][c]);
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            bfs_order.push_back(u);
            for (int c = 0; c < MAXC; ++c) {
                int v = nxt[u][c];
                // 注意：使用原 Trie 树结构（未优化的子节点指针）来 BFS 可能被覆盖
                // 安全做法：build 时保留原树，另用数组存子节点列表；这里采用预先存储所有节点及其转移边的方案。
                // 简化起见，可以直接用 node_cnt 和已知的 BFS 序，或者再次 BFS 并用原始子节点（需额外存储）。
            }
        }

        // 逆序遍历 BFS 序，累加 fail 树贡献
        for (int i = bfs_order.size() - 1; i >= 0; --i) {
            int u = bfs_order[i];
            node_vis[fail[u]] += node_vis[u];
        }

        // 统计每个模式串的出现次数：模式串结尾节点的 node_vis 值
        vector<int> result(pattern_cnt, 0);
        // 这里需要外部记录每个模式串的结尾节点编号，通常 insert 时记录下来
        // 省略细节：例如使用 vector<int> end_id(pattern_cnt) 存储
        return result;
    }
};

使用示例：统计每个模式串出现次数

cpp

int main() {
    AC ac;
    int n;
    cin >> n;
    vector<int> end_id(n);
    for (int i = 0; i < n; ++i) {
        string pat;
        cin >> pat;
        // 记录插入前的节点编号？需修改 insert 返回结尾节点
        // 这里简化为在类内部增加记录
    }
    ac.build();
    string text;
    cin >> text;
    auto ans = ac.query(text, n);
    for (int x : ans) cout << x << "\n";
    return 0;
}

核心补充：记录模式串结尾节点

在 insert 时可返回节点编号，或外部调用时用一个变量记录：

cpp

int insert(const string& s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (!nxt[u][c]) {
            nxt[u][c] = ++node_cnt;
            // 初始化新节点（略）
        }
        u = nxt[u][c];
    }
    cnt[u]++;
    return u; // 返回结尾节点编号
}

然后在 query 中通过 end_id[i] 得到 node_vis[end_id[i]] 即为模式串出现次数。

易错点与注意事项

节点编号 0 为根，fail[0] = 0，根的不存在边指向 0，保证任何字符都能在根处转移。
Trie 图优化：在 build 时，将不存在的子节点直接指向 fail[u] 的对应子节点，匹配时无需 while 跳 fail，直接 u = nxt[u][c]，效率更高。
统计出现次数：直接在每个访问节点 u 上递增计数器，最后沿 fail 树的拓扑逆序（BFS 逆序）将子节点的计数累加到父节点 fail[u]，避免每个匹配节点暴力上跳导致退化。
fail 树的拓扑序：BFS 构造 fail 时的队列顺序恰好是 fail 树的层次遍历，逆序即可实现从叶子到根的累加。
字符集大小：这里默认 26 个小写字母，若包含大写或数字，可调整为 26+26+10=62，或使用哈希映射。
多模式串重叠问题：若模式串有前缀包含关系（如 "ab" 和 "abc"），在文本 "abc" 中两者都应被匹配。上述拓扑累加方法能自动处理。

八、计算几何 (Computational Geometry)

（这部分在非 ICPC 竞赛中考得较少，但大厂笔试偶有涉及，备几个基础的即可）

二维点/向量结构体：封装好点积（Dot）、叉积（Cross）和距离计算。

45. 二维点/向量结构体 (Point & Vector 2D)

应用场景

所有平面几何问题的基石：点的位置、向量运算、距离角度计算。
判断方向：叉积判断点在线段左侧/右侧、三点共线。
面积计算：三角形、多边形面积（叉积的累加）。
线段相交判定、点到线段/直线的距离、凸包、旋转卡壳等高级算法均基于此。

复杂度分析

所有基本运算（加减、点积、叉积、距离）均为 O(1)O(1)，常数极小。

核心心法：统一向量与点

在计算几何中，点可以视为从原点出发的向量，向量运算可以直接应用于点。一个设计良好的结构体应该支持：

向量加减：对应点平移、向量合成。
标量乘法：缩放向量。
点积 (Dot Product)：a⋅b=∣a∣∣b∣cos⁡θa⋅b=∣a∣∣b∣cosθ，用于求夹角、投影、判断垂直。
叉积 (Cross Product)：a×b=xayb−yaxba×b=xayb−yaxb，其绝对值等于以 aa 和 bb 为边的平行四边形面积，符号表示方向（正：bb 在 aa 的逆时针方向）。
模长与距离。
旋转：逆时针旋转一定弧度。

核心代码模板

cpp

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const double eps = 1e-9; // 浮点误差容忍

// 符号函数：正数返回1，负数返回-1，零返回0
int sgn(double x) {
    if (fabs(x) < eps) return 0;
    return (x > 0) ? 1 : -1;
}

struct Point {
    double x, y;

    Point() : x(0), y(0) {}
    Point(double _x, double _y) : x(_x), y(_y) {}

    // 向量加法
    Point operator+(const Point& p) const { return Point(x + p.x, y + p.y); }
    // 向量减法
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    // 标量乘法
    Point operator*(double k) const { return Point(x * k, y * k); }
    // 标量除法
    Point operator/(double k) const { return Point(x / k, y / k); }

    // 点积 (内积)
    double dot(const Point& p) const { return x * p.x + y * p.y; }
    // 叉积 (外积，z 分量)
    double cross(const Point& p) const { return x * p.y - y * p.x; }

    // 模长的平方
    double len2() const { return x * x + y * y; }
    // 模长
    double len() const { return sqrt(len2()); }

    // 到另一个点的距离
    double dist(const Point& p) const { return (*this - p).len(); }

    // 逆时针旋转 rad 弧度
    Point rotate(double rad) const {
        double c = cos(rad), s = sin(rad);
        return Point(x * c - y * s, x * s + y * c);
    }

    // 单位向量（零向量调用需小心）
    Point unit() const {
        double l = len();
        if (sgn(l) == 0) return Point(0, 0);
        return Point(x / l, y / l);
    }

    // 比较运算符（用于排序，先 x 后 y）
    bool operator<(const Point& p) const {
        if (sgn(x - p.x) != 0) return x < p.x;
        return y < p.y;
    }
    bool operator==(const Point& p) const {
        return sgn(x - p.x) == 0 && sgn(y - p.y) == 0;
    }
};

// 一些常用非成员函数
double dot(const Point& a, const Point& b) { return a.dot(b); }
double cross(const Point& a, const Point& b) { return a.cross(b); }
double dist(const Point& a, const Point& b) { return a.dist(b); }

使用示例：方向与面积

cpp

int main() {
    Point A(0, 0), B(3, 0), C(1, 2);

    // 向量 AB 和 AC
    Point AB = B - A;
    Point AC = C - A;

    // 叉积判断方向：正值表示 C 在 AB 的左侧（逆时针方向）
    double dir = cross(AB, AC);
    if (sgn(dir) > 0)
        cout << "C 在 AB 的左侧\n";
    else if (sgn(dir) < 0)
        cout << "C 在 AB 的右侧\n";
    else
        cout << "A, B, C 共线\n";

    // 三角形 ABC 的有向面积（叉积的一半）
    double area = fabs(dir) / 2.0;
    cout << "三角形面积: " << area << endl; // 3

    // 点积判断垂直：若 AB 与 AC 垂直，点积为0
    if (sgn(dot(AB, AC)) == 0)
        cout << "AB 与 AC 垂直\n";
    else
        cout << "不垂直\n";

    return 0;
}

易错点与注意事项

叉积符号：二维叉积返回标量，cross(a,b) = a.x*b.y - a.y*b.x。正负由右手定则决定：若 a 到 b 是逆时针，则为正。千万不要与点积混淆。
浮点比较：必须使用 sgn 与 eps，不可直接用 ==。三角函数旋转可能引入微小误差。
零向量：单位化前需判断模长是否为 0，否则得到 nan。
旋转方向：逆时针旋转公式 x′=xcos⁡θ−ysin⁡θx′=xcosθ−ysinθ, y′=xsin⁡θ+ycos⁡θy′=xsinθ+ycosθ，确认正负号。
排序规则：operator< 应先按 x，再按 y，用于有序集合或凸包预处理。

46. 线段相交判定 – 跨立实验 (Segment Intersection)

应用场景

判断两条线段是否相交（包括严格相交或允许端点重合）。
多边形自交检测、路径碰撞检测、地图中线段交叉计数。
计算几何的许多高级算法（线段与多边形关系、线段树 + 扫描线求交点）都以此为基础。

复杂度分析

时间复杂度：O(1)O(1)，仅需若干次叉积和比较运算。
空间复杂度：O(1)O(1)。

核心心法：快速排斥 + 跨立实验

判断两条线段 ABAB 和 CDCD 是否相交，分两步：

快速排斥实验：用矩形框（axis-aligned bounding box）快速排除明显不可能相交的情况。若 ABAB 的矩形与 CDCD 的矩形没有重叠，则必然不相交。
- max⁡(A.x,B.x)<min⁡(C.x,D.x)max(A.x,B.x)<min(C.x,D.x) 或 max⁡(C.x,D.x)<min⁡(A.x,B.x)max(C.x,D.x)<min(A.x,B.x)
- max⁡(A.y,B.y)<min⁡(C.y,D.y)max(A.y,B.y)<min(C.y,D.y) 或 max⁡(C.y,D.y)<min⁡(A.y,B.y)max(C.y,D.y)<min(A.y,B.y)
  满足以上任意条件直接返回 false。
跨立实验：利用叉积判断一条线段的两个端点是否在另一条线段的两侧。对于线段 ABAB 和 CDCD：
- 计算 cross(AB,AC)cross(AB,AC) 与 cross(AB,AD)cross(AB,AD) 的符号，两者异号（或一个为 0）说明 CC 和 DD 在 ABAB 两侧。
- 同理，cross(CD,CA)cross(CD,CA) 与 cross(CD,CB)cross(CD,CB) 异号（或一个为 0）说明 AA 和 BB 在 CDCD 两侧。
- 当两个条件同时满足时，线段相交。

跨立实验的严格相交与允许端点重合：

若要求严格相交（不含端点），则要求叉积符号必须严格异号（均不为 0）。
若允许端点重合，则叉积为 0 也视为满足（即点在线段所在的直线上）。

核心代码模板（基于之前的 Point 结构体）

cpp

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const double eps = 1e-9;
int sgn(double x) { return (fabs(x) < eps) ? 0 : (x > 0 ? 1 : -1); }

struct Point {
    double x, y;
    Point() : x(0), y(0) {}
    Point(double _x, double _y) : x(_x), y(_y) {}
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    double cross(const Point& p) const { return x * p.y - y * p.x; }
    double dot(const Point& p) const { return x * p.x + y * p.y; }
    bool operator<(const Point& p) const {
        if (sgn(x - p.x) != 0) return x < p.x;
        return y < p.y;
    }
};

// 辅助函数：叉积
double cross(const Point& a, const Point& b) { return a.cross(b); }

// 判断点 p 是否在线段 ab 上（不含端点？含端点则 >=0 <=...）
bool onSegment(const Point& p, const Point& a, const Point& b) {
    // 共线且投影点积非正（即 p 在 a 和 b 之间）
    return sgn(cross(a - p, b - p)) == 0 &&
           sgn((a - p).dot(b - p)) <= 0;
}

// 线段相交判定：allow_endpoint 为 true 则允许端点重合相交
bool segmentIntersect(const Point& A, const Point& B,
                      const Point& C, const Point& D,
                      bool allow_endpoint = true) {
    // 快速排斥
    if (max(A.x, B.x) < min(C.x, D.x) || max(C.x, D.x) < min(A.x, B.x)) return false;
    if (max(A.y, B.y) < min(C.y, D.y) || max(C.y, D.y) < min(A.y, B.y)) return false;

    // 计算跨立所需的叉积符号
    double c1 = cross(B - A, C - A);
    double c2 = cross(B - A, D - A);
    double c3 = cross(D - C, A - C);
    double c4 = cross(D - C, B - C);

    if (allow_endpoint) {
        // 允许端点接触：只需符号不相反且乘积 <=0 即可
        if (sgn(c1) * sgn(c2) > 0) return false;
        if (sgn(c3) * sgn(c4) > 0) return false;
        return true;
    } else {
        // 严格相交（不含端点）：必须严格异号
        if (sgn(c1) * sgn(c2) >= 0) return false; // 同号或有一个为0都不行
        if (sgn(c3) * sgn(c4) >= 0) return false;
        return true;
    }
}

使用示例

cpp

int main() {
    Point A(0, 0), B(2, 2);
    Point C(0, 2), D(2, 0);
    
    // 相交于 (1,1)
    if (segmentIntersect(A, B, C, D))
        cout << "线段相交\n";
    else
        cout << "不相交\n";

    // 端点接触：E(0,0) F(1,1) 与 G(1,1) H(2,2)
    Point E(0,0), F(1,1), G(1,1), H(2,2);
    cout << "允许端点重合: " << segmentIntersect(E, F, G, H, true) << endl;  // 1
    cout << "严格相交: " << segmentIntersect(E, F, G, H, false) << endl;    // 0
    return 0;
}

易错点与注意事项

浮点数误差：叉积比较必须使用 sgn，不能直接与 0 比较。
快速排斥不能省略，它能快速排除大量不相交情况，同时也能处理线段退化为点的情况（矩形无面积时依然有效）。
onSegment 的作用：当 allow_endpoint = true 时，若一个点落在另一线段上，则叉积会出现 0，sgn(c1)*sgn(c2) <= 0 会将其判定为相交。此时若需精确区分“端点重合”还是“内部相交”，可再用 onSegment 辅助判断。
共线情况：两条线段共线且部分重叠时，跨立实验会得到 0 乘积，allow_endpoint = true 下会判为相交（正确）。但若共线且无重叠（如 A---B C---D 且 B 与 C 之间有间隙），快速排斥可以将其排除。因此必须先用快速排斥。
线段退化：若一条线段两端点相同，cross(B-A, ...) 为零向量，此时 c1 和 c2 均为 0，跨立实验失效。但快速排斥可以捕获点与线段的关系。若需要判定点是否在线段上，应单独使用 onSegment。

47. 凸包 (Convex Hull) – Andrew 算法

应用场景

给定平面上一组点，求覆盖所有点的最小凸多边形（凸包），是许多几何问题的基础。
求点集直径（最远点对）：利用旋转卡壳在凸包上 O(N)O(N) 求出。
点集的最小外接矩形、最小外接圆（Welzl 算法需凸包辅助）。
判断点是否在凸多边形内、求两凸包间最短距离、Minkowski 和等。

复杂度分析

时间复杂度：O(Nlog⁡N)O(NlogN)，瓶颈在于排序。扫描过程 O(N)O(N)。
空间复杂度：O(N)O(N)，存储排序后的点集和凸包栈。

核心心法：上下凸壳分别扫描

Andrew 算法（又称单调链算法）避免了 Graham Scan 中复杂的按极角排序和共线处理，仅需按 xx 坐标排序（xx 相同按 yy 排序），然后分别构造下凸壳和上凸壳。

排序：将所有点按 xx 升序，xx 相同时按 yy 升序。
下凸壳：从左到右遍历点，维护一个栈。当新点加入时，持续检查栈顶两个点与新点构成的向量是否形成“右转”（叉积 ≤0≤0），若是则弹出栈顶。这样保证下凸壳始终是“左转”前进。
上凸壳：从右到左遍历点，同样维护栈，保证左转。
合并：下凸壳的最后一个点和上凸壳的最后一个点分别是另一个方向的首点，需去重。

最后得到的凸包顶点按照逆时针（或顺时针）顺序排列。

核心代码模板（基于之前的 Point 结构体）

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const double eps = 1e-9;
int sgn(double x) { return (fabs(x) < eps) ? 0 : (x > 0 ? 1 : -1); }

struct Point {
    double x, y;
    Point() : x(0), y(0) {}
    Point(double _x, double _y) : x(_x), y(_y) {}
    Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
    double cross(const Point& p) const { return x * p.y - y * p.x; }
    bool operator<(const Point& p) const {
        if (sgn(x - p.x) != 0) return x < p.x;
        return y < p.y;
    }
};

double cross(const Point& a, const Point& b) { return a.cross(b); }

// Andrew 算法求凸包，返回逆时针排列的凸包顶点（不含重复起点）
vector<Point> convexHull(vector<Point> pts) {
    int n = pts.size();
    if (n <= 2) return pts; // 点集太小，直接返回

    sort(pts.begin(), pts.end());
    vector<Point> hull(2 * n); // 预留足够空间
    int k = 0;                 // 栈指针

    // 构建下凸壳 (从左到右)
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && sgn(cross(hull[k-1] - hull[k-2], pts[i] - hull[k-1])) <= 0) {
            k--;
        }
        hull[k++] = pts[i];
    }

    // 构建上凸壳 (从右到左)
    int t = k + 1; // 记录下凸壳终点，避免重复
    for (int i = n - 2; i >= 0; --i) {
        while (k >= t && sgn(cross(hull[k-1] - hull[k-2], pts[i] - hull[k-1])) <= 0) {
            k--;
        }
        hull[k++] = pts[i];
    }

    hull.resize(k - 1); // 最后一个点与第一个点重复，去掉
    return hull;
}

使用示例：求凸包面积（即多边形面积）

cpp

// 多边形面积（顶点按顺序给出，逆时针返回正，顺时针返回负）
double polygonArea(const vector<Point>& poly) {
    double area = 0;
    int n = poly.size();
    for (int i = 0; i < n; ++i) {
        int j = (i + 1) % n;
        area += cross(poly[i], poly[j]);
    }
    return fabs(area) / 2.0;
}

int main() {
    vector<Point> pts = {{0,0}, {1,0}, {2,1}, {1,2}, {0,1}, {1,1}};
    vector<Point> hull = convexHull(pts);
    cout << "凸包顶点:\n";
    for (auto& p : hull) cout << "(" << p.x << "," << p.y << ")\n";
    cout << "凸包面积: " << polygonArea(hull) << endl;
    return 0;
}

易错点与注意事项

叉积条件：使用 <= 0 意味着剔除共线或右转的情况。若要求保留凸包边上的共线点，则改为 < 0（仅剔除右转）。默认模板用 <= 0 得到严格的凸多边形（边界上无多余点）。
排序的稳定性：按 xx 升序、xx 相同按 yy 升序，这样可以唯一确定点的顺序，避免因等 xx 导致的凸包构建错误。
栈的容量：hull 预开 2n2n 空间，足够存放临时点。
边界情况：n≤2n≤2 直接返回即可。
下凸壳末尾和上凸壳起点的处理：上凸壳从 n-2 开始，避免重复加入最右侧点（该点已在下凸壳末尾）。k 的调整通过 t = k+1 保证不弹出下凸壳的最后一个点。
最终凸包的顶点顺序：Andrew 返回的点顺序是逆时针（从最左下点开始，沿下凸壳到最右，再沿上凸壳回到最左）。可以通过取反（reverse）得到顺时针。
凸包面积/周长：直接用上述 polygonArea 或逐边距离累加。

九、搜索与回溯 (Search & Backtracking)

这是解决迷宫问题、连通块问题、穷举问题以及所有“没有现成算法公式”的万能解法。

广度优先搜索 (BFS) —— 空间蔓延与最短路

BFS 的本质是“水波纹蔓延”。只要图中每一步的扩展代价相等，BFS 第一次碰到终点时，走过的路线绝对是最短的。

48. 基础网格图 BFS (Grid BFS)

应用场景：迷宫最短路径（无复杂权值）、图像泛洪填充、走马步问题、任何二维网格上的等代价搜索。

复杂度分析：时间复杂度 $O(R \times C)$ ，空间复杂度 $O(R \times C)$ 。每个格子至多入队一次。

核心心法：永远使用 dx 和 dy 方向数组配合 for 循环；用 queue 存储坐标；用 steps 按层扩展。

C++

#include <queue>
#include <vector>
using namespace std;

// 技巧：定义方向数组，极速遍历上下左右四个方向
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

int gridBFS(vector<vector<int>>& grid, int sx, int sy, int tx, int ty) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    queue<pair<int, int>> q;
    
    q.push({sx, sy});
    vis[sx][sy] = true;
    int steps = 0;

    while (!q.empty()) {
        int sz = q.size();
        // 核心：按层遍历，这一层的所有节点算作相同的 steps
        while (sz--) {
            auto [x, y] = q.front(); 
            q.pop();
            
            if (x == tx && y == ty) return steps; // 找到终点，直接返回最短步数

            for (int d = 0; d < 4; ++d) {
                int nx = x + dx[d], ny = y + dy[d];
                // 越界检查 + 未访问检查 + 障碍物检查 (-1 表示障碍)
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx][ny] && grid[nx][ny] != -1) { 
                    vis[nx][ny] = true; // ⚠️ 必须在入队时就标记访问，否则会导致内存超限 (MLE)
                    q.push({nx, ny});
                }
            }
        }
        steps++;
    }
    return -1; // 不可达
}

49. 多源 BFS (Multi-source BFS)

应用场景：腐烂的橘子、01 矩阵（求每个 1 到最近的 0 的距离）。

核心心法：多源 BFS 和普通 BFS 没有任何逻辑差异！你只需要在初始化时，将所有源点同时入队。它们会像多个水波一样同时向外扩散，完美解决“最近距离”问题。

C++

// 经典：求网格中每个位置到最近水源的距离（0 表示水源）
vector<vector<int>> multiSourceBFS(vector<vector<int>>& grid) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;
    
    // 初始化：找出所有水源，同时塞入队列，距离设为 0
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 0) {
                dist[i][j] = 0;
                q.push({i, j});
            }
        }
    }
    
    // 后续扩展与单源 BFS 完全一致
    while (!q.empty()) {
        auto [x, y] = q.front(); 
        q.pop();
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1; // 新位置的距离 = 源头距离 + 1
                q.push({nx, ny});
            }
        }
    }
    return dist;
}

50. 0-1 BFS (双端队列降维打击)

应用场景：边权只有 0 或 1 的图的最短路（例如：网格中经过特殊地形消耗 1，走空地消耗 0）。

核心心法：直接淘汰 $O(E \log V)$ 的 Dijkstra，换用 std::deque！遇到代价为 0 的边，压入队首（优先处理）；代价为 1 的边，压入队尾。这能强行保证队列的单调性，将复杂度压制到极限的 $O(V+E)$ 。

C++

#include <deque>

int zeroOneBFS(vector<vector<pair<int,int>>>& adj, int src, int dst) {
    int n = adj.size();
    vector<int> dist(n, 1e9); // 1e9 代表无穷大
    deque<int> dq;
    
    dist[src] = 0;
    dq.push_front(src);

    while (!dq.empty()) {
        int u = dq.front(); 
        dq.pop_front();
        
        for (auto [v, w] : adj[u]) { // v 是邻居，w 是边权 (只可能是 0 或 1)
            // 经典的松弛操作
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                // 核心分流：0 权边插队首，1 权边扔队尾
                if (w == 0) dq.push_front(v);
                else        dq.push_back(v);
            }
        }
    }
    return dist[dst];
}

51. 双向 BFS (Bidirectional BFS)

应用场景：明确知道起点和终点，但搜索空间巨大且呈指数级爆炸（如单词接龙、八数码）。

核心心法：如果单向 BFS 的时间复杂度是 $O(b^d)$ （$b$ 为分支因子，$d$ 为深度）。双向 BFS 从起点和终点交替扩展，相遇即停止。复杂度骤降至 $O(b^{d/2} + b^{d/2})$ ，这是肉眼可见的性能飞跃。实战技巧：每次优先扩展节点数较少的那一端。

C++

#include <unordered_set>
#include <string>

// 经典：单词接龙 (Word Ladder)
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    if (!dict.count(endWord)) return 0; // 终点不在字典中，直接判死刑

    // 维护两个方向的当前层集合
    unordered_set<string> q1{beginWord}, q2{endWord};
    // 维护两个方向的已访问集合
    unordered_set<string> vis1{beginWord}, vis2{endWord};
    int steps = 1;

    while (!q1.empty() && !q2.empty()) {
        // 极致优化：永远优先扩展较小的集合，控制指数爆炸
        if (q1.size() > q2.size()) {
            swap(q1, q2);
            swap(vis1, vis2);
        }
        
        unordered_set<string> next;
        for (auto s : q1) {
            for (int i = 0; i < s.size(); ++i) {
                char c = s[i];
                // 尝试替换 26 个字母
                for (char ch = 'a'; ch <= 'z'; ++ch) {
                    s[i] = ch;
                    if (dict.count(s)) {
                        // 如果在另一端的队列里发现了这个词，说明顺利会师！
                        if (q2.count(s)) return steps + 1;
                        if (!vis1.count(s)) {
                            vis1.insert(s);
                            next.insert(s);
                        }
                    }
                }
                s[i] = c; // 恢复原状
            }
        }
        q1 = next;
        steps++;
    }
    return 0; // 无法相遇
}

52. 状态空间 BFS (State-space BFS)

应用场景：推箱子、倒水问题、八数码。此时“节点”不再是一个坐标，而是一个完整的“系统状态”。

核心心法：将复杂的二维/多维状态压缩序列化（变成字符串或大整数），配合 unordered_set 进行判重。

C++

// 经典：滑动谜题 (2x3 的八数码变种)
int slidingPuzzle(vector<vector<int>>& board) {
    string start;
    for (auto& row : board) 
        for (int x : row) 
            start += to_string(x); // 序列化起始状态
            
    string target = "123450"; // 目标状态
    unordered_set<string> vis;
    queue<string> q;
    
    q.push(start);
    vis.insert(start);
    int steps = 0;
    
    // 预处理：在 2x3 展开的一维字符串中，每个索引位置可以向哪些索引交换？
    vector<vector<int>> dirs = {{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};

    while (!q.empty()) {
        int sz = q.size();
        while (sz--) {
            string s = q.front(); q.pop();
            if (s == target) return steps;
            
            int zero = s.find('0'); // 找到空格的位置
            for (int nxt : dirs[zero]) {
                swap(s[zero], s[nxt]); // 尝试移动空格
                if (!vis.count(s)) {
                    vis.insert(s);
                    q.push(s);
                }
                swap(s[zero], s[nxt]); // 恢复现场
            }
        }
        steps++;
    }
    return -1;
}

战区二：深度优先搜索 (DFS) 与回溯 —— 破釜沉舟的试探

DFS 的核心是“不撞南墙不回头”，它几乎不消耗额外的空间，是解决连通性问题和枚举全排列组合的最强武器。

53. 基础网格图 DFS (Flood Fill)

应用场景：求岛屿数量、封闭岛屿填充、最大连通块面积。

核心心法：一条路走到黑。越界或碰到海水立刻 return。

C++

void dfsGrid(int x, int y, vector<vector<int>>& grid, vector<vector<bool>>& vis) {
    // 1. 越界检查
    if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size()) return;
    // 2. 终止条件检查：已访问过，或者是海水 (0)
    if (vis[x][y] || grid[x][y] == 0) return;
    
    vis[x][y] = true; // 占领该土地
    
    for (int d = 0; d < 4; ++d) {
        dfsGrid(x + dx[d], y + dy[d], grid, vis);
    }
}

54. 显式栈 DFS (Iterative DFS)

应用场景：极端数据下的图/树遍历。当递归深度可能超过 $10^5$ 时，物理调用栈会爆栈 (Stack Overflow)。

核心心法：放弃系统的递归，手动开一个 std::stack。如果需要严格保持和递归 DFS 一模一样的遍历顺序，压栈时需要将子节点倒序压入。

C++

#include <stack>

void iterativeDFS(int start, vector<vector<int>>& adj) {
    vector<bool> vis(adj.size(), false);
    stack<int> st;
    st.push(start);
    
    while (!st.empty()) {
        int u = st.top(); 
        st.pop();
        
        if (vis[u]) continue; // 可能存在多次入栈，出栈时拦截
        vis[u] = true;
        
        // 此时正在处理节点 u...
        
        // 将未访问的邻居压入栈中
        for (int v : adj[u]) {
            if (!vis[v]) st.push(v);
        }
    }
}

55. 回溯法 (Backtracking)

核心心法：“试探 + 撤销”。无论是子集、组合还是排列，本质都是在遍历一棵决策树。进去的时候拿起物品，出来的时候放下物品（恢复现场）。

子集型（选或不选模型）

C++

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    
    function<void(int)> dfs = [&](int i) {
        if (i == nums.size()) { // 走到决策树叶子节点
            res.push_back(path);
            return;
        }
        // 岔路 1：不选当前数字，直接去下一个
        dfs(i + 1);
        
        // 岔路 2：选当前数字
        path.push_back(nums[i]);
        dfs(i + 1);
        path.pop_back(); // 撤销选择，恢复现场
    };
    dfs(0);
    return res;
}

组合型（选 K 个模型）

C++

void combineDFS(int start, int k, int n, vector<int>& path, vector<vector<int>>& res) {
    // 剪枝：如果剩下的数字全选上也不够 k 个，直接结束
    if (path.size() + (n - start + 1) < k) return; 
    
    if (path.size() == k) { 
        res.push_back(path); 
        return; 
    }
    
    for (int i = start; i <= n; ++i) {
        path.push_back(i);
        combineDFS(i + 1, k, n, path, res);
        path.pop_back();
    }
}

排列型（全排列模型）

C++

// 排列问题不用 start 变量，而是用 used 数组防重发
void permuteDFS(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
    if (path.size() == nums.size()) { 
        res.push_back(path); 
        return; 
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (used[i]) continue; // 用过的不能再用
        
        used[i] = true;
        path.push_back(nums[i]);
        
        permuteDFS(nums, used, path, res);
        
        path.pop_back();
        used[i] = false; // 必须恢复 used 状态
    }
}

战区三：搜索的终极进化 —— 记忆化与剪枝

纯粹的搜索面临的最致命问题就是超时 (TLE)。记忆化和剪枝是拯救指数级复杂度的两大灵丹妙药。

56. 记忆化搜索 (Memoization DFS)

应用场景：自顶向下的动态规划 (Top-down DP)。例如矩阵中的最长递增路径、带约束的找零问题。

核心心法：用 memo 数组记录算过的状态。在递归函数的第一行永远是查表：if (memo[state] != -1) return memo[state];。只要子问题重叠，直接强行降维。

C++

// 经典：矩阵中最长递增路径
int dfs(int i, int j, vector<vector<int>>& matrix, vector<vector<int>>& memo) {
    if (memo[i][j] != -1) return memo[i][j]; // 查表：算过直接交卷
    
    int best = 1; // 至少包含自己，长度为 1
    for (int d = 0; d < 4; ++d) {
        int ni = i + dx[d], nj = j + dy[d];
        // 只能往严格更大的格子走
        if (ni >= 0 && ni < matrix.size() && nj >= 0 && nj < matrix[0].size() 
            && matrix[ni][nj] > matrix[i][j]) {
            best = max(best, 1 + dfs(ni, nj, matrix, memo));
        }
    }
    return memo[i][j] = best; // 记录并返回
}

57. 高级剪枝技巧 (Pruning)

在回溯中，如果发现前方的路注定是死胡同或者不如已知的最优解，立刻停下，不要做无用功。

三大黄金剪枝原则：

可行性剪枝：当前状态已不可能满足约束（如剩余容量无法装下）。
最优性剪枝：当前花费已经 $\ge$ 已知最优解，立刻停止。
搜索顺序优化：极其重要！优先处理那些能让搜索树迅速变窄的选项。 比如组合求和前先将数组排序，数独中优先填备选数字最少的格子。

C++

// 经典：组合总和剪枝 (要求找出和为 remain 的所有组合)
void combinationSumDFS(vector<int>& cand, int idx, int remain, vector<int>& path, vector<vector<int>>& res) {
    if (remain < 0) return;               // 可行性剪枝
    if (remain == 0) { res.push_back(path); return; }
    
    for (int i = idx; i < cand.size(); ++i) {
        // ⚠️ 极其核心的排序后剪枝：
        // 如果当前数字已经大于 remain，因为数组已经【升序排列】，
        // 后面的数字肯定更大，绝无可能凑成 remain。直接 break 砍掉整片森林！
        if (cand[i] > remain) break;     
        
        path.push_back(cand[i]);
        combinationSumDFS(cand, i, remain - cand[i], path, res);
        path.pop_back();
    }
}

分享

一、 基础算法与技巧 (Basic Algorithms)

1. 浮点数二分 (Floating-point Binary Search)

核心代码模板

2. 三分查找 (Ternary Search)

核心代码模板

3. 双指针与滑动窗口 (Two Pointers & Sliding Window)

核心代码模板 1：相向双指针 (对撞指针)

核心代码模板 2：滑动窗口 (同向双指针)

场景 B：求最长的满足条件的子数组（例如：无重复字符的最长子串）

4. 滑动窗口的最值 (单调队列)

核心代码模板

5. 前缀和与差分 (Prefix Sum & Difference Array)

核心代码模板 1：一维与二维前缀和 (极速查询)

核心代码模板 2：一维与二维差分 (极速修改)

6. 离散化 (Discretization)

核心代码模板

7. 位运算子集枚举 (Bitwise Subset Enumeration)

核心代码模板 1：常规子集枚举 ($O(2^N)$)

核心代码模板 2：子集的子集枚举 ($O(3^N)$) —— 竞赛高级神技

二、 高级数据结构 (Advanced Data Structures)

8. 单调栈 (Monotonic Stack)

核心代码模板：正向遍历法 (推荐，适用性极强)

9. 并查集 (Disjoint Set Union, DSU)

核心代码模板：面向对象封装版 (竞赛与面试首选)

10. 树状数组 (Fenwick Tree / BIT)

核心代码模板：面向对象封装版

11.线段树 (Segment Tree) 附 Lazy Tag 懒标记

核心代码模板：面向对象封装版 (区间加法 + 区间求和)

12. ST 表 (Sparse Table)

核心代码模板：面向对象封装版 (以区间最大值为例)

13. 字典树 (Trie) 与 01-Trie

核心代码模板 1：经典字符串 Trie (数组静态分配法)

核心代码模板 2：01-Trie (降维打击异或最值问题)

三、 图论算法 (Graph Theory)

最短路系列：

14. Dijkstra (堆优化版)

核心代码模板：竞赛级邻接表 + priority_queue

15. SPFA (最短路快速算法 / 处理负权与判环)

核心代码模板：SPFA 单源最短路与负环检测

16.Floyd-Warshall (多源最短路)

核心代码模板：图论最美三重循环

最小生成树 (MST)：

17. 最小生成树 (Kruskal 算法)

核心代码模板：贪心排序 + 并查集

18. 拓扑排序 (Topological Sort - Kahn 算法)

核心代码模板：Kahn 算法 (基于 BFS 与入度表)

19.强连通分量与双连通分量 (Tarjan)：

20. 无向图：求割点 (Articulation Points) 和桥 (Bridges)

21. 染色法判定二分图 (Bipartite Graph Check)

核心代码模板：DFS 优雅染色

22. 匈牙利算法 (二分图最大匹配)

核心代码模板：基于 DFS 找增广路

四、 树上问题 (Tree Algorithms)

23. 树的直径 (Diameter of a Tree)

核心代码模板 1：两次 DFS/BFS 寻找法 (最符合直觉)

核心代码模板 2：树形 DP 法 (降维打击)

24. 树的重心 (Centroid of a Tree)

核心代码模板：一次 DFS 极限打擂

25. 最近公共祖先 (LCA) - 倍增法 (Binary Lifting)

核心代码模板：DFS 预处理 + 二进制对齐跳跃

26. 树链剖分 (Heavy-Light Decomposition)

核心代码模板：两次 DFS 与路径狂飙

五、 动态规划核心模型 (Dynamic Programming)

27. 01背包 (0/1 Knapsack)

28. 完全背包 (Unbounded Knapsack)

29. 多重背包 (Multiple Knapsack) – 二进制拆分优化

30. 最长递增子序列 (LIS) – 二分贪心模板

31. 最长公共子序列 (LCS)

32. 区间 DP – 石子合并问题

33. 状态压缩 DP – 旅行商问题 (TSP) 模板

34. 数位 DP (Digit DP) – 记忆化搜索模板

六、 数学与数论 (Mathematics & Number Theory)

35. 快速幂 (Binary Exponentiation)

36. 矩阵快速幂 (Matrix Exponentiation)

37. 素数筛法 – 埃氏筛与欧拉线性筛

38. 扩展欧几里得算法 (Extended Euclidean Algorithm)

39. 乘法逆元与模除法

40. 组合数取模 – 阶乘与逆元预处理

一、基础算法与技巧 (Basic Algorithms)

二、高级数据结构 (Advanced Data Structures)

三、图论算法 (Graph Theory)

四、树上问题 (Tree Algorithms)

五、动态规划核心模型 (Dynamic Programming)

六、数学与数论 (Mathematics & Number Theory)

七、字符串高级算法 (String Algorithms)

八、计算几何 (Computational Geometry)

九、搜索与回溯 (Search & Backtracking)