我发现我现在发文章越来越依靠ai了，这导致我自己的思想在文章当中的占比很少，这对我的成长也不是很好，所以我以后的文章会尽量的少使用ai，除非就是那种排版，以及图片之类的，总的内容还是要自己去输出。

bfs就是宽度优先搜索，用到队列来保持一个先入先出的结构，队列开的长度应该是边长的平方表示的是全部点的个数，存的是位置，所以可以是用pair<int, int> 来存，

其中用组数模拟队列的方法就是定义两个指针，hh、tt ,hh = 0, tt = -1,存入元素时，++tt ,表示向后退一格，弹出队头时hh++，表示同时退后一个元素，同时原来的索引就不用管了，为的是节约时间，但是可以浪费一点内存

这样是为了，在后面加入的元素时可以优先把前面先加入的元素进行宽搜，为了标记位置是否已经来过，需要一个bool二维数组来储存，同时用一个int类型的二维数组来储存每一个点是第几个经过的点，当这个点是终点时，也就是成了从初始点到终点的距离，所以显然，初始点的值为0，表示还没有开始走，也就是头节点。因为是对没有个节点进行标记，所以第一次到达终点时，就是最短的路径，因为有队列在保持后面相同同一层的点，假如某一点要再走两格才可以到达，但是第一个点，就是我们拿出来的头节点可以在下一次的遍历中就到达终点，并给终点上了个标记，所以很显然就是，这个第一次经过的终点距离是最短的。

用来模拟向四个方向走可以新建两个数组，表示偏移量，例如dx = {-1，0，1，0}，dy = {0，1，0，-1}，分别表示（-1，0）、（0，1）、（1，0）、（0，-1），即向上，向右，向下，向左
之后只要for循环4次，表示四个坐标，同时加上限制条件（边界或其他），如果满足条件，则那个点的路径数为前面的路径数 + 1，然后将其放到对列中

所以为了保持这个最短的性质，每次再加入队列之前先进行判断是不是已经经过了，如果已经经过了就没有必要再经过一遍，所以就不用加入队列，从而有了一个循环结束的标志，就是当队列中没有元素时，即没有新的元素加入，然后老元素也已经全部走完时，就是表示表格中的所有元素都被走过了，此时输出终点的路径数就是最短路径数

关于输入以及边界判断，如果主要是看题目，来看是从1开始还是从0开始。以及对应的终点的坐标是否要减1

关于如何输出路径，可以再新建一个类型为pair<int, int> 类型的二维数组pre，来存放每个点之前的坐标，然后在输出的时候，可以用一个while循环来表示，while(x || y) 表示当x或y有一个不为0时，循环就继续，即如果x和y都为0时循环就结束，在逻辑上就是起始点没有前一个点，然后在每次进行扩张的时候都将当前点的上一个存入pre。

思考：这个时候如果已经知道了终点的坐标，而且只有一个询问，是不是可以在当循环遍历到终点时就return，但是如果是有多组询问，或许应该就是要让他bfs跑完，这样的话每次查询的时间复杂度就是O(1)的了。

在算法竞赛中，堆常被用来处理需要动态维护最小值或最大值的操作。本文介绍一种基于最小堆的数据结构，支持插入、删除、修改和查询最小值的操作，并且针对每个插入操作进行编号，以便实现按插入顺序删除和修改的功能。

题目描述

我们需要维护一个集合，初始时集合为空，支持如下几种操作：

• I x，插入一个数 x；
• PM，输出当前集合中的最小值；
• DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
• D k，删除第 k 个插入的数；
• C k x，修改第 k 个插入的数，将其变为 x。

要求进行 N 次操作，并对于所有 PM 操作，输出当前集合的最小值。

输入格式

• 第一行包含整数 N；
• 接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。

输出格式

对于每个 PM 操作，输出当前集合的最小值，每个结果占一行。

数据范围

• 1 ≤ N ≤ 10^5
• -10^9 ≤ x ≤ 10^9
• 数据保证合法。

输入样例：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例：

-10
6

思路分析

为了在 O(log n) 时间内实现插入、删除和修改操作，同时支持按插入顺序的删除和修改，我们需要用到最小堆，并且引入两个额外的数组来维护插入顺序与堆中元素位置的映射关系。

核心数据结构

• h[]: 最小堆，存储实际的堆元素；
• ph[]: 插入元素编号到堆位置的映射，即第 k 个插入的元素当前在堆中的哪个位置；
• hp[]: 堆中元素的下标对应的插入编号，表示堆中第 i 个位置存储的是第 k 个插入的元素。

这两个数组互为反函数，即 ph[hp[i]] = i，hp[ph[k]] = k。

操作实现

1. 插入操作 I x：

   • 将新元素插入堆，并更新插入编号和堆中的位置。
   • 调用 up() 函数对堆进行上浮操作。

2. 输出最小值 PM：

   • 直接输出堆顶元素，即 h[1]。

3. 删除最小值 DM：

   • 将堆顶元素与堆末尾元素交换，然后删除堆末尾元素。
   • 调用 down() 函数对堆顶进行下沉操作。

4. 删除第 k 个插入的数 D k：

   • 找到第 k 个插入的元素在堆中的位置，进行删除操作。
   • 调用 down() 和 up() 函数对该位置进行调整。

5. 修改第 k 个插入的数 C k x：

   • 修改第 k 个插入的元素的值，并进行上下调整，保持堆的性质。

代码实现

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int h[N], s = 0, hp[N], ph[N]; // ph[]是对应编号元素的下标，hp[]是元素的插入编号，h[]是堆

void heap_swap(int x, int y)
{
    swap(ph[hp[x]], ph[hp[y]]);
    swap(hp[x], hp[y]);
    swap(h[x], h[y]);
}

void down(int x)
{
    int t = x;
    if (x * 2 <= s && h[x * 2] < h[t]) t = x * 2;
    if (x * 2 + 1 <= s && h[x * 2 + 1] < h[t]) t = x * 2 + 1;
    if (x != t)
    {
        heap_swap(x, t);
        down(t);
    }
}

void up(int x)
{
    while (x / 2 && h[x / 2] > h[x])
    {
        heap_swap(x / 2, x);
        x /= 2;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, x, m = 0; // m 表示第几个插入
    string op;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> op;
        if (op == "I")
        {
            cin >> x;
            h[++s] = x;
            hp[s] = ++m;
            ph[m] = s; 
            up(s);
        }
        else if (op == "PM")
        {
            cout << h[1] << '
';
        }
        else if (op == "DM")
        {
            h[1] = h[s--];
            down(1);
        }
        else if (op == "D")
        {
            cin >> k;
            heap_swap(ph[k], s--);
            down(ph[k]), up(ph[k]);
        }
        else if (op == "C")
        {
            cin >> k >> x;
            h[ph[k]] = x;
            down(ph[k]), up(ph[k]);
        }
    }
    return 0;
}

关键点说明

• heap_swap()：用于交换两个堆元素的位置，同时维护 ph[] 和 hp[] 的映射关系。
• down()：下沉操作，确保最小堆性质。若子节点比当前节点小，则将当前节点下沉。
• up()：上浮操作，确保最小堆性质。若父节点比当前节点大，则将当前节点上浮。
• ph[] 和 hp[] 的作用：这两个数组使得我们可以快速定位并删除或修改任意编号的元素，而无需遍历整个堆。

总结

通过最小堆结合 ph[] 和 hp[] 两个数组，我们能够高效地完成插入、删除、修改和查询最小值的操作。对于每个操作，插入、删除和修改的时间复杂度都是 O(log n)，而查询最小值的操作则为 O(1)。

这类问题广泛应用于需要动态维护有序集合的场景，比如优先队列、任务调度等。

在这篇文章中，我们将深入探讨两个常见的基础算法概念：递归 和 并查集。这两者在计算机算法中非常重要，理解它们的核心思想和应用场景将极大地帮助你解决许多常见的问题。

递归的核心思想

什么是递归？

递归是一种算法思想，它通过函数调用自身来实现重复操作。每次递归调用时，问题的规模都会逐步减小，直到满足特定的条件（基准条件，base case）来结束递归。

递归与循环的关系

很多人会将递归与 while 或 for 循环混淆，因为它们都用于实现某种形式的重复操作。实际上，递归可以看作是通过函数调用实现的循环结构。

递归通常使用 if 语句来检查递归的终止条件，而 while 则是基于显式的条件判断持续运行。递归与循环的本质区别在于，递归是通过函数的调用栈实现的，而循环是显式的控制流程。

递归的例子：斐波那契数列

int fibonacci(int n) {
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

在这个例子中，递归通过 if 语句检查基准条件（n == 0 和 n == 1），并在这些条件满足时返回结果。这避免了无限递归的发生。

递归的注意点

递归虽然直观，但如果不注意基准条件或者优化，可能会导致性能问题或栈溢出。常见的优化技巧包括尾递归和动态规划。

并查集简介

什么是并查集？

并查集是一种数据结构，主要用于处理动态连通性问题。它能够高效地管理并查找多个不相交集合，支持合并（union） 和 查找（find） 操作。

在并查集中，每个元素最初都是一个独立的集合，其集合的代表是元素的祖先节点（根节点）。通过两个优化手段——路径压缩 和 按秩合并，并查集能够以接近常数时间（几乎是 O(1)）的复杂度执行合并和查找操作。

并查集的基本操作

1. 查找（Find）：
   查找元素的祖先节点（根节点），根节点是集合的唯一标识符。
2. 合并（Union）：
   将两个集合合并，实际上是将一个集合的根节点连接到另一个集合的根节点上。

并查集的实现

并查集的实现非常简洁。每个元素的根节点作为其集合的标识。当需要合并两个集合时，首先找到它们的根节点，然后根据根节点是否相同来决定是否需要合并。

并查集的代码实现

class UnionFind {
public:
    UnionFind(int n) : parent(n), rank(n, 1) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    // 查找操作（带路径压缩）
    int find(int p) {
        if (parent[p] != p) {
            parent[p] = find(parent[p]);  // 路径压缩
        }
        return parent[p];
    }

    // 合并操作（按秩合并）
    void unionSets(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        if (rootP != rootQ) {
            if (rank[rootP] > rank[rootQ]) {
                parent[rootQ] = rootP;
            } else if (rank[rootP] < rank[rootQ]) {
                parent[rootP] = rootQ;
            } else {
                parent[rootQ] = rootP;
                ++rank[rootP];
            }
        }
    }

private:
    std::vector<int> parent;
    std::vector<int> rank;
};

在这个实现中，我们使用了路径压缩（find 函数中的递归调用）和按秩合并（unionSets 函数中的秩判断），这确保了查找和合并操作都能高效地执行。

并查集的应用场景

并查集广泛应用于解决以下问题：

• 组团问题：判断两个元素是否属于同一组。
• 连通性问题：在图论中判断节点是否连通。
• 动态连通性问题：如社交网络中的好友关系。

总结

• 递归 是通过函数调用自身并基于 if 语句来实现重复操作的算法，适用于问题规模可以递归分解的场景。
• 并查集 是一种高效的数据结构，主要用于处理动态连通性问题，通过根节点代表集合，并支持合并和查找操作。

通过掌握递归与并查集的基本原理和实现方式，你将能够解决许多常见的算法问题。

Trie 树，亦称前缀树，是一种高效处理字符串的基础数据结构。许多算法问题中，Trie 树因其能快速检索字符串的前缀匹配而备受青睐。

在本文中，我们将从 Trie 树的基本插入与查询操作出发，详解为何节点编号 p 不会被限制在 26 个以内。

1. Trie 树的基本结构

Trie 树通常用于处理一组字符串，每个节点代表一个前缀。Trie 树的每个节点最多有 26 个子节点，分别对应小写字母 a 到 z。

插入操作

以下是 Trie 树的典型插入代码：

void insert(char str[])  
{  
    int p = 0;  // 从根节点开始遍历  
    for (int i = 0; str[i]; i++) // 沿着字符串的每个字符进行遍历  
    {  
        int j = str[i] - 'a';  // 将字符映射为 0 ~ 25 的整数  
        if (!son[p][j]) son[p][j] = ++idx;  // 如果该子节点不存在，则创建新节点  
        p = son[p][j];  // 移动到下一个节点  
    }  
    cnt[p]++;  // 记录该字符串出现的次数  
}

在上述代码中，p 代表当前遍历到的节点编号，而 j = str[i] - 'a' 则将字符映射为相应的索引值，范围为 0 到 25，分别对应 a 到 z 的 26 个字母。

查询操作

查询一个字符串是否存在于 Trie 树中的代码如下：

bool search(char str[])  
{  
    int p = 0;  // 从根节点开始  
    for (int i = 0; str[i]; i++)  // 遍历字符串的每个字符  
    {  
        int j = str[i] - 'a';  // 计算字符的索引  
        if (!son[p][j]) return 0;  
        p = son[p][j];  // 移动到下一个节点  
    }  
    return cnt[p];  
}

p 是节点编号，不是字符索引

p 是 Trie 树中节点的编号，它表示当前遍历到的节点。虽然每个节点最多有 26 个子节点（对应字母 a 到 z），但 p 的值会随着 Trie 树的扩展而不断增加。p 代表的是节点编号，而不是字符范围。

2. 为什么 p 不会被限制在 26？

很多人可能疑惑，既然每个节点最多有 26 个子节点（分别对应字母 a 到 z），那么为什么 p 的值不会被限制在 26 个以内呢？

关键在于节点数量的动态扩展

Trie 树的每个节点最多有 26 个分支，但节点的总数却不限于 26。不同字符串的前缀可能会产生不同的节点，因此节点数量会根据插入的字符串的数量和内容动态增长。每当插入一个新字符串，如果某个字符的节点不存在，都会创建一个新的节点，并分配一个新的编号。

例如：

• 插入字符串 "apple" 时，p 将沿着字符路径 "a" -> "p" -> "p" -> "l" -> "e" 移动，并为每个新字符创建一个新节点。
• 每创建一个新节点时，节点编号 p 会递增，而不仅仅是 0 到 25 之间的固定值。
• 因此，随着插入字符串数量的增加，Trie 树中的节点数量可以轻松超过 26，p 也会相应地增大。

3. Trie 树节点扩展的示例

假设我们插入三个不同的字符串："apple"、"app" 和 "bat"。Trie 树的扩展情况如下：

1. 插入 "apple"：

   • a -> 新建节点（编号 1）
   • p -> 新建节点（编号 2）
   • p -> 新建节点（编号 3）
   • l -> 新建节点（编号 4）
   • e -> 新建节点（编号 5）

2. 插入 "app"：

   • 由于 "app" 与 "apple" 共享前缀 "app"，只需沿着现有节点移动即可，不创建新节点。

3. 插入 "bat"：

   • b -> 新建节点（编号 6）
   • a -> 新建节点（编号 7）
   • t -> 新建节点（编号 8）

最终，节点 p 的最大编号会达到 8，而不是 26。这是因为每插入一个新字符串，都会动态扩展树的节点数量。

4. 总结

通过对 Trie 树插入和查询操作的讲解，我们可以得出以下结论：

• 节点编号 p 表示当前遍历的节点，不是字符索引。
• 节点数量根据插入的字符串数量动态增长，虽然每个节点的子节点数目被限制为 26，但节点的总数是根据需要不断扩展的，因此节点编号 p 也会随之增长。
• Trie 树是一种高效的字符串存储和检索结构，非常适合前缀匹配和大规模字符串数据处理场景。

如果你在学习算法的过程中遇到类似的疑问或困惑，不妨从基础概念入手，逐步理解数据结构的设计原理。Trie 树作为一个经典的算法问题，值得深入理解与应用。