算法基础课(持续更新中)

发表于 2025-02-14 更新于 2026-04-01 分类于算法题阅读次数：

| 置顶

本文字数： 438k 阅读时长 ≈ 13:17

算法基础课

[toc]

基础算法（一）

快速排序

1.很久没刷算法题后重新开始刷，发现了容易遗忘的一些点：

（1）const int N=多少是依据题目给出的范围去推断，比如这里快排题要求数组中数字范围是1-100000，那就写成1-100010（多开10防止爆数组），然后再接上对数组的定义int q[N]，这样就可以保证开的数组位置是一定管够的。

（2）对于这种功能是处理xxx的函数通常定义为void。

（3）写代码时可以先把int main也就是有关输入、函数调用和输出的部分先写好，再去写具体函数的内容，这样可以减轻处理题目的逻辑容量。

（4）函数定义中参数写 int q[]，而在 main 函数调用时只写 q：在 C++ 中，数组名 q 本质上是数组首元素的地址。在函数定义时，int q[] 仅是语法上的声明，表示该参数接收一个数组地址（等价于指针 int *q）；而在调用函数时，直接写 q 即可将该地址传入。这种按址传递的方式避免了复制整个数组的巨大开销，并允许函数直接修改原数组的数据。

2.关于quick_sort与分治：

（1）分治通常就是按下面这种形式写：

void function(xxx)
{
    //1.处理边界
    if(边界条件)return xxx;//比如这里就是不能使左边界大于右边界所以直接return
    
    //3.写具体处理逻辑
    xxx;
    
    //2.写递归调用
    function(xxx);
    function(xxx);
}

（2）quick_sort具体处理逻辑部分

int x=q[(l+r)>>1],i=l-1,j=r+1;//定义分界点pivot以及左右指针，-1/+1是因为每一次对i/j循环时都会先++/--

while(i<j)
{
    do(i++);while(q[i]<x);
    do(j++);while(q[j]>x);
    if(i<j)
        swap(q[i],q[j]);//这一步是指在i<j的前提下当i/j的俩while循环都无法继续工作，说明此时指向的数字分别都不是对应序列的数字，就需要交换位置来使该位置数字回到正确序列中；然后再重新while循环
}

3.完整代码

#include<iostream>

using namespace std;

const int N=1e5+10;

int q[N];

void quick_sort(int q[],int l,int r)
{
    if (l>=r)return;
    int x=q[(l+r)>>1],i=l-1,j=r+1;
    
    while(i<j)
    {
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j)
            swap(q[i],q[j]);
    }
    
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&q[i]);
    }
    quick_sort(q,0,n-1);
    for(int i=0;i<n;i++)
    {
        printf("%d ",q[i]);
    }
    return 0;
}

归并排序

1.为什么快排是先处理再递归，而归并是先递归再处理？

归并排序采用的是“后序遍历”思想，必须先通过递归把数组切分到不能再分的单元素状态（此时自然有序），然后在回溯阶段才能将这些有序子序列合并；而快排采用的是“先序遍历”思想，先通过分区逻辑确定一个基准点的位置，再据此划分区间继续向下递归。

2.为什么归并处理边界时必须使用小于等于号？

因为在归并排序的代码逻辑中，mid 和 r 都是闭区间内真实存在的合法下标，如果不加等号，循环就会在处理到最后一个元素之前提前跳出，导致区间边界上的那个数据被遗漏在排序过程之外。如题目要求合并两个只有 1 个元素的区间，左边是 q[0]（此时 mid=0），右边是 q[1]（此时 r=1）。如果你写 i < mid（即 0 < 0），判断条件立刻失效，循环一次都不会执行，这两个数就永远没法被装进结果数组 tmp 里。

3.完整代码

#include<iostream>

using namespace std;

const int N=1e5+10;

int q[N],tmp[N];

void merge_sort(int q[],int l,int r)
{
    //1.处理边界
    if(l>=r)return;
    
    
    int mid=(l+r)>>1,i=l,j=mid+1,k=0;
    //2.递归调用归并（和快排不一样）
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);
    
    //3.具体归并逻辑
    while(i<=mid&&j<=r)
    {
        if(q[i]<q[j])tmp[k++]=q[i++];
        else tmp[k++]=q[j++];
    }
    
    while(i<=mid)tmp[k++]=q[i++];
    while(j<=r)tmp[k++]=q[j++];
    
    for(int i=l,j=0;i<=r;i++,j++)
        q[i]=tmp[j];
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&q[i]);
    }
    merge_sort(q,0,n-1);
    for(int i=0;i<n;i++)
        printf("%d ",q[i]);
    return 0;
}

4.板子

void merge_sort(int q[],int l,int r)
{
    if(l>=r)return;

    int mid=l+r>>1;

    merge_sort(q,l,mid),merge_sort(q,mid+1,r)；

        int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)
        if(q[i]<=q[j])tmp[k++]=q[i++];
    else tmp[k++]=q[j++];
    while(i<=mid)tmp[k++]=q[i++];
    while(j<=r)tmp[k++]=q[j++];

    for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
}

5.用归并排序求逆序对

（1）为什么用 long long 而不直接用 int

因为在 $10^{5}$ 的数据规模下，最坏情况（如数组完全逆序）产生的逆序对数量约为 $\frac{n (n - 1)}{2} \approx 5 \times 10^{9}$ ，这已经超过了 int 类型约 $2 \times 10^{9}$ 的最大承载极限。

（2）为什么 res += mid - i + 1

可以理解为merge_sort在执行具体操作之前就已经是一个划分成单个数字组成的有序数列。此时左半区间是有序的，一旦发现 $q [i] > q [j]$ ，就意味着从 $q [i]$ 到 $q [m i d]$ 的所有元素（一共 $m i d - i + 1$ 个）都必然比 $q [j]$ 大，因此 $q [j]$ 与这一整段都能构成逆序对。

#include<iostream>

using namespace std;

const int N=1e5+10;

int q[N],tmp[N];

long long merge_sort(int q[],int l,int r)
{
    if(l>=r) return 0;
    
    int mid=(l+r)>>1,i=l,j=mid+1,k=0;
    
    long long res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);//相当于把merge sort改造成输出是数字，然后在
    
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j])tmp[k++]=q[i++];
        else 
        {
            res+=mid-i+1;
            tmp[k++]=q[j++];
        }
    }
    
    while(i<=mid)tmp[k++]=q[i++];
    while(j<=r)tmp[k++]=q[j++];
    
    for(int i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
    
    return res;
}


int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&q[i]);
    printf("%lld",merge_sort(q,0,n-1));
    return 0;
}

二分

整数二分

1.思路

（1）整体思路就是先考虑数组中位数值q[mid]>k再考虑q[mid]<k的判断，据此不停变换左右边界l/r的取值，最终收束得到k的左右边界取值，输出时均以左边界l为取值；

（2）需要注意的是边界一旦涉及mid-1的操作时取mid=(l+r+1)>>1要有这个＋1，不然-1之后mid无法更新就会死循环；此外在跑完k的左边界并输出l后要记得更新l=0,r=n-1这个操作重新计算，不然此时数组边界已经收束就无法再计算k的右边界。

2.题目：789. 数的范围 - AcWing题库

#include<iostream>

using namespace std;

const int N=1e5+10;

int q[N];

int main()
{
    int n,m,k;
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    while(m--)
    {
        scanf("%d",&k);
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(q[mid]<k)l=mid+1;
            else r=mid;
        }
        if(q[l]!=k)printf("-1 -1\n");
        else
        {
            printf("%d ",l);
            int l=0,r=n-1;
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(q[mid]>k)r=mid-1;
                else l=mid;
            }
            printf("%d\n",l);
            
        }
        
    }
    
    
    return 0;
    
}

3.板子

bool check(int x) {/* ... */} // 检查x是否满足某种性质
    
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分

1.思路

先看题目保留n位小数，那么精度就要对应是n+2位小数（比如保留六位小数那么范围就是1e-8）；然后取一个必定包含取值范围的左右边界初始值，然后正常取中点计算即可。

2.题目：790. 数的三次方根 - AcWing题库

#include<iostream>
using namespace std;

int main()
{
    double n;
    cin>>n;
    double l=-100,r=100;
    while(r-l>1e-8)
    {
        double mid=(l+r)/2;
        if(mid*mid*mid>n)r=mid;
        else l=mid;
    }
    printf("%.6lf",l);
    
    return 0;
}

3.板子

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

基础算法（二）

高精度

高精度加法

本质上是模拟人进行列竖式加法的过程，即 $a_{1}$ +…+ $a_{n}$ +t，其中当 $a$ 的退一位加起来不超过10则 $t = 0$ 否则 $t = 1$ ，以此类推

1.思路

（1）先加低位还是高位？

先加低位（个位）。在 main 函数里用 for(int i=a.size()-1;i>=0;i--) 把字符串反向存入了 vector，所以 A[0] 存的是个位，A[1] 存的是十位。

（2）为什么在C.push_back(t%10);用 push_back 而不是 C[i]？

因为 C 刚创建时是空的，根本没有下标 i。 在 C++ 中，vector<int> C; 初始长度为 0。如果写 C[i] = ...，程序会因为访问越界而崩溃。push_back 的作用是“动态扩容”，它会在数组末尾新开辟一个空间并把数放进去。

（3）push_back 和 size() 的适用范围

push_back： 适用于动态序列容器，最常用的是 vector、string 和 deque。

size()： 适用于几乎所有 STL 容器。包括 vector、string、list、map、set 等。

2.题目：791. 高精度加法 - AcWing题库

#include<iostream>
#include<vector>

using namespace std;

vector<int>add(vector<int>&A,vector<int>&B)
{
    vector<int>C;
    int t=0;//存储每一位相加后的数，同时完成是否需要进位的考量
    
    for(int i=0;i<A.size()||i<B.size();i++)
    {
        if(i<A.size())t+=A[i];
        if(i<B.size())t+=B[i];
        C.push_back(t%10);
        t/=10;
	}    
    if(t)C.push_back(1);//最后一个t代表最高位，因此等for循环运行完后再用判断看看进位情况，是的话就在vector后面再加一个1
    return C;
}

int main()
{
    string a,b;
    vector<int>A,B;
    cin>>a>>b;
    
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
//A、B元素进栈都是逆序进栈，比如a='123456',那A=[6.5,4,3,2,1],目的是方便进位多了1的时候整体数组挪动空间不大，否则要是最高位在前边ta进位后面数组所有数字都要往后挪
    
    auto C=add(A,B);
    for(int i=C.size()-1;i>=0;i--)cout<<C[i];
    return 0;
}

高精度减法

1.思路

（1）输入的处理逻辑整体与高精度加法一致，变化的在于①需要判别A和B谁大②需要处理前导0（把有效数字外高位的没用的0全部扔掉）

（2）对于判别大小的函数cmp而言，首先比较二者位数，位数大者自然大；其次位数相同的情况下，从高位依次比较具体位数的数值，数值大者自然大；最后一样大了就返回一个true；cmp返回比较时就是返回的布尔值（成立为1不成立就是0，转过弯就行）

（3）判定循环是i=A.size()-1;i>=0;i--还是i=o;i<A.size();i++取决于是从高位还是从低位算起；因为读入时采取了i=a.size()-1;i>=0;i--，则此时vector中A[0]代表低位A[n-1]代表高位，因此cmp的比较中还是要从高位算起，因此i=A.size()-1;...

（4）由于cmp已经隐含A＞B，因此我们默认A位数更大，外层循环管A.size()而里面再用个B.size()管。

2.题目：792. 高精度减法 - AcWing题库

#include<iostream>
#include<vector>

using namespace std;

bool cmp(vector<int> &A,vector<int> &B)
{
    if(A.size()!=B.size())return A.size()>B.size();
    else
    {
        for(int i=A.size()-1;i>=0;i--)
        {
            if(A[i]!=B[i])return A[i]>B[i];
        }
    }
    
    return true;
}

vector<int> sub(vector<int> &A,vector<int> &B)
{
    vector<int> C;
    
    for(int i=0,t=0;i<A.size();i++)
    {
        t=A[i]-t;
        if(i<B.size())t-=B[i];
        C.push_back((t+10)%10);
        if(t<0)t=1;
        else t=0;
    }
    
    while(C.size()>1&&C.back()==0)C.pop_back();
    
    return C;
}

int main()
{
    string a,b;
    vector<int> A,B;
    cin>>a>>b;
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
    
    vector<int> C;
    if(cmp(A,B))C=sub(A,B);
    else C=sub(B,A),printf("-");
    
    for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);
    
    return 0;
}

高精度乘法

1.思路

处理逻辑不难，和加减法差不多

2.题目：793. 高精度乘法 - AcWing题库

#include<iostream>
#include<vector>


using namespace std;

vector<int> mul(vector<int> A,int b)
{
    vector<int> C;
    int t=0;
    
    for(int i=0;i<A.size();i++)
    {
        t+=A[i]*b;
        C.push_back(t%10);
        t/=10;
    }
    
    if(t!=0)C.push_back(t);
    while(C.size()>1&&C.back()==0)C.pop_back();
    
    return C;
}

int main()
{
    string a;
    int b;
    cin>>a>>b;
    vector<int> A;
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    auto C = mul(A,b);
    for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);
    
    return 0;
}

高精度除法

1.思路

整体和乘法比较像，但是有三个注意的点：

（1）题目要求输出余数r，因此在写自定义函数的时候一定要记得加引用符&

（2）输出结果对应的是整除，输出余数对应的是取余；由于除法在处理时（也就是div函数内部）和加减乘都不一样，他还是倒序读数，因此最后得reverse把结果再反过来。这么麻烦的目的是使得题目同时高精度加减乘除时都统一；该做的前序0去除也是得有

（3）对于除法，除的交互对象变为b而不是10

2.题目：794. 高精度除法 - AcWing题库

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

using namespace std;

vector<int> div(vector<int> A,int b,int &r) //要记得加引用，不然参数改变了传不回去
{
    vector<int> C;
    r=0;
    for(int i=A.size()-1;i>=0;i--)
    {
        r=r*10+A[i];
        C.push_back(r/b);
        r%=b;
    }
    
    reverse(C.begin(),C.end());
    
    while(C.size()>1&&C.back()==0)C.pop_back();
    
    return C;
}


int main()
{
    string a;
    int b;
    cin>>a>>b;
    vector<int> A;
    for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
    int r;
    auto C=div(A,b,r);
    for(int i=C.size()-1;i>=0;i--)cout<<C[i];
    cout<<endl<<r;
    
    return 0;
}

前缀和与差分

一维前缀和

1.思路

（1）一维前缀和 $s [i] = a [1] + . . . + a [n]$ ，因此读入 $a [i]$ 后可以有 $s [i] = s [i - 1] + a [i]$ ，那么要求指定区间的前缀和就记得要把左边界囊括上，也即s[r]-s[l-1]即可。

（2）需要注意的是对于前缀和与差分，都默认i/j=1;i<=n;i/j++而不是从0开始，原因是数组默认初始时所有值都是零也就是a[0]/a[0][0]=0（以及后面的），而前缀和表达式是从1开始的，（给定a[0]/a[0][0]=0后）则数组也要相应的从1开始（差分则是对前缀和在某一段添加固定值时的效率提升，可以理解为在特定情况下对前缀和的改进，也就是基于前缀和，那么自然是也遵循这个设定）。

2.题目：795. 前缀和 - AcWing题库

#include<iostream>

using namespace std;

const int N=1e5+10;

int s[N],a[N];

int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    while(m--)
    {
        int l,r;
        scanf("%d %d",&l,&r);
        printf("%d\n",s[r]-s[l-1]);
    }
    
    return 0;
    
}

二维前缀和

1.思路

做二维题关键就是理清楚数组取值与其相邻两格的取值关系（要在脑子里形成一个网格状的图）。

首先是弄清楚前缀和与具体取值在二维中的表示，就可以在脑中快速形成关系：

s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1](多减了一个就补上)+a[i][j](当前取值)

转换为求和之后就可以快速得到特定区间的求和范围及对应求法（如下图所示）：（b[][]就是s[][]，多在脑中过几遍就会想的更快）

2.题目：796. 子矩阵的和 - AcWing题库

#include<iostream>

using namespace std;

const int N=1010;

int a[N][N],s[N][N];

int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
            
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)            
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];

    while(q--)
    {
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]<<endl;
    }
    
    return 0;
}

一维差分

1.思路

上文提到，差分的本质就是对前缀和的某种改进（明确一点，差分刻画了前缀和的增长量），因此会有b[i]=a[i]-a[i-1]），希望对原数组中的部分区间加一个固定值c；因此直观地可以把差分理解为把原输出a[i]转换成用b[i]表示并对b[i]进行运算后再转换回a[i]输出；因此转换与输出应当互为相反，因此有转换b[i]=a[i]-a[i-1]; ，输出a[i]=a[i-1]+b[i]（二维亦是如此）；这个过程中当b[i]加了c，则a[n]=b[1]+…+b[i]+…+b[n]也就都加了c，但我们只希望特定区间(l,r)加c，因此对于r+1外的b数组就要减回c。

2.题目：797. 差分 - AcWing题库

#include<iostream>

using namespace std;

const int N=1e5+10;

int a[N],b[N];

void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i]-a[i-1];    
    }

    while(m--)
    {
        int l,r,c;
        cin>>l>>r>>c;
        insert(l,r,c);
    }
    
    for(int i=1;i<=n;i++)
    {
        a[i]=a[i-1]+b[i];
        printf("%d ",a[i]);
    }
    
    return 0;
}

二维差分

1.思路

（1）思路其实就揉合了前面差分的定义 $b [i] = a [i] - a [i - 1]$ 和二位前缀和的思想，那么在二维差分中前缀和a[i][j]与a[i-1][j-1]的增长量不等于简单的 $a [i] [j] - a [i - 1] [j - 1]$ ，而是包括a[i][j]与[i-1][j-1]围起来的所有格子，因此正确表示形式是b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]

（2）总结起来，网格图中前缀和考虑的是（x1,y1）前面的部分，差分考虑的是（x2,y2）后面的部分，这么想就会发现区别了

2.题目：798. 差分矩阵 - AcWing题库

#include<iostream>

using namespace std;

const int N=1e3+10;

int a[N][N],b[N][N];

void insert(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}

int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
        }
    
    while(q--)
    {
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        insert(x1,y1,x2,y2,c);
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
            printf("%d ",a[i][j]);
        }
        cout<<endl;
                
    }

    
    return 0;
}

基础算法（三）

双指针算法

1.思路

使用双指针是降低算法复杂度的一个有效途径，对于原本采用暴力嵌套循环，时间复杂度为 $O (n^{2})$ 的代码来说可以简化为 $O (n)$ ：

//暴力解法
for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {
        if(check(j,i))
            res=max(res,i-j+1);
    }
//双指针算法
for(int i=0,j=0;i<=n;i++)
{
    while(j<=i&&check(j,i))j++;
    res=max(res,i-j+1);
}

void check(...){}

（1）对于最长连续不重复子序列：

数组a表示正常数据内容，s表示a的计数器；s[a[i]]++就是对数值为a[i]的这个数出现次数进行计数；j和i分别代表当前最长连续不重复序列的左边界和右边界，当保证左边界始终不超过右边界且发现某个数值a[i]出现次数大于一次也即s[a[i]]>1时，触发s[a[j]]--：含义是将a[j]的出现次数减一，更直观的解释是把重复的数（中的一个，而对于初始数字也就是s[a[0]]来说就是这个数不可能是左边界了，它就变成0）移出当前最长连续不重复序列的观察窗口，否则就会使得while(j<i&&s[a[i]]>1)重复执行。

（2）对于数组元素的目标和：

①假设输入如下：数组 a = [1, 2, 4, 7] (长度 $n = 4$ )；数组 b = [3, 4, 6, 8] (长度 $m = 4$ )；目标值 x = 6

初始状态： i = 0 (指向 $a [0] = 1$ ), j = 3 (指向 $b [3] = 8$ )

| 步骤 | 指针位置 | 当前值 | a[i]+b[j] | 逻辑判断 | 动作 |
| ---- | -------- | -------------- | --------- | -------- | -------------------- |
| 1 | i=0, j=3 | a[0]=1, b[3]=8 | 9 | 9 > 6 | j 左移 (j=3 → 2) |
| 2 | i=0, j=2 | a[0]=1, b[2]=6 | 7 | 7 > 6 | j 左移 (j=2 → 1) |
| 3 | i=0, j=1 | a[0]=1, b[1]=4 | 5 | 5 ≯ 6 | 跳出 while，执行 if |
| 4 | i=0, j=1 | a[0]=1, b[1]=4 | 5 | 5 ≠ 6 | 进入下一轮 for (i=1) |
| 5 | i=1, j=1 | a[1]=2, b[1]=4 | 6 | 6 ≯ 6 | 跳出 while |
| 6 | i=1, j=1 | a[1]=2, b[1]=4 | 6 | 6 = 6 | 匹配成功！输出 1 1 |

②为什么是相向双指针？如何想到？

核心逻辑：单调性（Monotonicity）双指针算法的本质是利用问题的单调性来规避掉不必要的搜索空间。

同向双指针（如滑动窗口）： 通常用于处理“连续子数组”问题。当 $i, j$ 同向移动时，窗口内的元素和通常是随着 $j$ 增大而增大，随着 $i$ 增大而减小。

相向双指针（本题）：如果 $i$ 变大， $a [i]$ 变大，总和 $↑$ ；如果 $j$ 变大， $b [j]$ 变大，总和 $↑$ 。如果 $i$ 和 $j$ 都从 $0$ 开始，当 $a [i] + b [j] < x$ 时就需要增大总和，此时 $i$ 增大或 $j$ 增大都能实现无法确定该动哪一个。这导致必须尝试所有组合，退化回 $O (n \times m)$ 的暴力破解。只有相向而行才能做到“随着xxxx而增大，随着xxxx而减小。”

（3）对于判断子序列：

该算法利用双指针同步扫描，通过不断移动 $b$ 数组指针 $j$ 来在序列中按顺序寻找与 $a$ 数组当前元素 $a [i]$ 相等的项，只有匹配成功时才移动 $i$ ，最终通过判断 $i$ 是否走完整个 $a$ 数组来确定 $a$ 是否为 $b$ 的子序列。

2.题目

（1）799. 最长连续不重复子序列 - AcWing题库

#include<iostream>

using namespace std;

const int N=100010;

int a[N],s[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    int res=0;
    
    
    for(int i=0,j=0;i<n;i++)
    {
        s[a[i]]++;
        while(j<i&&s[a[i]]>1)
        {
            s[a[j]]--;
            j++;
        }
        res=max(res,i-j+1);
    }
    
    cout<<res<<endl;
    
    return 0;
}

（2）800. 数组元素的目标和 - AcWing题库

#include<iostream>
using namespace std;

const int N=100010;

int a[N],b[N];

int main()
{
    int n,m,x;
    cin>>n>>m>>x;
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    for(int i=0;i<m;i++)scanf("%d",&b[i]);
    
    for(int i=0,j=m-1;i<n;i++)
    {
        while(j>=0&&a[i]+b[j]>x)
        {
            j--;
        }
        
        if(a[i]+b[j]==x)
        {
            cout<<i<<" "<<j;
            break;
        }
    }
    
    return 0;
}

（3）2816. 判断子序列 - AcWing题库

#include<iostream>

using namespace std;

const int N=100010;

int a[N],b[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<m;i++)cin>>b[i];
    
    int i=0,j=0;
    
    while(i<n&&j<m)
    {
        if(a[i]==b[j])i++,j++;
        else j++;
    }
    
    if(i==n)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    
    return 0;
}

位运算

1.知识点

（1）lowbit(x)：提取最低位的 1。lowbit 利用计算机中补码的特性，通过 x & -x 得到 $x$ 在二进制下最低位的 1 及其后连带的 0所代表的数值。本质上， $- x$ 等于 ~x + 1（反码加 1），这会导致 $x$ 最低位的 1 与其左边的所有位全部取反，而该 1 及其右边的 0 保持不变，二者按位与后，除最低位的 1 被保留外，其余位全部变为 0。

（2）x >> n & 1：获取第 $n$ 位的值。该操作用于查询整数 $x$ 在二进制表示下第 $n$ 位（从右往左数，从 0 开始）是 0 还是 1。逻辑上分为两步：首先通过右移操作 x >> n 将目标位移动到最低位（第 0 位），然后与 1（二进制为 ...0001）进行按位与运算，从而屏蔽掉目标位左侧的所有干扰，直接提取出该位的值（结果仅为 0 或 1）。

2.题目：801. 二进制中1的个数 - AcWing题库

#include<iostream>
using namespace std;

const int N=100010;

int a[N];

int lowbit(int x)
{
    return x&(-x);
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int x;
        cin>>x;
        
        int res=0;
        while(x)x-=lowbit(x),res++;
        cout<<res<<" ";
    }
    
    return 0;
    
}

离散化

1.思路

（1）什么是离散化？为什么要叫这个名字？

原本的坐标轴是“连续”的（或者范围巨大到接近连续），但我们只关心其中散落的、离散的几个点。我们将这些“散落的点”提取出来，压进一个连续的数组里。虽然结果变连续了，但过程是处理离散点，所以叫离散化。

（2）为什么这道题要用离散化？

①空间塞不下： 坐标范围是 $[- 10^{9}, 10^{9}]$ 。如果开一个 int a[2000000000] 的数组，那么电脑内存直接爆掉（需要约 8GB 内存，而题目通常只给 64MB）。

②实际有用点很少： 虽然坐标大，但操作只有 $N$ 次（加数）和 $M$ 次（询问）。涉及到的坐标最多只有 $N + 2 M$ 个（约 $3 \times 10^{5}$ ）。这个数字很小，完全可以存进内存。

（3）什么是pair?vector<PII>是啥意思？

在 C++ 中，pair 是一个可以把两个不同类型（或相同类型）的值捆绑在一起的结构。

①成员名固定：盒子的第一个格叫 first，第二个格叫 second。

②写法：pair<类型1, 类型2> 变量名;

PII 是别名（typedef pair<int, int> PII;），因为 pair<int, int> 写起来太长；vector<PII> 是由一对对整数组成的动态数组。形象比喻是，int：一个独居的人；PII：一对同居的室友；vector<int>：一排单人间宿舍；vector<PII>：一排双人间宿舍。

（4）处理思路

①记录需求：把所有坐标 $x, l, r$ 全部存起来。

②排队领号：把这些坐标从小到大排好，去掉重复的。每个坐标对应的“排队序号”就是它的新名字。

③映射数据：把原本在巨大坐标 $x$ 上的值，搬到新数组 a[序号] 里。

④前缀和：在 a 数组上做一遍前缀和。

⑤回答问题：把查询的 $l, r$ 翻译成“序号”，然后用前缀和公式 $s [右序号] - s [左序号 - 1]$ 。

2.题目：802. 区间和 - AcWing题库

（1）输入处理：

3 3        <-- n=3 (加数操作次数), m=3 (询问次数)
1 2        <-- 第1个add：在坐标 x=1 处，加 c=2
3 6        <-- 第2个add：在坐标 x=3 处，加 c=6
7 5        <-- 第3个add：在坐标 x=7 处，加 c=5
1 3        <-- 第1个query：询问区间 [1, 3] 的和
4 6        <-- 第2个query：询问区间 [4, 6] 的和
7 8        <-- 第3个query：询问区间 [7, 8] 的和

此时代码在做什么：

把这 3 对 (x, c) 存进 vector<PII> add（存加了数的数字的位置，以及加数）。
把这 3 对 (l, r) 存进 vector<PII> query（存要求前缀和的左右边界）。
把所有的坐标 1, 3, 7 (来自add) 和 1, 3, 4, 6, 7, 8 (来自query) 全部一股脑塞进 alls。

此时 alls 的状态： [1, 3, 7, 1, 3, 4, 6, 7, 8]

（2）离散化：

sort(alls.begin(), alls.end()) 和 unique(...)。

①排序：alls 变成 [1, 1, 3, 3, 4, 6, 7, 7, 8]。

②去重：alls 变成 [1, 3, 4, 6, 7, 8]（此时该数对应的位置就隐含在数组的位置中，不再是一个pair了）。

③处理 add 里的加数操作：先用find()函数返回r+1也就是前缀和中待加数的位置（前缀和从1开始算），然后把这个数加进去。

（4）算前缀和并返回对应值：

前缀和代码就是s[i]=s[i-1]+a[i]，返回求和值（区间值）就是s[r]-s[l-1]

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

using namespace std;

// PII 是 pair<int, int> 的别名，用来存一对数
typedef pair<int, int> PII;

// 为什么是 300010？因为 n 次加数 + m 次询问(l和r)，坐标最多 10w + 20w = 30w 个
const int N = 300010;

int n, m;
int a[N], s[N]; // a 是离散化后的数组，s 是前缀和数组

vector<int> alls; // 存储所有要用到的坐标
vector<PII> add, query; // 存储操作和询问, add是 {坐标, 加的值}, query是{左边界, 右边界}

// 二分查找：输入一个超大坐标 x，返回它在 alls 数组里的下标（即离散化后的编号）
int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid; // 找第一个大于等于 x 的位置
        else l = mid + 1;
    }
    return r + 1; // 返回从 1 开始的编号，方便后面算前缀和
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c}); // 记录在 x 处加 c
        alls.push_back(x);     // 坐标 x 需要被离散化
    }

    for (int i = 0; i < m; i ++ )
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r}); // 记录询问区间 [l, r]
        alls.push_back(l);       // 坐标 l 需要被离散化
        alls.push_back(r);       // 坐标 r 需要被离散化
    }

    // --- 核心步骤：排序 + 去重 ---
    sort(alls.begin(), alls.end());
    // unique 把重复的数挪到最后，并返回重复序列的起始位置
    // erase 把后面重复的那一段彻底删掉
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    // --- 执行加数操作 ---
    // auto item : add 是 C++11 语法，意为“遍历 add 里的每一个 PII”
    // item.first 是坐标，item.second 是加的值
    for (auto item : add)
    {
        int x = find(item.first); // 把超大坐标变成小编号
        a[x] += item.second;      // 在小编号位置加值
    }

    // --- 算出离散化后数组的前缀和 ---
    for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];

    // --- 执行查询操作 ---
    for (auto item : query)
    {
        // 把查询的超大左、右边界也变成小编号
        int l = find(item.first), r = find(item.second);
        // 直接用前缀和公式 O(1) 算出结果
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

区间合并

1.思路

（1）通过对所有区间按左端点进行升序排列，利用变量维护当前合并区间的边界，遍历时若发现后续区间与当前边界存在交集则更新右边界，若无交集则结算当前区间并重新初始化边界。

（2）在执行 if (r < seg.first) 逻辑块时，为什么必须先 push_back 再更新 l, r？

变量 l 和 r存储的是当前正在处理的合并区间的边界数据，只要存的不是初始的l=r=-2e-9，那么就可以把这个pair压入vector并把边界更新，并等待下一个左右边界判断与当前边界的关系；

①如果不判断l!=-2e9：初始pairl=r=-2e9也会压入数组数据就不对了。

②如果先更新边界并根据这个边界压入vector里：不知道还有没有可以合并的数组。

③不在循环完后手动压入边界至vector：因为一开始先判断的不让初始边界进vector，相当于压入是滞后的，不手动压入一次就会漏掉一个pair。

2.题目：803. 区间合并 - AcWing题库

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

using namespace std;

typedef pair<int,int> PII;

vector<PII> merge(vector<PII> &segs)
{
    vector<PII> res; // 存放合并后的最终结果
    
    // [关键步]sort对pair排序时默认按first为参考排序，这里就是按左端点从小到大排序。
    // 只有排了序才能保证后面扫描时，新区间的左端点一定是向后移动的。
    sort(segs.begin(), segs.end());
    
    // 初始化当前维护的区间边界，设为负无穷（防止和题目给的合法坐标重叠）
    int l = -2e9, r = -2e9;
    
    for (auto seg : segs) // 遍历每一个原始区间
    {
        // 情况 1：当前扫描到的区间左端点比维护的右端点还要大，说明这两个区间“断开了”完全没有交集。
        if (r < seg.first) 
        {
            // 如果不是初始的那个负无穷区间，就把上一个已经“捏好”的区间存入结果
            if (l != -2e9) res.push_back({l, r});
            
            // 更新维护目标：开始观察这个全新的独立区间
            l = seg.first, r = seg.second;
        }
        // 情况 2：当前扫描到的区间左端点 <= 我们维护的右端点
        // 说明：这两个区间有重叠，或者刚好头尾相接。
        else 
        {
            // 贪心策略：把右边界延伸到最远的那一个
            r = max(r, seg.second);
        }
    }
    
    // 循环结束时，最后一个维护着的区间还没来得及塞进结果，得手动补上
    if (l != -2e9) res.push_back({l, r});
    
    segs = res; // 更新原数组
    return res;
}

int main()
{
    int n;
    cin>>n;
    
    vector<PII> segs;
    
    while(n--)
    {
        int l,r;
        cin>>l>>r;
        segs.push_back({l,r});
    }
    
    merge(segs);
    
    cout<<segs.size()<<endl;
    
    return 0;
}

数据结构（一）

单链表

1.思路

（1）为什么不用课本上学的结构体来构造链表？

数据结构课本中，链表由节点构成，每个节点保存了值Val和下一个元素的位置*Next这两个信息。节点的表示形式如下：

struct Node{
    int val;
    Node* next;
};


class Node{
public:
    int val;
    Node* next;
};

使用这种方法，在创建一个值为 x 新节点的时候使用new：

1 2	Node* node = new Node(); node->val = x

new的底层涉及内存分配，调用构造函数，指针转换等多种复杂且费时的操作。一秒大概能new 1w次左右。在平时的工程代码中，不会

涉及上万次的new操作，所以这种结构是一种“见代码知意”的好结构（也就是可以用在工程）。

但在算法题场景下，经常碰到操作在10w级别的链表操作；若使用结构体这种操作，则无法在算法规定时间完成任务。因此不能频繁使用

new操作，也即不能使用结构体来实现数组。

（2）详细问题解答：【问题解答用数组模拟单链表】

（3）在 if (!k) head = ne[head]; 中，如何理解 !k 的含义以及这行代码的作用？

! 是逻辑非运算符 (Logical NOT operator)。在逻辑判断中，0固定为False，那么!k就是用来判断是否为0，!0=True <=> k==0，反之为False。因此!核心作用是将操作数的布尔状态“取反”；比如k=5，逻辑上为真，取反就为假，也就是说k!=0前提下!k=False该判断不成立；反之k==0,!k=True。在该题中 $k = 0$ 时，特指删除头结点。

2.题目：826. 单链表 - AcWing题库

#include <iostream>

using namespace std;

const int N = 100010;


// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 将x插到头结点
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx ++ ; //该代码等价于head=idx,idx++;即让head指向当前节点idx，然后idx++代表操作下一个节点
}

// 将x插到下标是k的点后面
void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}

// 将下标是k的点后面的点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    int m;
    cin >> m;

    init();

    while (m -- )
    {
        int k, x;
        char op;

        cin >> op;
        if (op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'D')
        {
            cin >> k;
            if (!k) head = ne[head]; //<=>if(k==0)head=ne[head];
            else remove(k - 1);
        }
        else
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }

    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}

3.再写一次的错误

（1）ne[idx]=head;head=idx++;写成head=ne[idx]++这就是写反了，应当先更新idx，再更新和蔼的

（2）init();写进了循环里面，这样参数就没办法及时更新

双链表

1.思路

理解这段代码下标逻辑的关键在于两个核心设定：一是 insert(k, x) 的定义是在下标为 k 的节点右侧插入；二是 idx 从 2 开始，导致第 $k$ 个插入的数下标偏移为 $k + 1$ （对于单链表是 $k - 1$ ）。

（1）op == "L"（在最左端插入）：因为下标 0 是固定的虚拟头节点（左哨兵），根据 insert(k, x) 在 k 右侧插入的定义，直接在 0 后面插入即可成为第一个真实节点。

（2）op == "R"（在最右端插入）：因为下标 1 是虚拟尾节点（右哨兵），在最右端插入等价于“在右哨兵左边的那个节点（l[1]）的右边插入”。

（3）op == "D"（删除第 $k$ 个插入的数）：由于 idx 从 2 开始分配，第 1 个数下标是 2，第 2 个是 3，推导出第 $k$ 个插入的数其数组物理下标必然是 $k + 1$ 。

（4）op == "IL"（在第 $k$ 个插入的数左边插入）：在节点 $k + 1$ 的左边插入，等价于“在 $k + 1$ 那个节点当前左邻居（l[k+1]）的右边插入”。

（5）else (IR)（在第 $k$ 个插入的数右边插入）：这完全符合 insert 函数“在给定下标右侧插入”的本意，直接传入第 $k$ 个数的物理下标 $k + 1$ 即可。

2.题目：827. 双链表 - AcWing题库

注意：IL、IR是俩字母，所以不能用char要用string

#include<iostream>
using namespace std;

const int N=100010;

int e[N],l[N],r[N],idx;

void init()
{
    r[0]=1;
    l[1]=0;
    idx=2;
}

void insert(int k,int x)
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx++;
}

void remove(int k)
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}

int main()
{
    int m;
    cin>>m;
    
    init();
    
    while(m--)
    {
        int k,x;
        
        string op;
        cin>>op;
        
        if(op=="L")
        {
            cin>>x;
            insert(0,x);
        }        
        else if(op=="R")
        {
            cin>>x;
            insert(l[1],x);
        }        
        else if(op=="D")
        {
            cin>>k;
            remove(k+1);
        }     
        else if(op=="IL")
        {
            cin>>k>>x;
            insert(l[k+1],x);
        }        
        else
        {
            cin>>k>>x;
            insert(k+1,x);
        }
    }
    
    for(int i=r[0];i!=1;i=r[i])cout<<e[i]<<' ';
    cout<<endl;
    
    return 0;
}

3.再写一次的错误

（1）void init() { r[0]=1; l[1]=0; idx=2; }写成了l[0]=1这样就相当于0左边还有点，这肯定是不对的

（2） l[idx]=l[r[k]]; l[r[k]]=r[idx];，yxc代码中l[idx]=k;写成l[r[k]]也是对的但是自然是k更简洁明了；但是l[r[k]]=r[idx];就不对了，因为idx右边就是r[k]了这样相当于自环了。

（3）忘记了循环输出结果怎么写for(int i=r[0];i!=1;i=r[i])cout<<e[i]<<' ';，注意i!=1中这个1就是init的1，这里的1是虚拟出来的右边界，相当于插入的所有节点都在0，1这俩节点中间。

栈

1.思路

（1）单调栈：题目要找数组里头左边最小的数，首先第一个数进去的时候左边没数，应该输出-1，因此代码结构就是先做逻辑处理再对stk数组进行入栈；然后核心判断逻辑while(top&&stk[top]>=x)top--;tt用于判断stk是否为空，stk[tt]>=x自不必说，随后就一直top--，直到找到第一个在栈中小于x的数；top–只动了栈顶，因此数组是没变化的，但是确实能让指针指向了栈底的数字，所以等价于“出栈”（实际上是没出的），后续就通过stk[++top]=x;直接给使用过的位置替换就行。（注意stk[0]是不存数字的，因为0已经用于判空，因此是++tt）

（2）模拟栈：这个题很简单，就是在单调栈基础上稍微扩展了一下。

（3）表达式求值：该算法基于中缀表达式的算符优先法（Operator-Precedence Parsing），通过维护操作数栈和运算符栈协同实现。在遍历表达式字符串的过程中：若遇到数字，需通过内层循环连续读取字符并转化为十进制整数后压入操作数栈；若遇到左括号，直接压入运算符栈作为局部运算的起始边界；若遇到右括号，则循环调用 eval 函数直至运算符栈顶为左括号，并随后弹出该左括号以完成括号内子表达式的收敛；若遇到普通算术运算符，当运算符栈非空、栈顶不为左括号且栈顶运算符优先级大于或等于当前运算符时，循环调用 eval 执行先行运算以维护运算符的左结合律，随后将当前运算符压入运算符栈；eval 函数的原子操作定义为从操作数栈先后弹出右操作数 $b$ 和左操作数 $a$ ，从运算符栈弹出算子 $o p t$ ，并将计算结果 $a opt b$ 重新压回操作数栈；待字符串遍历结束后，依次清空运算符栈中的剩余算子进行最终结算，操作数栈中残余的唯一元素即为该表达式的最终代数结果。

解题思路：

①优先级表：用 unordered_map<char, int> 预设好 + - 为 1，* / 为 2。

②eval() 逻辑：

从 num 弹出 $b$ （右操作数）。
从 num 弹出 $a$ （左操作数）。
从 op 弹出操作符。
结果压回 num。

③两个 while 循环：

拼数字：while(isdigit) x = x * 10 + ...
对左右括号的处理：左括号直接入栈，右括号就运算括号内所有内容，最后把左括号弹出栈。
比优先级：while(op.size() && op.top() != '(' && h[op.top()] >= h[s[i]]) eval();

④后置处理：字符串跑完后，符号栈可能还有剩下的（比如 1+2+3 只处理了第一个 +），所以最后要 while(op.size()) eval();。

2.题目：

（1）830. 单调栈 - AcWing题库

#include<iostream>

using namespace std;

const int N=100010;

int stk[N],top;

int main()
{
    int n;
    cin>>n;
    
    while(n--)
    {
        int x;
        scanf("%d",&x);
        while(top&&stk[top]>=x)top--;
        if(top)printf("%d ",stk[top]);
        else printf("-1 ");
        
        stk[++top]=x;
    }
    
    return 0;
    
}

（2）828. 模拟栈 - AcWing题库

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

const int N=100010;

int stk[N],top;

int main()
{
    int n;
    cin>>n;
    int x;
    string op;
    while(n--)
    {
        cin>>op;
        if(op=="push")
        {
            cin>>x;
            stk[++top]=x;
        }
        else if(op=="pop")
        {
            top--;
        }
        else if(op=="empty")
        {
            if(top)cout<<"NO"<<endl;
            else cout<<"YES"<<endl;
        }
        else
        {
            cout<<stk[top]<<endl;
        }
    }
    
    return 0;
}

（3）3302. 表达式求值 - AcWing题库

//除了常规的两个库，还需要调stack栈，unordered_map无向图（哈希表）和string字符串
#include<iostream>
#include<cstdio>
#include<stack>
#include<unordered_map>
#include<string>

using namespace std;

stack<int> num;
stack<char> op; //用两个栈分别负责数据和符号的存储

unordered_map<char,int> h{{'+',1},{'-',1},{'*',2},{'/',2}}; //存储优先级键值对

void eval()
{
    int b=num.top(); //注意先出栈的其实是最后入栈的数，在运算中应该是处在符号后面，因此先定义b再定义a
    num.pop();
    
    int a=num.top();
    num.pop();
    
    char c=op.top();
    op.pop();
    
    int r=0; //定义r存储结果，后续再令结果入栈
    
    if(c=='+')r=a+b;
    else if(c=='-')r=a-b;
    else if(c=='*')r=a*b;
    else r=a/b;
    
    num.push(r);
}

int main()
{
    string s;
    cin>>s; //先定义字符串，然后在循环中分类讨论情况
    
    for(int i=0;i<s.size();i++)
    {
        int x=0,j=i; //用x存运算结果，j存运算位次
        if(isdigit(s[i])) //情况1：字符串这一位是数字，在循环里完成从字符串到数字的转换
        {
            while(j<s.size()&&isdigit(s[j]))
            {
                x=x*10+s[j]-'0';
                j++; //在连续的数里面j相当于取代了i的作用负责管这一整个数的各个位
            }
            num.push(x);
            i=j-1; //因为i还有++，所以要让i退回j指向的前一位，不然就两个++了
        }
        else if(s[i]=='(') //情况2：左括号不管可以直接入栈
        {
            op.push(s[i]);
        }
        else if(s[i]==')') //情况3：碰到右括号就直接开始算括号内的数并将结果压入栈
        {
            while(op.top()!='(')
            {
                eval();
            }
            op.pop(); //把左括号'('给弹出去
        }
        else //情况4：解决优先级高的*/先运算的问题
        {
            while(op.size()&&op.top()!='('&&h[op.top()]>=h[s[i]])eval(); 
            //op.top() != '('作用是在遇到对应的右括号之前，不进行左括号左边的运算
            op.push(s[i]);
        }
    }
    
    while(op.size())eval();
    cout<<num.top()<<endl;
    return 0;
}

队列

1.思路

（1）滑动窗口

（1）变量解释（front后面会换成head，这样和tail才配对）

①front 的作用：负责维护滑动窗口边界的有效性。它始终指向当前窗口内最优解（最大值或最小值）的下标；当队头存储的下标超出当前滑动窗口的有效左边界（即 i - k + 1 > q[front]）时，通过 front++ 执行队头出队操作，剔除失效的区间元素。

②tail 的作用：负责维护数据结构的单调性。它控制元素的入队与尾部出队；在新元素入队前，通过循环执行 tail-- 弹出队尾所有破坏指定单调性（如非严格递减或非严格递增）的冗余元素，随后通过 q[++tail] = i 将新元素的下标存入队列。

③需要注意的是front说白了是管出不出队，tail是管入不入队，不能简单地认为头一定要大于尾，在这里头反而要小于等于尾，这说明插入的数大于出去的数，队列才是非空的。

（2）核心代码解释

①if(front<=tail&&i-k+1>q[front])front++;：执行队头过期清理。 front <= tail 是边界安全检查，确保队列非空，防止出现空队列越界访问；i - k + 1 > q[front] 用于判定当前队头存储的下标是否已经落后于滑动窗口的有效左边界。若判定为真，说明该最优解已滑出窗口失效，通过 front++ 将其从队头物理逻辑上剔除。

②while(front <= tail && a[i] <= a[q[tail]]) tail--; （以寻找最小值为例）：维护队列的单调递增性。 front <= tail 同样保证队列非空；a[i] <= a[q[tail]] 将当前新遍历到的元素与队尾元素进行值比较。若当前元素更小或相等，说明现有的队尾元素在未来绝对不可能成为窗口内的最小值（因为新元素既比它小，存活时间又比它长）。此时触发 tail--，持续将这些丧失竞争力的冗余队尾元素弹出，直至遇到比新元素更小的值或队列被清空。

③ q[++tail] = i;：新元素下标强制入队。 经过上一句的单调性维护（剔除所有劣势元素）后，当前处理的元素下标 i 必须入队。因为它作为当前窗口最新加入的元素，是未来滑动窗口最优解的合法候选者。

④ if(i - k + 1 >= 0) printf("%d ", a[q[front]]);：输出当前窗口的最优解。 i - k + 1 >= 0（即 i >= k - 1）用于拦截未完全成型的窗口，判断当前遍历的进度是否已经容纳了至少 k 个元素。一旦第一个完整的滑动窗口形成，由于单调队列的性质，队头 q[front] 对应的元素 a[q[front]] 绝对是当前窗口的最优解，直接将其取出并打印。

（3）常见问题解答

①a[q[tail]]什么时候只有一个数，什么时候允许有两个数或以上？

当新来的元素比队列中所有的元素都“更优”（例如找最小值时，新来的元素比队列里所有数都小）时，队列会被清空到只剩这一个数。当新来的元素没有破坏单调性，也就是它比队尾元素“更劣”（例如找最小值时，新来的元素比队尾的数更大）时，它无法踢走任何人，只能委屈地排在队尾充当“备胎”。

（4）基于样例手写处理过程

（2）模拟队列

这题关键就在于理清楚头指针与尾指针的数量关系，初始时head=0，tail=-1，tail负责插入数head负责移除树；当没有数时head==tail+1为空；当插入第一个数时tail先加再赋值a[0]，此时head==tail非空；再插入第二个数是++tail，此时tail指向1head仍指向0，……，当需要移除数的时候head++，此时虽然数组中仍存着数据（也可以考虑free）但是从指针的角度已经把队头的数扔了。整体操作和模拟栈是很像的，只是从一个指针变成两个。

2.题目：

（1）154. 滑动窗口 - AcWing题库

#include<iostream>
#include<cstdio>

using namespace std;

const int N=1000010;

int a[N],q[N],head=0,tail=-1;

int main()
{
    int n,k;
    cin>>n>>k;
    
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    
    //按照题目先求最小值序列，其中a[i]<=a[q[tail]]表示当前值与队尾插入值的大小比较，如果当前值更小说明当前值更适合成为最小值候选/甚至直接成为最小值，取决于while会不会直接使tail=-1造成单调队列q[]归空。
    for(int i=0;i<n;i++)
    {
        if(head<=tail&&i-k+1>q[head])head++;
        while(head<=tail&&a[i]<=a[q[tail]])tail--;
        q[++tail]=i;
        if(i-k+1>=0)printf("%d ",a[q[head]]);
    }
    
    cout<<endl; //或者puts("");
    
    //求最大值序列
    head=0,tail=-1; //一定要记得复原队头队尾
    
    for(int i=0;i<n;i++)
    {
        if(head<=tail&&i-k+1>q[head])head++;
        while(head<=tail&&a[i]>=a[q[tail]])tail--;
        q[++tail]=i;
        if(i-k+1>=0)printf("%d ",a[q[head]]);
    }
    
    return 0;
}

（2）模拟队列

#include<iostream>
#include<cstdio>

using namespace std;

const int N=100010;

int a[N],head=0,tail=-1;

int main()
{
    int n;
    cin>>n;
    string op;
    int x;
    while(n--)
    {
        cin>>op;
        if(op=="push")
        {
            cin>>x;
            a[++tail]=x;
        }
        else if(op=="pop")
        {
            head++;
        }
        else if(op=="empty")
        {
            if(head==tail+1)cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        else
        {
            cout<<a[head]<<endl;
        }
    }
}

KMP

1.思路

（1）KMP算法是取三个发明者的首字母得来的名字，算法的目的是在字符串匹配时不用暴力求解（双循环）这种方式而采用部分匹配表的形式避免重复比较。

（2）参考思路解析：字符串匹配的KMP算法 - 阮一峰的网络日志

（3）个人解析：KMP关键就是弄懂如何避免重复比较取而代之地是实现快速从当前失败的匹配串跳到下一个部分成功匹配串的位置，具体来说首先要弄懂待定子串（也就是不确定是不是子串的那个短的字符串，题目里称为模式串）内部的以某一个pivot（轴）分成两半的串有没有相同部分，然后就是用相同的思路让待定子串在完整字符串（也就是长的字符串）也实现借助相同部分的快速跳跃。

具体来说首先就是弄清楚待定子串里头是否有重复可跳跃位置并用数组ne[]记录。注意处理ne[]时我们已经先让ne[0]=-1因为内部的跳跃不能自己跳转到自己位置，这样无意义，因此设置为-1；故循环时int i=1;i……。然后就是用while反复判断当j没有回到完全无匹配状况，且前后子串确实无法匹配上时就回退代表匹配成功长度的j，i扮演的角色就是不停挪动这个轴，然后看看轴两次能否找到相同部分，找到了匹配长度j++，由此便可记录下子串内部的可跳跃位置，用ne[]存储；

然后再让i~[0,n)因为此时i代表大字符串了，然后j=-1依旧，表示待定子串的重复长度，然后重复待定子串内部的匹配过程即可。因为最后输出的是重复子串的初始位置而非长度，因此用i-j来输出子串位置。

要初始设置的变量是待定子串char p[N]（可以记：kmp以p结尾，故待定匹配子串为p），大字符串为char s[N]，待定子串内部跳跃位置用ne[N]存储，以及待定子串和大字符串的长度。

（4）疑问：在 KMP 匹配成功一个完整模式串后，执行 j = ne[j] 的核心目的是什么？

核心目的是为了高效处理重叠匹配的情况，利用当前匹配成功的模式串末尾部分（后缀）可能正是下一个潜在匹配开头部分（前缀）的特性，通过 $n e [j]$ 将指针跳转到最长相等前后缀的位置，从而在不遗漏任何重叠子串的前提下，最大化地利用已匹配信息继续向后扫描，避免了像暴力算法那样在匹配成功后直接重置进度而导致效率低下或结果遗漏。

以在 ababa 中搜索 aba 为例，当程序在文本串下标 $0, 1, 2$ 处找到第一个 aba 后， $j$ 会根据 $n e [2] = 0$ 回退到下标 $0$ ，这本质上是利用了 aba 首尾都是 a 的对称性，让模式串开头的 a 瞬间对齐到文本串刚才匹配成功的那个末尾字符 a（下标 2），使得程序能紧接着从文本串下标 $3$ 开始比对模式串的第 $1$ 位（字符 b），从而丝滑地识别出从下标 $2$ 开始的第二个 aba；而如果将 $j$ 重置为 $- 1$ ，程序就会从文本串下标 $3$ 开始重新寻找字符 a，进而彻底错过这两个 aba 之间共享的那个字符。

2.题目：831. KMP字符串 - AcWing题库

#include<iostream>
#include<cstdio>

using namespace std;

const int N=1000010;

char p[N],s[N];
int ne[N];

int main()
{
    int n,m;
    cin>>n>>p>>m>>s;
    ne[0]=-1;
    
    //对待定子串内部找重复内容并记录跳跃点，将跳跃点存入ne数组中
    for(int i=1,j=-1;i<n;i++)
    {
        while(j!=-1&&p[i]!=p[j+1])j=ne[j];
        if(p[i]==p[j+1])j++;
        ne[i]=j;
    }
    
    //将待定子串与字符串进行匹配，并输出结果
    for(int i=0,j=-1;i<m;i++)
    {
        while(j!=-1&&s[i]!=p[j+1])j=ne[j];
        if(s[i]==p[j+1])j++;
        if(j==n-1)
        {
            cout<<i-j<<' ';
            j=ne[j];
        }
    }
    
    
    return 0;
}

数据结构（二/三）

三是哈希表+STL常用内容。

Trie树：以树结构存储字符串、数字串等

1.思路

（1）Trie字符串统计

①son[N][26]代表啥意思？

是 Trie 树的“导航地图”，第一维 N 是节点的唯一编号，第二维 26 对应 26 个字母路径所指向的下一个节点下标。因为该数组处理时是son[p][u]，p就是节点所在层数，u就是添加的字母转为1~26的数字。

②为什么是char op[2]，为什么是if(*op == 'I')有这个*？

char op[2] 预留了一个空位给结束符 \0 以便使用 %s 安全读入，而 \*op 则是通过解引用获取该地址存储的第一个字符（即具体的指令字母）。

③这道题是处理小写字符串用int u = str[i] - 'a';，那要是处理数字串呢？

将转换逻辑改为 int u = str[i] - '0';，并确保 son 数组的第二维大小至少设为 10 即可。

（2）Trie字典树求异或和：该算法利用 01-字典树（01-Trie） 存储整数的二进制表示，通过贪心策略（Greedy Strategy）在 $O (N \cdot \log C)$ 时间复杂度内解决最大异或和问题。在处理过程中：首先将每个整数视为长度为 31 位的二进制序列（从高位 $2^{30}$ 到低位 $2^{0}$ ）；insert 函数通过 idx 计数器在 son[M][2] 数组中动态开辟节点，将数字按位插入树中，形成一条唯一的从根到叶的路径；query 函数则是算法的核心，对于给定的数字 $x$ ，从高位到低位遍历其二进制位 $u$ ，并优先尝试检索路径中与 $u$ 相反的节点 !u（即若当前位为 0 则找 1，为 1 则找 0）。若相反路径存在，则该位异或结果为 1，累加至结果 res 并进入该分支；若不存在，则被迫进入相同位分支。基于二进制权重特性，高位异或产生的 1 贡献远超低位之和，故该贪心检索能确保找到与 $x$ 异或结果最大的配对数。最终，通过遍历原数组并不断更新全局最大值，即可得到答案。

① 存储结构与指针：

使用 son[M][2] 模拟二叉树，其中 M 约为 $N \times 31$ 。

idx 作为自增变量，负责为新出现的二进制路径节点分配唯一的“房间号”。

② insert(x) 逻辑：

位拆解： 使用 for(int i=30; i>=0; i--) 循环。

路径创建： 取出 $x$ 的第 $i$ 位 u = x >> i & 1。

动态开点： 若 son[p][u] 为 0，则执行 ++idx 创建新节点，随后 p 指向该子节点。

③ query(x) 贪心搜索：

目标： 找与 $x$ 每一位都尽量相反的路径。

优先级： 检查 son[p][!u] 是否存在。

存在（成功）： 说明这一位能异或出 1，res = res * 2 + 1，进入 !u 分支。
不存在（失败）： 只能走 son[p][u]，这一位异或得 0，res = res * 2 + 0，进入 u 分支。

④ 全局遍历：

同步进行： 在读入数据时先执行 insert(a[i])。

二次遍历： 循环数组，对每个 a[i] 执行 query(a[i])，利用 max(res, query(a[i])) 维护全局最高得分。

2.题目

（1）835. Trie字符串统计 - AcWing题库

#include <iostream>

using namespace std;

const int N = 100010;
//son[][]存储子节点的位置，分支最多26条；
//cnt[]存储以某节点结尾的字符串个数（同时也起标记作用）
//idx表示当前要插入的节点是第几个,每创建一个节点值+1
int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str/str[])
{
    int p = 0;  //类似指针，指向当前节点
    for(int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a'; //将字母转化为数字
        if(!son[p][u]) son[p][u] = ++idx;   //该节点不存在，创建节点
        p = son[p][u];  //使“p指针”指向下一个节点
    }
    cnt[p]++;  //结束时的标记，也是记录以此节点结束的字符串个数
}

int query(char *str/str[])
{
    int p = 0;
    for(int i = 0; str[i]; i++)
    {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;  //该节点不存在，即该字符串不存在
        p = son[p][u]; //p = son[p][u]是根据字符偏移量实现从当前节点到特定子节点索引的状态转移，不能用p++：p++仅是内存下标的线性自增，违背字典树的层级拓扑逻辑并导致前缀压缩存储失效。
    }
    return cnt[p];  //返回字符串出现的次数
}

int main()
{
    int m;
    cin >> m;

    while(m--)
    {
        char op[2];
        scanf("%s%s", op, str);

        if(*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }

    return 0;
}

（2）143. 最大异或对 - AcWing题库

#include<iostream>
#include<cstdio>

using namespace std;

const int N=100010,M=31*N;

int a[N],son[M][2],idx;

void insert(int x)
{
    int p=0; //定义当前所处树的层级
    for(int i=30;i>=0;i--) // 从最高位开始处理是利用贪心思想：高位异或出1对数值增大的贡献远大于低位之和
    {
        int u=x>>i&1; //与1运算相当于就是看这一位是1还是0，1&1=1，1&0=0
        if(!son[p][u])son[p][u]=++idx; //如果不存在这个节点就借助idx这个变量开一个第idx号节点
        p=son[p][u]; //进入下一个节点
    }
}

int query(int x)
{
    int p=0,res=0;
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;
        if(son[p][!u]) //异或运算就是两个数相等得0不相等得1，因此!u才是想要的结果（代表不相等），res=res*2+1相当于手动进行了二进制进位
        {
            p=son[p][!u]; //成功了就进入这个!u节点
            res=res*2+1; //res相当于记录已经转成10进制得2进制数串结果，不相等所以当前位结果为1
        }
        else
        {
            p=son[p][u]; //失败了就进入这个u节点
            res=res*2+0; //不相等所以当前位结果为0
        }
    }
    
    return res;
}

int main()
{
    int n;
    cin>>n;
    
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]); 
        insert(a[i]); //在输入具体数字的同时把数字插入trie树里
    }
    
    int res=0;
    for(int i=0;i<n;i++)res=max(res,query(a[i])); //定义一个结果，通过查询取最终结果
    cout<<res<<endl;
    
    return 0;
}

并查集

1.思路

所谓并查集就是利用树实现对集合的合并与查找（并查集：可以合并可以查找的集合），解题关键在于定义父节点数组p[]并借助find函数沿着p数组最终找到根节点，实现并查。

2.题目

（1）836. 合并集合 - AcWing题库

#include<iostream>

using namespace std;

const int N=100010;

int p[N];

int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]); //一方面实现递归寻找父节点最终求得根节点，另一方面实现路径压缩，即找到根节点之后直接把当前节点连到根节点上，提升效率。
    return p[x];
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)p[i]=i; //初始化的时候每个节点的父节点都是自己，这也意味着每个节点在初始化的时候都是单独的节点，也就是自己作为这棵树的根节点。
    
    while(m--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(*op=='M')p[find(a)]=find(b); //如果需要合并，就把一棵树的根节点当成另一棵树根节点的子节点，find作用就是求得当前节点的根节点。
        else
        {
            if(find(a)==find(b))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
}

（2）837. 连通块中点的数量 - AcWing题库

#include<iostream>
#include<cstdio>

using namespace std;

const int N=100010;

int p[N],s[N];

int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        p[i]=i;
        s[i]=1;
    }
    
    while(m--)
    {
        char op[5];
        int a,b;
        scanf("%s",op);
        
        if(op[0]=='C')
        {
            cin>>a>>b;
            if(find(a)==find(b))continue;
            s[find(b)]+=s[find(a)]; //注意这里必须得先计算节点数量再进行合并，不然对子树a的统计就不准确了，因为此时a已经合并到了b。此外是b的节点数量中要加上a的，因为是把a的祖宗节点连到了b的祖宗节点里，不能反了
            p[find(a)]=find(b);
        }
        
        else if(op[1]=='1')
        {
            cin>>a>>b;
            if(find(a)==find(b))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        
        else 
        {
            cin>>a;
            cout<<s[find(a)]<<endl;
        }
    }
    
    return 0;
}

堆

1.思路

（1）堆排序

（2）模拟堆

① ph[idx]=cnt; hp[cnt]=idx; h[cnt]=x; 这三个数组分别存储了什么东西？

直观来记hp[cnt]=idx中数组取值cnt代表该节点在heap中的位置，取值idx代表该节点实际插入位置，因此是hp（heap-pointer）；反之ph[idx]=cnt就是已知第idx插入求堆中实际位置cnt；因此在对第k个数操作时才会有k=ph[k]本质上就是得出了k在堆中的实际位置。

答案： 这三个数组构成了双向映射堆的核心，用于在 $O (1)$ 时间内定位第 $k$ 个插入的元素。

h[i]：存储堆中下标为 $i$ 的节点的权值。

ph[k]（Pointer to Heap）：存储第 $k$ 个插入的元素当前在堆数组 h 中的下标。

hp[i]（Heap to Pointer）：存储堆下标为 $i$ 的元素是第几个插入的（即该节点对应的 idx）。

举例： 依次执行 I 10 (第1个插入) 和 I 5 (第2个插入)。

插入 10 后：h[1]=10, ph[1]=1, hp[1]=1。

插入 5 后（放入末尾）：h[2]=5, ph[2]=2, hp[2]=2。

执行 up(2)：由于 $5 < 10$ ，两者交换。

h 数组：变为 h[1]=5, h[2]=10。
hp 数组：同步交换，变为 hp[1]=2, hp[2]=1（说明现在堆顶是第2个插入的）。
ph 数组：通过 hp 反向定位并更新，变为 ph[2]=1, ph[1]=2（说明第2个插入的数现在在堆顶）。

②为什么 DM 只用了 down，而 D 和 C 操作需要同时使用 down 和 up？

DM 操作：其逻辑是将堆顶（全堆最小值）与堆尾元素交换并删除堆尾。被交换到堆顶的元素原属于底层，其值必然大于等于原堆顶，且通常大于其新的子节点。因此，该节点在逻辑上只能向下移动（down）以重新寻找平衡，不存在向上移动的空间。

D k 或 C k x 操作：其目标是堆中的任意节点。由于第 $k$ 个插入的数可能被修改为任意值，或者被堆尾的一个随机大小的数所替换，该位置的新值与原有父节点、子节点的关系是随机的。若新值比父节点小，则需 up；若比子节点大，则需 down。在实际执行中，up 和 down 只会有一个被触发（或都不触发），同时调用两者是为了应对任意位置数值变动的不确定性。

2.题目

（1）838. 堆排序 - AcWing题库

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N=100010;


int h[N],cnt;

void down(int u) //因为小根堆中只能保证父节点的两个子节点一定大于等于父节点，但是两个子节点之间连必然关系都没有，因此需要借助down函数完成这三个数的大小判断并改动堆，实现更小的数一定排上面 
{
    int t=u; //u指代的是父节点，后续要对t这个存储最小值下标的变量操作
    if(2*u<=cnt&&h[2*u]<h[t])t=2*u;
    if(2*u+1<=cnt&&h[2*u+1]<h[t])t=2*u+1;
    if(u!=t)
    {
        swap(h[u],h[t]);
        down(t);
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<=n;i++)scanf("%d",&h[i]); //注意i要从1开始，从0开始就没办法算2n/2n+1了
    cnt=n;
    
    for(int i=n/2;i;i--)down(i); //构建堆，因为堆的性质对于最后一层的叶节点是不成立的，因此必须是对叶节点的子节点以上构建堆，因此选的是1=n/2
    
    while(m--)
    {
       printf("%d ",h[1]);
       h[1]=h[cnt--];
       down(1); //这里只需要用down操作，因为是对根节点重新构建小根堆
    }
    
    return 0;
    
}

（2）839. 模拟堆 - AcWing题库

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=100010;

int h[N],hp[N],ph[N],cnt,idx;

void heap_swap(int a,int b) //一楼1：注意这是三个swap不是赋值
{
    swap(ph[hp[a]],ph[hp[b]]); //先交换实际插入位置，它需要根据堆位置来映射推断
    swap(hp[a],hp[b]);  //然后交换实际堆位置
    swap(h[a],h[b]);  //最后交换取值本身
}

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

void up(int u)
{
    while(u/2&&h[u]<h[u/2])  //注意这里是while判断且面向子节点小于父节点的情况，u是子节点，u/2是父节点
    {
        heap_swap(u,u/2);
        u/=2;
    }
}

int main()
{
    int n;
    cin>>n;
    
    while(n--)
    {
        string op;
        int k,x;
        cin>>op;
        
        if(op=="I")
        {
            cin>>x;
            cnt++,idx++; //首先要先给俩下标都加1
            ph[idx]=cnt; //对应完成赋值
            hp[cnt]=idx;
            h[cnt]=x;
            up(cnt); //遗漏2：最后要给cnt完成堆排序（因为cnt是最大值所以用up）
        }
        
        else if(op=="PM")printf("%d\n",h[1]);
        
        else if(op=="DM")
        {
            heap_swap(1,cnt--);
            down(1);
        }
        else if(op=="D")
        
        {
            cin>>k;
            k=ph[k];
            heap_swap(k,cnt--);
            down(k); //这里同时有down/up原因是这个插入的值既可能比上面小也可能比下面大，所以俩都得有，实际上一次也只会用一个，因为更新好了就不存在第二个。
            up(k);
        }
        
        else
        {
            cin>>k>>x;
            k=ph[k];
            h[k]=x;
            up(k);
            down(k);
        }
    }
    
    return 0;
}

哈希表

1.思路

（1）模拟散列表

散列表的构建有两种方法：拉链法和开放寻址法，为了方便这里就只介绍拉链法（与后续图论相关）。实现的方法与构建单链表类似，最核心就是如何从实际数值映射到哈希表下标来存储：N=100000+3是一个经验值（因为是质数）用于提高哈希表的映射效率。k=(x%N+N)%N本质其实就是k=x%N基于这样的方式去映射到下标，先加再模是对负数的特殊处理，负数的模在C++里还是负数，而数组是从0开始，因此必须得先加再模；后面的操作思想就非常类似于单链表了。

（2）字符串哈希

字符串哈希就是从k进制的角度把字符看成数字，然后用求前缀和的形式去比较哈希值看字符串是否相等。首先需要明确的是相比于前缀和（用右边界前缀和减左边界前缀和）字符串哈希需要给左边界前缀和进位到与右边界前缀和最高位对齐，这样才会得到需要比较的那两位的哈希值。然后注意进位k取得是经验值P=131；随后代码从前往后，先定义ull的哈希数组h[N]和负责管进位数的数组p[N]，然后初始化前缀和——即分别设置h[0]=1以及前缀和的初始过程，然后还得初始化进位数组p，然后就是计算前缀和是否相等，由此判断Yes/No。

2.题目

（1）840. 模拟散列表 - AcWing题库

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int N=100010+3;

int h[N],e[N],ne[N],idx;

void insert(int x)
{
    int k=(x%N+N)%N;
    e[idx]=x;
    ne[idx]=h[k];
    h[k]=idx++;
}

bool find(int x)
{
    int k=(x%N+N)%N;
    for(int i=h[k];i!=-1;i=ne[i])
    {
        if(e[i]==x)
        {
            return true;
            break;
        }
    }
    return false;
}

int main()
{
    int n;
    cin>>n;
    memset(h,-1,sizeof(h));
    
    
    while(n--)
    {
        char op[2];
        int x;
        scanf("%s %d",op,&x);
        
        if(*op=='I')insert(x);
        else
        {
            if(find(x))cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    
    return 0;
}

（2）841. 字符串哈希 - AcWing题库

#include<iostream>
#include<cstdio>

using namespace std;

const int N=100010,P=131;

typedef unsigned long long ull;

ull h[N],p[N];
char str[N];

//get函数求前缀和
ull get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1]; //p[r-l+1]表示求子串的长度然后让他进这个长度的p位
}

int main()
{
    int n,m;
    cin>>n>>m;
    scanf("%s",str+1);
    
    
    //初始化前缀和
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        h[i]=h[i-1]*P+str[i];
        p[i]=p[i-1]*P;
    }
    
    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)==get(l2,r2))cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    
    return 0;
}

STL容器

STL：Standard Template Library标准模板库

vector向量/pair<变量类型1,变量类型2>（存储二元组）

1.vector变长数组，基本思想是倍增：系统为某一程序分配空间时所需时间与空间大小无关，只与申请次数有关；因此申请一次开一个1000大小的空间速度是申请1000次开1个大小空间的1000倍。因此vector开空间采用倍增思想，当个数超过当前大小空间时，就开辟一个当前大小两倍的空间，把当前元素直接复制过去，从而尽可能减少申请次数，允许浪费空间。

2.开vector可以用vector<int> a(10,3)，相当于给每变长数组开了10个，每个值为3；也可以用vector<int> a[10]，只是开了个vector。

3.vector有的函数是：size()返回元素个数；empty()返回是否为空；clear()清空（大部分容器都没有这个函数）；front()/back()返回vector的第一个数/最后一个数；push_back()/pop_back()是把vector的最后一个位置插入数/删除数；begin()/end()分别代表vector的第一个数/最后一个数。

//vector两种迭代方式
int main()
{
    vector<int> a;
    
    for(int i=0;o<10;i++)a.push_back(i);
    
    //循环迭代
    for(int i=0;i<a.size();i++)cout<<a[i]<<' ';
    
    //迭代器迭代
    for(vector<int>::iterator i=a.begin();i!=a.end();i++)cout<<*i<<' ';
	
    cout<<endl;
}

4.vector还支持比较运算，具体比较方式就是按位字典序，比如下面这个例子a<b是成立的（3<4）：

1
2
3

vector<int> a(4,3),b(3,4);
if(a<b)cout<<"Yes"<<endl;
else cout<<"No"<<endl;

5.pair二元组前后的变量类型可以任意，比如pair<int,string>；其中pair.first代表第一个元素pair.second代表第二个元素。

6.pair支持比较运算，以first为第一关键字，second为第二关键字（字典序）

#include<vector>

int main()
{
    pair<int,string>p; //定义pair；
    
    p=make_pair(10,"yxc");//pair创建方法1：用make_pair函数
    p={20,"yxc"};//c++11后pair可以以花括号形式创建
}

7.pair的应用场景：比如说有一个二元组要按照其中一个元素排序，那么就把要排序的元素放在第一关键字，第二关键字的元素就会跟着第一关键字元素一起移动。

8.pair还可以直接用来存储三个属性：pair<int,pair<int,int>>p

string字符串

1.string字符串，substr()返回某个子串，c_str()返回字符数组的头指针。

2.支持的函数：size()/length()返回字符个数/字符串长度；empty()判空；clear()清空字符串。

3.string可以直接用+拼接字符串，比如a+='abc';b+='def'。

4.函数substr(a,b)，a是指定起始位置，b是指定长度，这样就可以获取特定子串的内容了：a.substr(1,2)返回的就是从1开始长度为2的字符串子串。如果设定的a,b参数使得字符串子串长度超出字符串本身长度，那么就输出到字符串本身长度为止。如果不提供参数b比如substr(a)，那么就返回从a开始的完整子串。

queue队列/priority queue优先队列

1.queue队列，push()从队尾插入，front()返回队头元素，pop()从队头弹出

2.priority queue优先队列（是一个堆），push()插入元素，top()返回堆顶，pop()把堆顶弹出

3.push是向队尾插入元素，front()/back()是返回队头/队尾元素，pop()弹出队头元素， size()/empty()这种常规的当然也有，但是queue是没有clear()的。

stack栈

1.stack是栈，push()是往栈顶添加元素，top()返回栈顶元素，pop()弹出栈顶元素

set，map，multiset，multimap

红黑树就是平衡二叉树的一种；set，map，multiset，multimap基于平衡二叉树（红黑树），动态维护有序序列

1.set（集合）：是一个有序且元素唯一的容器（基于红黑树，插入时自动排序并去重）。

2.multiset（多重集合）：是一个有序但允许元素重复的容器（基于红黑树，插入时自动排序但不断开相同元素）。

set/multiset支持insert()插入一个数，find()查找一个数，count()返回某一个数的个数，erase(x)输入一个数x删除所有的x，也可以是输入一个迭代器，删除所有迭代器；两个核心操作是lower_bound(x)返回大于等于x的最小的数，upper_bound(x)返回大于x的最小的数

3.map（映射）：是一个存储唯一键值对（key-value）的有序关联容器（基于红黑树，按 key 排序且 key 不可重复）。

4.multimap（多重映射）：是一个存储键值对且允许键重复的有序关联容器（基于红黑树，按 key 排序且允许同一个 key 对应多个 value）。

map就类似于py中的字典，以键值对的形式实现映射

insert()插入的数是一个pair，erase()输入的参数是pair或迭代器，find()查找一个数，最重要的是能像数组一样用，比如：

#include<map>
using namespace std;

int main()
{
    map<string,int> a;
    a["yxc"]=1;
    cout<<a["yxc"]<<endl;
    
    return 0;
}

unordered set，unordered map，unordered multiset，unordered multimap

1.unordered_set：是一个无序且元素唯一的容器（基于哈希表，插入和查找平均时间复杂度为 $O (1)$ ）。

2.unordered_multiset：是一个无序但允许元素重复的容器（基于哈希表，相同哈希值的元素会被放在同一个桶中）。

3.unordered_map：是一个存储唯一键值对（key-value）的无序关联容器（基于哈希表，按 key 的哈希值存储，key 不可重复）。

4.unordered_multimap：是一个存储键值对且允许键重复的无序关联容器（基于哈希表，允许同一个 key 映射到多个 value）。

搜索与图论（一）

DFS

1.思路

（1）排列数字：上数据结构时老师曾提到dfs用栈bfs用队列，bfs确实用队列但dfs通过递归解决。通常解题思路就是先明确终止递归对应的操作（通常对应print一个结果）定义一个存结果的数组和一个状态数组表示是否访问过，如果没访问过即状态数组为false就将其置为true，然后处理相关内容，然后递归调用dfs，然后再将其状态返回false代表往回走。

dfs回溯的时候通常还需要恢复结果数组本身内容，但是这个排列数字刚好自己会覆盖所以就可以省略这一行，但是一般都得对结果数组也有操作

（2）n-皇后：整体处理过程与排列数字一致，主要讲讲状态数组为什么写成col[y]==false&&dg[x-y+n]==false&&udg[x+y]==false：国际象棋皇后可以横走竖走正反对角线走，因为dfs的迭代层u本身表示了行，所以就只定义了列和两个对角线，对于正对角线，其上元素都用x-y表示，但因为其可能为负所以得+n保证为正否则数组下标会溢出；反对角线就用x+y表示，不存在溢出所以直接就写位x+y

3019_d7a30075cc-微信图片_20220505182615

2.题目
（1）842. 排列数字 - AcWing题库

#include<iostream>
#include<cstdio>

using namespace std;

const int N=10;

int path[N];
bool state[N];
int n;

void dfs(int u)
{
    if(u==n)
    {
        for(int i=0;i<n;i++)printf("%d ",path[i]); //这里i是0~n-1原因是管的存储数据的数组path的下标
        puts("");
        return; //到达搜索树的叶子节点,终止该分支的深度优先搜索,返回（系统开辟的）调用栈的上一层
    }
    
    for(int i=1;i<=n;i++) //这里i是1~n原因是全排列求的是1~n的数: path[u]=i
    {
        if(!state[i])
        {
            path[u]=i;
            state[i]=true;
            dfs(u+1);
            //path[u]=i; 这一行可加可不加，但是dfs通常都需要恢复原位所以一概加就不用专门记
            state[i]=false;
        }
    }
}


int main()
{
    cin>>n;
    dfs(0);
    return 0;
}

（2）843. n-皇后问题 - AcWing题库

#include<iostream>
#include<cstdio>

using namespace std;

const int N=20;

int n; //因为n在函数和主函数里都得用，所以必须得全局定义
char q[N][N]; //存放皇后和占位符.
bool col[N],dg[N],udg[N]; //col表示某列是否放置皇后，dg表示对角线是否放置皇后，udg表示反对角线是否放置皇后；dg就是diagonal对角线

void dfs(int u)
{
    if(u==n)
    {
        for(int i=0;i<n;i++)puts(q[i]); //这里只给q[i]没有j就意味着一个q[i]代表一整行的"..Q."这样，然后每输出完一行就会自动换行，遍历q[i]就代表了q的所有行
        puts("");
        return;
    }

    int x=u;
    for(int y=0;y<n;y++)
    {
        if(col[y]==false&&dg[x-y+n]==false&&udg[x+y]==false)
        {
            q[x][y]='Q';
            col[y]=dg[x-y+n]=udg[x+y]=true;
            dfs(u+1);
            q[x][y]='.'; //和之前的输出全排列相比多了一个复位行，因为path[u]=i这种赋值操作本身就是一种“覆盖式恢复”
            col[y]=dg[x-y+n]=udg[x+y]=false;
        }
    }
}


int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            q[i][j]='.';
        }
    }

    dfs(0);
    return 0;
}

BFS

1.思路

（1）利用广度优先搜索BFS在一张二维网格图上，通过按层扩展在 $O (N \times M)$ 时间复杂度内解决无权图的最短路径问题。在处理过程中：首先利用memset将全局数组g初始化设定为障碍物状态，形成天然的防越界边界，随后读入真实的 $N \times M$ 迷宫数据；bfs函数是算法的核心，借助queue队列结构遵循先进先出原则，从起点 $(1, 1)$ 开始向外逐层扩散；每次进入while循环，从队头取出一个中心坐标节点，并利用对应绑定的方向数组dx与dy尝试向上下左右四个相邻位置进行试探走位。若遇到值为 $0$ 的合法空地，立刻将该地标为 $1$ 以防后续路径重复访问陷入死循环，同时将新位置的移动步数累加转移至记录数组d中，并将该新坐标送入队列尾部。基于BFS特性，水波纹首次蔓延到目标终点 $(N, M)$ 时必然经历的是最短步数路径。最终，直接打印输出d[n][m]即可得到答案。

①数据结构与预处理：

状态存储：使用g[N][N]存储迷宫地图与实时访问状态，d[N][N]独立记录每个点距离起点的最短步数。
坐标打包：借助typedef对pair<int,int>进行重命名缩写为pii，方便后续将二维坐标 $(x, y)$ 统一打包压入queue<pii>队列中。
边界防御：进入main函数后通过memset(g,1,sizeof(g))巧妙地将整张大网格默认刷成障碍物墙壁，从而免去bfs中繁琐的地图边界越界检查逻辑。

②队列初始化与主循环：

注入源头：通过q.push({a,b})将起点坐标装入队列，作为向外扩张探索的零号源头。
循环屏障：while(!q.empty())保证只要图中依然存在合法且未走过的联通空地，试探扩散就会不断维持运行。
取出中心：通过pii start=q.front()拿到当前扩张波纹的中心节点，并紧接q.pop()将其移出队列准备运算。

③四向扩展与状态转移：

偏移匹配：定义局部方向数组dx[4]={0,0,-1,1}与dy[4]={-1,1,0,0}，两两纵向配对产生四个正交方向的位移增量。
坐标推演：在for(int i=0;i<4;i++)循环中，基于当前节点计算出下一步即将迈入的测试坐标 $x$ 与 $y$ 。
合法校验：核心拦截判断if(g[x][y]==0)负责审核新坐标是否属于尚未被任何人踩踏过的安全空地。

④节点入队与距离结算：

状态封锁：成功进入合法空地后，光速执行g[x][y]=1将其踩成障碍物，彻底杜绝其他路线再来走二次回头路。
步数递推：执行d[x][y]=d[start.first][start.second]+1实现状态转移，到达新点的花费恒等于其父亲节点花费加 $1$ 。
入队待命：末尾执行q.push({x,y})将新阵地装入队列，该点将在未来的循环中正式晋升为新的扩张中心，直至全图探索结束并在主函数输出d[n][m]。

（2）八数码：处理过程中首先将传统的 $3 \times 3$ 二维矩阵降维压缩成一个长度为 $9$ 的一维字符串，并将目标状态定义为end变量中存储的"12345678x"；bfs函数是算法的核心，借助queue队列结构与unordered_map哈希表，从输入的初始字符串状态s开始向外逐层扩散查找；每次进入while循环，从队头取出一个当前状态字符串t，若等于目标状态end则直接返回记录的距离变量distance；若不等于，则通过find函数定位出空格'x'的一维索引 $k$ ，并利用数学运算 $x = k / 3$ 与 $y = k % 3$ 将其映射回虚拟的二维坐标 $(x, y)$ 。随后，利用方向数组dx与dy尝试向四个相邻方向移动空格。若移动未越界，则在字符串中执行一维索引 $a \times 3 + b$ 的字符交换操作生成新状态；若该新状态在哈希表d中未被记录，说明这是一次有效且未重复的推演，遂将其步数加 $1$ 并压入队列q尾部待命。特别注意，每次试探完毕后必须立刻再次交换以回溯恢复原状态字符串，确保四个方向的扩展互不干扰。最终，若队列耗尽仍未碰见目标状态，则返回 $- 1$ 代表无解。

①数据结构与状态表示：

降维映射：利用string类型将二维盘面拉直为一维字符串，既节约内存又大幅简化了状态比对的复杂度。
状态哈希：使用unordered_map建立从当前状态字符串到初始状态距离的键值对映射d，完美兼顾了距离记录与判重拦截功能。

②队列初始化与主循环：

源头注入：将起始字符串s通过q.push(s)压入队列，并初始化d[s]=0确立零步基准。
循环屏障：通过while(q.size())维持探索，利用string t=q.front()取出队头并在q.pop()后立即检查if(t==end)，若命中则果断终止搜索并返回步数。

③坐标转换与四向扩展：

一二维映射：定位'x'的一维下标 $k$ 后，利用除法 $k / 3$ 提取行号，利用取模 $k % 3$ 提取列号，巧妙还原其真实的二维物理属性。
越界拦截：在遍历四个正交方向后，通过if(a>=0&&a<3&&b>=0&&b<3)严防空格移出 $3 \times 3$ 的虚拟九宫格边界。

④状态转移与现场恢复：

字符交换：通过swap(t[k],t[a*3+b])将二维位移重新折叠回一维索引，物理改变字符串形貌生成全新盘面。
入队查重：利用!d.count(t)拦截已经被搜索过的废弃盘面，仅对全新状态执行距离加法d[t]=distance+1并送入队列。
状态回溯：紧跟其后的第二次swap是核心细节，负责将盘面复原，保证同一层级的四个方向分支均是基于同一个父状态独立衍生的。

2.题目

（1）844. 走迷宫 - AcWing题库

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

const int N=100+10;

int g[N][N],d[N][N];
int n,m;

typedef pair<int,int> pii; //因为同时要存x和y所以开一个pair

void bfs(int a,int b)
{
    queue<pii> q;
    q.push({a,b}); //先让a和b进队列
    while(!q.empty()) //因为只要能执行下去队列就会一直非空，约等于递归的作用
    {
        pii start=q.front(); //定义start为队列头节点
        q.pop(); //将用到的头节点出队列，也代表开始运算
        int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0}; //定义上下左右，dx和dy是一一对应的·不能搞错
        
        for(int i=0;i<4;i++) //通过循环测试上下左右哪里能走
        {
            int x=start.first+dx[i],y=start.second+dy[i]; //定义x和y假定上下左右可以走
            if(g[x][y]==0) //如果能走
            {
                g[x][y]=1; //该节点置1表示已经走过，成为了一个“障碍物”
                d[x][y]=d[start.first][start.second]+1; //移动距离相应加1
                q.push({x,y}); //此时走到了x,y这个新节点里，所以让他进队列
            }
        }
    }
    
    cout<<d[n][m]; //输出走到重点时已经走过的距离
}

int main()
{
    cin>>n>>m;
    memset(g,1,sizeof(g));
    
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
        }
    }
    
    bfs(1,1);
    
    return 0;
}

（2）845. 八数码 - AcWing题库

#include<iostream>
#include<cstdio>
#include<unordered_map> //这个理解为键值对即可
#include<cstring>
#include<queue>

using namespace std;

int bfs(string s)
{
    string end="12345678x"; //将二位字符串压成一维来做，先定义结果
    queue<string> q; //定义队列（bfs做题必定义队列，必先将输入的内容进行push，然后在while循环里用某个变量表示front，然后pop，处理完后再将处理结果push
    unordered_map<string,int> d; //定义键值对t
    q.push(s); 
    d[s]=0; //初始化输入字符串的距离位0
    int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
    
    while(q.size()) //dfs经典while循环
    {
        string t=q.front(); //用t存储队头元素
        q.pop(); //队头元素出队，代表开始处理
        int distance=d[t]; //用distance表示字符串t的处理距离
        if(t==end)return distance; //如果此时t已经变化为end就输出距离（处理次数，在dfs中相当于根节点到叶结点的距离）
        int k=t.find('x'); //用k存储find函数找出的字符串中x的位置
        int x=k/3,y=k%3; //用/3、%3的形式把一个一维变量用二维表示，比如本来在字符串中下标为8，8/3=2，8%3=2，用二位表示就是(2,2)
        
        for(int i=0;i<4;i++) //依旧经典上下左右遍历
        {
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<3&&b>=0&&b<3) //在不超出3*3的边界的前提下
            {
                swap(t[k],t[a*3+b]); //尝试交换x与其上下左右的数字的位置
                if(!d.count(t)) //如果t没存在过
                {
                    d[t]=distance+1; //说明这个t是一次有效变换（不管好坏）距离+1
                    q.push(t); //经典处理结果入队
                }
                swap(t[k],t[a*3+b]); //回溯：必须要转回原位才能继续上下左右，否则就换位置了
            }
        }
    }
    
    return -1; //如果一直没有return distance说明处理失败，返回-1
}

int main()
{
    string s,c; //定义两个字符串，一个负责读入一个负责存储
    for(int i=0;i<9;i++) //因为8数码固定9位所以直接写死
    {
        cin>>c;
        s+=c;
    }
    
    cout<<bfs(s)<<endl;
    
    return 0;
}

树与图的深度优先遍历

1.思路

树的重心：处理过程中首先利用memset将头节点数组h初始化为 $- 1$ ，并通过构建邻接表的形式利用add函数将读入的 $n - 1$ 条边存为双向边；dfs函数是算法的核心，从任意节点（例如代码中的1）开始向下递归搜索。进入某个节点u后，首先将其状态state[u]置为true以防止回头路。随后遍历其所有连通的相邻节点，若未被访问过，则递归调用dfs(j)计算以j为根的子树大小size。在回溯过程中，累加这些子树大小得到以u为根的总节点数sum，并同步维护当前节点u的所有向下分支中的最大连通块大小res。当遍历完所有子节点后，利用整棵树的总节点数n减去sum，即可得到节点u上方（即父节点方向）的连通块大小，再次与res取最大值，此时的res即为“若删去节点u，剩余各个连通块中节点数的最大值”。最后，利用全局变量ans在所有备选的重心方案中抓取这个最大值的最小值。最终，直接打印输出ans即可得到答案。

sum和res分别负责统计连通块规模与评估最大碎片。sum（初始值为 $1$ ）用于累加包含当前节点u及其所有向下分支的节点总数，它既要作为函数返回值供给父节点继续向上层递归汇总，又要在循环结束后通过推导n-sum来帮助当前节点计算出其“上方连通块”的规模；而res（初始值为 $0$ ）的核心使命是记录“若将节点u物理删除，整棵树分裂出的所有连通块中最大的那一个的节点数”，它在遍历子节点时不断与各个向下子树的规模打擂台提取最大值，最后再与上方连通块n-sum进行终极比较，从而精准锁定以u作为候选重心时所产生的最大破坏力。

①数据结构与建图准备：

邻接表存储：使用h[N]、e[M]、ne[M]与idx模拟链表结构，由于是无向图，边数上限设为 $M = N \times 2$ 。
双向建边：在main函数中读取每一对相连的节点a与b时，必须对称执行add(a,b)与add(b,a)操作。
访问标记：布尔数组state[N]负责记录节点是否被搜索过，这是避免在无向图中出现父子节点间死循环递归的关键。

②搜索起点与局部变量：

零号源头：由于树是全连通的，主函数中直接调用dfs(1)即可顺藤摸瓜遍历完所有节点。
节点计数：每次进入dfs时定义sum=1，代表当前子树至少包含自身这 $1$ 个节点；定义res=0准备记录删除自身后切分出的最大连通块。

③子树递归与回溯统计：

向下探索：在for(int i=h[u];i!=-1;i=ne[i])循环中，通过int j=e[i]取出子节点编号。
拦截校验：通过if(!state[j])判断该相邻节点不是自己的父节点（即尚未访问过）。
递归收集：执行int size=dfs(j)获取该分支的子树规模，并利用sum+=size将其并入总和，同时执行res=max(res,size)打擂台更新当前向下的最大分支。

④上方连通块与全局更新：

向上统计：退出循环后，通过数学推导n-sum精准计算出节点u被拔除后，其上方挂载的连通块大小。
汇总比较：执行res=max(res,n-sum)综合比对上下所有方向的碎片，确定删除节点u产生的最大连通块破坏力。
全局维护：执行ans=min(ans,res)将当前节点u的破坏力与历史记录打擂台，保留破坏力最小的方案，直至递归结束完成求解。

2.题目：846. 树的重心 - AcWing题库

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=100010,M=N*2;

int h[N],e[M],ne[M],idx; //用邻接表（类似于哈希表的形式）存放节点
bool state[N]; //定义bool变量表示状态
int n,ans=N; //最终节点一开始假设的是一个很大的值，实际的n就在0~N的范围内

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int dfs(int u)
{
    state[u]=true; //从u开始做dfs遍历，因为先给其状态设为true表示已经遍历过
    int res=0,sum=1; //定义res为所有子树分支中最大连通块的节点数，sum为以节点u为根的整棵子树（包含u本身）的节点总数
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!state[j])
        {
            int size=dfs(j); //定义size为以j为根节点的子树所包含的节点总数，j=e[i]代表取节点本身，i只是个编号
            sum+=size; //以j为根的树的节点数
            res=max(res,size); //记录最大联通子图的节点数
        }
    }
    
    res=max(res,n-sum); //选择u节点为重心时最大的连通子图节点数
    ans=min(ans,res); //遍历过的假设重心中，最小的最大联通子图的节点数
    return sum;
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof(h)); //初始时另哈希表都为-1表示没有节点无需遍历
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a); //因为bfs是无向边，相当于连接双向边
    }
    dfs(1); //可以从任意节点开始bfs遍历，这里选了1
    
    cout<<ans<<endl;
    return 0;
}

树与图的广度优先遍历

1.思路

图中点的层次：该算法利用广度优先搜索(BFS)在有向无权图上，通过按层扩展在 $O (N + M)$ 时间复杂度内求解从起点 $1$ 到终点 $n$ 的最短路径问题。在处理过程中：首先在main函数中利用memset将邻接表头数组h初始化为 $- 1$ ，并读入 $m$ 条有向边通过add函数构建出图的拓扑结构；bfs函数是算法的核心，借助queue队列结构遵循先进先出原则，从起点 $1$ 开始向外逐层辐射搜索。初始化阶段将距离数组d全部设为 $- 1$ 以充当未访问标记，随后确立起点d[1]=0并将其压入队列。每次进入while循环，取出队头节点t，并通过邻接表for循环遍历其所有相邻出边节点j。若发现d[j]==-1，说明节点j是首次被波及抵达，根据BFS按层遍历的特性，此时经历的必然是最短路径，故立即执行状态转移d[j]=d[t]+1结算距离，并将新节点j送入队尾作为下一层的扩展源。最终，当队列排空(或提前到达终点)后，直接返回d[n]即可得到答案，若终点不可达则会保持 $- 1$ 原貌。

①数据结构与建图准备：

邻接表存储：使用h[N]、e[N]、ne[N]与idx模拟链表结构，负责高效存储图的节点与有向边关系。
距离记录：定义数组d[N]充当双重角色，既负责记录从起点到各节点的实时最短距离，又利用其初始值 $- 1$ 作为节点是否被访问过的判重标记。
单向建边：在读取数据时直接执行add(a,b)建立从a指向b的有向边，摒弃了无向图的双向连边逻辑。

②队列初始化与起点确立：

全局重置：进入bfs后立刻通过memset(d,-1,sizeof(d))将全图节点标记为处于未访问状态。
零号源头：确立起点距离为零即d[1]=0，随后执行q.push(1)将其装入队列q，作为水波纹向外扩张的最初原点。

③按层扩展与状态转移：

循环屏障：while(!q.empty())保证只要还有可达且未向下延伸的节点，扩散就会不断维持运行。
提取队头：利用t=q.front()获取当前处理层级的中心节点，紧跟q.pop()将其移出队列准备运算。
邻接遍历：通过for循环配合i=ne[i]沿链表骨架游走，并利用j=e[i]依次提取出节点t所能直接抵达的下层节点j。

④距离结算与节点入队：

合法校验：核心拦截判断if(d[j]==-1)负责审核节点j是否属于从未被访问过的安全地带，防止走回头路破坏最短路性质。
步数递推：成功进入分支后光速执行d[j]=d[t]+1结算距离，由于图是无权的，新节点的花费严格等于其父节点花费加1。
入队待命：末尾执行q.push(j)将刚被探索的节点j装入队列，等待在后续循环中晋升为新一层的扩展中心，直至全图探索结束并在末尾返回d[n]。

2.题目：847. 图中点的层次 - AcWing题库

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N=100010;

int h[N],e[N],ne[N],idx; //依旧定义邻接表
int d[N]; //定义距离数组
int n,m;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int bfs()
{
    memset(d,-1,sizeof(d)); //初始化所有距离数组为-1
    queue<int> q; //bfs一般都与队列定义挂钩
    d[1]=0; //定义起始点为1，同时他到起始点也就是自己距离为0
    q.push(1); //把1压进队列
    
    while(!q.empty())
    {
        int t=q.front(); //设t为队首元素
        q.pop(); //弹出队首元素表示其参与处理过程中
        for(int i=h[t];i!=-1;i=ne[i]) //依旧邻接表遍历
        {
            int j=e[i]; //依旧另j为当前节点
            if(d[j]==-1) //当j的距离为-1说明j是i的下一个节点但是距离还没计算
            {
                d[j]=d[t]+1; //计算节点j=e[i]的距离，不计算的就还是-1
                q.push(j); //把节点j压入队列
            }
        }
    }
    
    return d[n]; //返回起点到终点的最短距离
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof(h)); //初始化邻接表为-1
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b); //给a和b连接边，因为算距离没有回头路所以是单向边
    }
    
    cout<<bfs()<<endl;
    
    return 0;
}

拓扑排序

1.思路

拓扑排序：该算法利用广度优先搜索(BFS)的思想在有向图上，通过维护各个节点的入度在 $O (N + M)$ 时间复杂度内解决有向无环图(DAG)的拓扑序列问题。在处理过程中：首先在main函数中利用memset将邻接表头数组h初始化为 $- 1$ ，并读入 $m$ 条有向边通过add函数建图，同时核心操作是在每次建边时将终点b的入度记录数组in[b]累加 $1$ ；topsort函数是算法的核心，借助数组q模拟的队列结构，首先遍历所有节点，将初始入度为 $0$ （即没有任何前置依赖）的节点全部压入队尾作为突破口；每次进入while循环，取出队头节点t，并通过邻接表for循环遍历其所有相邻出边节点j。因为节点t已经被处理并移出图外，所以其所有下层相连节点j的入度必须减 $1$ （即in[j]--）。若某节点j的入度在削减后归零，说明其所有前置先决条件均已完成，立刻将其推入队列尾部。由于模拟队列数组q的特性，元素一旦入队便按序排列且不被物理覆盖，因此当循环结束时，若队列中成功收入了全部 $n$ 个节点（即队尾指针tt==n-1），则说明拓扑排序成功，且数组q天然记录了正确的拓扑输出序列；否则说明图中存在环，无解。

①数据结构与建图准备：

邻接表存储：使用h[N]、e[N]、ne[N]与idx模拟链表结构高效存图。
队列与入度：定义q[N]充当静态模拟队列记录处理顺序，in[N]数组是算法灵魂，负责精确量化每个节点的“被依赖次数”。
依赖记录：在main函数读取边集时，对于边a到b，不仅执行add(a,b)建立有向连接，更同步执行in[b]++记录节点b增加了一个前置门槛。

②队列初始化与突破口定位：

队列双指针：在topsort中定义队头hh=0与队尾tt=-1，巧妙利用++tt与hh++控制元素进出。
搜寻起点：通过for(int i=1;i<=n;i++)扫描全图，核心拦截判断if(in[i]==0)负责精准捞出所有零依赖的初始节点，并执行q[++tt]=i让它们率先入队启动连锁反应。

③按层剥离与入度动态削减：

循环屏障：while(hh<=tt)维持着“取出节点-削减下层依赖-新节点入队”的循环生态，只要还有新入度归零的节点产生就持续运行。
依赖解除：通过int t=q[hh++]取出并剥离当前安全节点后，沿邻接表找到所有受其制约的下属节点j=e[i]，并立刻执行in[j]--宣告它们的一个前置条件已达成。

④连锁入队与成环判定：

状态跃迁：紧跟削减操作后的if(in[j]==0)负责监控下属节点状态，一旦发现某个节点的前置依赖被彻底清空，光速执行q[++tt]=j将其送入队列。
终局裁定：循环结束后通过return tt==n-1进行最终验收，若指针tt推进到了 $n - 1$ 说明所有 $n$ 个节点均已顺利剥离入队，此时q中按先后顺序存放的即为拓扑序列；反之若提前卡死则判定图中包含死循环环路。

2.题目：848. 有向图的拓扑序列 - AcWing题库

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=100010;

int h[N],e[N],ne[N],idx; //依旧邻接表存储树图
int q[N],in[N]; //定义q数组表示模拟队列，in数组表示各节点入度
int n,m;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool topsort()
{
    int hh=0,tt=-1; //定义头为hh，尾为tt，头负责出队尾负责入队
    for(int i=1;i<=n;i++)
    {
        if(in[i]==0)q[++tt]=i; //先初始化队列，把入度为0的节点加入队列，因为节点是1~n所以循环从1开始
    }
    while(hh<=tt) //当队头小于等于队尾表示出队元素的数量小于等于入队元素的数量，表示队列不为空
    {
        int t=q[hh++]; //定义t为头元素，hh++表示令其出队
        for(int i=h[t];i!=-1;i=ne[i]) //邻接表遍历边
        {
            int j=e[i];
            in[j]--; //因为已经出队，所以i的下一个节点j的入度-1
            if(in[j]==0)q[++tt]=j; //如果入度-1后为0，则令其入队
        }
    }
    
    return tt==n-1; //因为tt从-1开始，所以与n-1作比较，相等则说明拓扑排序成立
}   

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h); //一定要记得初始化哈希散列表
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        in[b]++; //每加一条边，边的指向节点b入度+1
    }
    if(topsort())
    {
        for(int i=0;i<n;i++)printf("%d ",q[i]); //q的顺序即是入队顺序，同时也是拓扑排序的顺序
    }
    else cout<<-1<<endl;
    
    return 0;
}

基础算法（一）

快速排序

归并排序

二分

整数二分

浮点数二分

基础算法（二）

高精度

高精度加法

高精度减法

高精度乘法

高精度除法

前缀和与差分

一维前缀和

二维前缀和

一维差分

二维差分

基础算法（三）

双指针算法

位运算

离散化

区间合并

数据结构（一）

单链表

双链表

栈

队列

KMP

数据结构（二/三）

Trie树：以树结构存储字符串、数字串等

并查集

堆

哈希表

STL容器

vector向量/pair<变量类型1,变量类型2>（存储二元组）

string字符串

queue队列/priority queue优先队列

stack栈

set，map，multiset，multimap

unordered set，unordered map，unordered multiset，unordered multimap

搜索与图论（一）

DFS

BFS

树与图的深度优先遍历

树与图的广度优先遍历

拓扑排序

搜索与图论（二）

访客信息登记

提交成功

算法基础课(持续更新中)

申请友情链接