ACwing—算法基础

AcWing算法基础课学习记录

起因

自学算法确实不能记得很牢啊，学晚不过一年很多基础数据结构都忘了。为了兼顾考研学习花了大价钱149买了y总的算法基础课学习。希望能有不错的收获。虽然叫算法基础课但是其实课程并不是那种数据结构入门的零基础课，许多东西其实都是一般课程里没有的。

基础算法

排序、二分

快速排序
这题不知道为什么我写的就会超时，用模板的就不会，不过都无伤大雅。快排思想就是选择一个对照值将比对照值大的放到一边，比对照值小的放到另一边。

#include<iostream>
using namespace std;
int a[100010];
int n;
void quickSort(int a[],int l,int r)
{
    if(l>=r) return ;
    int i = l-1,j =r+1,k = a[l+r>>1];//注意如果是int i=l,j=r;可能会产生边界问题
    while(i<j)
    {
        while(a[++i]<k);//很关键换成i++可能产生边界问题
        while(a[--j]>k);//查找右半部分比中间数小的数
        if(i<j)
        swap(a[i],a[j]);
    }
    quickSort(a,l,j);
    quickSort(a,j+1,r);
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    quickSort(a, 0, n - 1);
    for(int i = 0; i < n; i++){
        cout << a[i] << " ";
    }
    return 0;
}

第k个数
其实就是加了个输出而已

#include <iostream>

using namespace std;

const int N = 1000010;

int q[N];

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

    int i = l - 1, j = r + 1, x = q[l + 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,m;
    cin>>n>>m;

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    cout<<q[m-1];

    return 0;
}

归并排序
归并的思想就是分治，将大问题换成等分的小问题再来解决处理

#include<iostream>
using namespace std;
int q[1000005];
void Merge_sort(int a[],int l,int r)
{
    if(l>=r) return;
    int mid =(l+r)/2;
    Merge_sort(a,l,mid);//递归分为不同等分组
    Merge_sort(a,mid+1,r);
    
    int i =l,k=0,j =mid+1;
    while(i<=mid&&j<=r)
    {
        if(a[i]<a[j])
        {
            q[k] = a[i];
            i++;
        }else
        {
            q[k] =a[j];
            j++;
        }
        k++;
    }
    while(i<=mid) q[k++] =a[i++];//当一组还有剩余另一组已经为空的时候直接将剩余的加到排序队里就好了
    while(j<=r) q[k++] =a[j++];
    for(j = 0, i = l; i <= r; j++, i++) a[i] = q[j];
}
int main()
{
    int n,a[1000005];
    cin>>n;
    for(int i =0;i<n;i++) cin>>a[i];
    Merge_sort(a,0,n-1);
    for(int i =0;i<n;i++) cout<<a[i]<<" ";
    return 0;
}

逆序对的数量
用了归并排序来查找逆序对

#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;
int a[1000010];
long long ans=0;
void merge_sort(int a[],int l,int r)
{
    if(l>=r) return;
    int mid =(l+r)/2;
    merge_sort(a,l,mid);
    merge_sort(a,mid+1,r);//排序是为了查找时更加方便
    int tmp[r - l + 1];
    int i =0,j =l,k =mid+1;
    while(j<=mid&&k<=r)
    {
        if(a[j]<=a[k]) tmp[i++] = a[j++];
        else
        {
            tmp[i++] = a[k++];
            ans+=(mid-j+1);//这里表示如果大组的A数与小组其中一个数符合逆序意味着A数与小组所有数都能组成逆序对
        }
    }
    while(j<=mid) tmp[i++] =a[j++];
    while(k<=r) tmp[i++] = a[k++];

    for(int x =l,y = 0;x<=r;x++,y++)
    {
        a[x] = tmp[y];
    }
    
}
int main()
{   
    int n;
    cin>>n;
    for(int i =0;i<n;i++)
    cin>>a[i];
    merge_sort(a,0,n-1);
    cout<<ans;
    return 0;
}

数的范围

这题思路是用两个二分分别开始和结尾

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    while (m -- )
    {
        int x;
        scanf("%d", &x);

        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }

        if (q[l] != x) cout << "-1 -1" << endl;
        else
        {
            cout << l << ' ';

            int l = 0, r = n - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }

            cout << l << endl;
        }
    }

    return 0;
}

数的三次方
这种题用二分能优化时间复杂度到Olngn，y总的这种写法更是简洁

#include<iostream>
using namespace std;

int main()
{
double n;
cin>>n;
double l =-10000,r =10000;
while(r - l>1e-8)//这个1e-8是控制精度用的
{
double mid =(l+r)/2;
if(mid*mid*mid>=n) r =mid;
else l =mid;
}
printf("%1f\n",l);
return 0;
}

高精度

高精度简而言之就是高位数字之间的运算，细节就是用数组储存每一位数字方便运算，注意从个位数到高位依次放在数组的首位到末位。如123456在数组中是(6、5、4、3、2、1)的样式储存

高精度加法

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);
    return c;
}
int main()
{
    vector<int> a,b;
    string c,d;
    cin>>c>>d;
    for(int i =c.size()-1;i>=0;i--) a.push_back(c[i]-'0');//数组首位放的是数字的个位，方便位数变大好进位
    for(int i =d.size()-1;i>=0;i--) b.push_back(d[i]-'0');
    
    auto ans = add(a,b);
    
    for(int i =ans.size()-1;i>=0;i--) cout<<ans[i];
    return 0;
    
    
}

高精度减法

#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;
bool cmp(vector<int>&a,vector<int>&b)
{
    if(a.size()!=b.size()) return a.size()>b.size();
    
    for(int i = a.size(); i >= 0; i--)
        if(a[i] != b[i])
            return a[i] > b[i];
    
    return true;
}
vector<int> add(vector<int>&a,vector<int>&b)
{
    vector<int>c;
   
    for(int i =0,t =0;i<a.size()||i<b.size();i++)
    {
        t = a[i]-t;
        if(i<b.size())  t-=b[i];
        c.push_back((t+10)%10);//这个相当于运算了t-b[i]后的情况，如果t>=0则运算后还是 == t的值，否则就是10-t后的值
        if(t<0) t =1;
        else t =0;
    }
    //if(t) c.push_back(1);
    while(c.size() > 1 && c.back() == 0) c.pop_back();  //去掉前导0
    return c;
}
int main()
{
    vector<int> a,b;
    string c,d;
    cin>>c>>d;
    for(int i =c.size()-1;i>=0;i--) a.push_back(c[i]-'0');//数组首位放的是数字的个位，方便位数变大好进位
    for(int i =d.size()-1;i>=0;i--) b.push_back(d[i]-'0');
    
 if (cmp(a,b)) 
    {
        auto C = add(a, b);
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);
        return 0;
    }
    else
    {
        auto C = add(b, a);
        printf("-");
        for(int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);     
    }

    
    return 0;
    
}

高精度算法

#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;

vector<long long> mul(vector<long long>&a,int b)
{
    vector<long long>ans;
    int t =0;
    for(int i = 0;i<a.size()||t;i++)
    {
        if(i<a.size()) t += a[i]*b;
        ans.push_back(t%10);
        t/=10;
    }
    for(int i =ans.size()-1;i>0;i--) 
    {
        if(ans[i]==0) ans.pop_back();
    }
    return ans;
}
int main()
{
    vector<long long> a;
    string c;
    int d;
    cin>>c>>d;
    for(int i =c.size()-1;i>=0;i--) a.push_back(c[i]-'0');//数组首位放的是数字的个位，方便位数变大好进位
    auto ans = mul(a,d);
   
    for(int i =ans.size()-1;i>=0;i--) cout<<ans[i];
 
    
    return 0;
    
}

高进度除法

#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;

vector<int> mul(vector<int>&a,int b,int &r)//r是余数
{
    vector<int>ans;
    for(int i = a.size()-1;i>=0;i--) //与其他不同除法从高位开始算
    {
        r = r*10+a[i];
        ans.push_back(r/b);
        r%=b; 
    }
    reverse(ans.begin(),ans.end());
    while(ans.size()>1&&ans.back()==0) ans.pop_back();
    
    return ans;
}
int main()
{
    vector<int> a;
    string c;
    int d;
    cin>>c>>d;
    for(int i =c.size()-1;i>=0;i--) a.push_back(c[i]-'0');//数组首位放的是数字的个位，方便位数变大好进位
    int r = 0;
    auto ans = mul(a,d,r);
   
    for(int i =ans.size()-1;i>=0;i--) 
    cout<<ans[i];
    
    cout<<endl<<r<<endl;
 
    
    return 0;
    
}

前缀和

前缀和——假如原数组: a[1], a[2], a[3], a[4], a[5], …, a[n]；前缀和 Si为数组的前 i项和；即前缀和: S[i] = a[1] + a[2] + a[3] + … + a[i]
前缀和可以在O(1)的时间复杂度下求出范围内的数目之和，前提是经过On的数组遍历
注意：前缀和下标从1开始，s[0]=0

前缀和

#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;
const int N =1000010;
int n,m;
int s[N],a[N];

int main()
{
    cin>>n>>m;
    for(int i =1;i<=n;i++)
    cin>> a[i]; // scanf比cin快一倍，比赛技巧
    for(int i =1;i<=n;i++) s[i] = s[i-1]+a[i];//构建前缀和数组

    while(m--)
    {
        int l ,r;
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}

二维矩阵也可以使用前缀和减去s[i-1,j-1]是因为两次相加后会多出一份重复的s[i-1,j-1]，故需要减去一次

#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;
const int N =1010;//不能开太大否则报错Error: value of 000003a35758f6b3 too large for field of 4 bytes at 00000000000000f3
int n,m,q;
int a[N][N],s[N][N];

int main()
{
    cin>>n>>m>>q;
    for(int i =1;i<=n;i++)
        for(int j =1;j<=m;j++)
            cin>>a[i][j];
    
     for(int i =1;i<=n;i++)
        for(int j =1;j<=m;j++)
            s[i][j] = s[i][j-1]+s[i-1][j] - s[i-1][j-1]+a[i][j];//固定公式,但也需要理解
    
    while(q--)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        int res = s[x2][y2]-s[x1-1][y2]- s[x2][y1-1]+s[x1-1][y1-1];
        cout<<res<<endl;
    }
    return 0;
}

差分

差分也很巧妙啊，就是利用前缀和在O1复杂度内使某一段范围全部加上某个数字。
即设范围l~r，从第l项开始是数组全部加x，再对第r个以后的数组全部减x就完成了某一段值加x的操作了。

#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;
const int N =100010;
int n,m,q;
int a[N],b[N];

void insert(int l,int r,int x)//相当于标记了从哪里开始加x，从哪里后开始减去x
{
    b[l]+=x;
    b[r+1]-=x;
}
int main()
{
    cin>>n>>m;
    for(int i  = 1;i<=n;i++)
        cin>>a[i];
    for(int i =1;i<=n;i++)
        insert(i,i,a[i]);
    
    while(m--)
    {
        int l,r,x;
        cin>>l>>r>>x;
        insert(l,r,x);
    }
    for(int i = 1;i<=n;i++) b[i]+=b[i-1];
    for(int i = 1;i<=n;i++) cout<<b[i]<<" ";

    return 0;
    
}

大佬的极简写法,Acwing加强数据后能过

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,a,b,c,f[1010100]={},s[10101010]={};
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>f[i],s[i]=f[i]-f[i-1];
    while(m--)cin>>a>>b>>c,s[a]+=c,s[b+1]-=c;
    for(int i=1;i<=n;i++)f[i]=f[i-1]+s[i],cout<<f[i]<<" ";
}

二维差分和二维前缀和差不多，只是处理方向相反，具体点击其他大佬详解思想还是得看图来的快一些

#include<iostream>
#include<bits/stdc++.h>//万能头文件
using namespace std;
const int N =1010;
int n,m,q;
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()
{
    cin>>n>>m>>q;
    for(int i =1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            {
                cin>>a[i][j];
                insert(i,j,i,j,a[i][j]);
            }
    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++)
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
     for(int i =1;i<=n;i++)
        {
            for(int j = 1;j<=m;j++)
            cout<<b[i][j]<<" ";

            cout<<endl;
        }

    return 0;
    
}

双指针

复杂度O(n)
代码模板

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

最长连续不重复子序列

#include<iostream>
using namespace std;

int main()
{
    int n,a[1000010],s[1000010];
    cin>>n;
    for(int i =0;i<n;i++) cin>>a[i];
    int ans = 0;
    for(int i =0,j =0;i<n;i++)
    {
        s[a[i]]++;//记录当前数字，一旦出现2说明重复了
        while(s[a[i]]>1)
        {
            s[a[j]]--;//将j踢出记录数组并往前移动j
            j++;
        }
        ans = max(ans,(i-j+1));
    }
    cout<<ans;
    return 0;
}

数组元素的目标和
双指针，一个从小到大匹配，另一个从大到小匹配

int n,m,x;
    cin>>n>>m>>x;
    int a[100010],b[100010];
    for(int i =0;i<n;i++) cin>>a[i];
    for(int i =0;i<m;i++) cin>>b[i];
    for(int i =0,j = m-1;i<n;i++)
    {
        while(j>=0&& a[i]+b[j]>x) j--;
        if(j>=0&&a[i]+b[j]==x) cout<<i<<" "<<j<<endl;
    }

判断子序列
常规双指针

#include<iostream>
using namespace std;
int a[1000010],b[1000010];
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 l=0,r=0,flag= 0;
    while(r<m)
    {
        if(a[l]==b[r])
        {     
            l++;
            r++;
            //cout<<flag<<endl;
            if(l==n)
            {
                flag=1;
                break;
            }
        }else
        r++;
        
    }
    if(flag)
    cout<<"Yes";
    else cout<<"No";
    
            
    return 0;
}

位运算

位运算就是直接对整数在内存中的二进制位进行运算
C++ 提供了按位与（&）、按位或（| ）、按位异或（^）、取反（~）、左移（<<）、右移（>>）这 6 种位运算符

二进制中1的个数
使用lowbit操作，进行，每次lowbit操作截取一个数字最后一个1后面的所有位，每次减去lowbit得到的数字，直到数字减到0，就得到了最终1的个数。
lowbit原理
根据计算机负数表示的特点，如一个数字原码是10001000，他的负数表示形式是补码，就是反码+1，反码是01110111，加一则是01111000，二者按位与得到了1000，就是我们想要的lowbit操作

#include<iostream>
using namespace std;
int a[1000010];
int lowbit(int x)
{
    return x &- x;
}
int main()
{
    int n;
    cin>>n;
    
    for(int i = 0;i<n;i++)
    {
        cin>>a[i];
        int res = 0;
        while(a[i])
        {
            a[i]-=lowbit(a[i]);
            res++;
        }
        cout<<res<<" ";
    }
   
  
    
            
    return 0;
}

离散化

离散化本质上是一种哈希，它在保持原序列大小关系的前提下把其映射成正整数。
其实算法本质不难的，就是以大化小，然后再用其他方法如前缀和去更好的解决问题。
算法模板如下：

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

区间和

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>

using namespace std;
const int N =3000010;
int n,m;
int a[N];//存储坐标插入值
int s[N];//存储a的前缀和
vector<int> alls;//存储坐标
vector<pair<int,int>> add,query;//存储插入和询问操作的数据

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;
        else l = mid + 1;
    }
    return r+1;
}
int main()
{
    cin>>n>>m;
    for(int i =1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        add.push_back({x,y});
        alls.push_back(x);
    }
    for (int i = 1; i <= m; i++) {
        int l , r;
        cin>>l>>r;
        query.push_back({l, r});
        alls.push_back(l);
        alls.push_back(r);
    }
    //排序去重
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());
     //执行前n次插入操作
    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];
    //处理后m次询问操作
    for (auto item : query) 
    {
        int l = find(item.first);
        int r = find(item.second);
        cout<<s[r]-s[l-1]<<endl;
       
    }
    
    return 0;
}

区间合并

顾名思义就是把有交集的区间合并为一个
模板

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

区间合并
这题倒是不算少见，之前用贪心做过

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>

using namespace std;
const int N =1000010;
vector<pair<int,int>> a;
vector<pair<int,int>> merge(vector<pair<int,int>>& a)
{
    vector<pair<int,int>> res;
    sort(a.begin(),a.end());
    int l = -2e9,r = -2e9; //设置边界参照
    for(auto i:a)
    {
        if(r<i.first)//说明找到了一个新的区间
        {
            if(l != -2e9) res.push_back({l,r});
            l = i.first;
            r = i.second;
        }
        else
        {
            r = max(r,i.second);
        }
    }
    if(l!=-2e9) res.push_back({l,r});
    return res;
}
int main()
{
    int n;
    cin>>n;
    for(int i =0;i<n;i++)
    {
        int l,r;
        cin>>l>>r;
        a.push_back({l,r});
    }    
    auto res = merge(a);
    cout<<res.size()<<endl;
    return 0;
}

数据结构

算法题目里面一般不会用到构造的数据结构，new用起来太慢了在笔试中容易超时，因此还是使用模拟的方法来实现数据结构算法。

单链表

单链表用的最多的是写邻接表—邻接表是图的一种链式存储方法，其数据结构包括两部分：节点和邻接点。多用于存储图和树，记得在树结构中这个属于图的范围。
双链表用来最多的是优化某些问题

单链表
静态链表使用数组来模拟是因为写起来方便，效率也比new 快了将近100倍

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>

using namespace std;
const int N =1000010;
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;
// 初始化
void init()
{
    head = -1;
    idx = 0;
}
// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a,ne[idx] =head,head = idx,idx++;
}
//将x插入到下标为k的点的后面
void add(int k, int x)
{
    e[idx] =x;
    ne[idx] = ne[k];
    ne[k] =idx;
    idx++;
}
//将下标是k的点后面的点个删掉
void remove(int k){
    ne[k] = ne[ne[k]];//让k的指针指向，k下一个人的下一个人，那中间的那位就被挤掉了。
}
int main()
{
    int n;
    cin >> n;
    init();//初始化
    for(int i =0;i<n;i++)
    {
        char s;
        cin>>s;
        if(s =='H')
        {
            int x;
            cin>>x;
            insert(x);
        }
        else if(s=='D')
        {
            int x;
            cin>>x;
             if (x == 0) head = ne[head];//删除头节点
            else remove(x - 1);//注意删除第k个输入后面的数，那函数里放的是下标，k要减去1
        }
        else if(s=='I')
        {
             int k, x;
            cin >> k >> x;
            add(k - 1, x);//同样的，第k个数，和下标不同，所以要减1
        }
    }
    for(int i = head; i != -1; i = ne[i]) cout<<e[i]<<" ";
    cout<<endl;
    return 0;
}

双链表

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>

using namespace std;
const int N =100010;
// head存储链表头，e[]存储节点的值，l[]存储前驱地址，r[]存储下一个地址，idx表示当前指针
//双指针要记住假设当前节点为p,则l[p]表示p的前驱节点位置，l[r[p]]表示p->next->pre的意思
int e[N], l[N], r[N],idx= 0;
// 初始化
void init()//没加头节点了
{
    l[1] = 0;
    r[0] =1;
    idx =2;
}
//将x插入到下标为k的点的后面
void add(int k, int x)
{
    e[idx] =x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;//让原本k左边的前驱节点指向idx
    r[k] =idx;
    idx++;
}
//将下标是k的点后面的点个删掉
void remove(int k){
    r[l[k]] = r[k];//k->pre->next = p->next;
    l[r[k]] = l[k];//k->next->pre = p->pre;
}
int main()
{
    int n;
    cin >> n;
    init();//初始化
    for(int i =0;i<n;i++)
    {
       string op;
        cin >> op;
        int k, x;
        if(op == "L")
        {
            cin >> x;
            add(0, x);
        }
        else if(op == "R")
        {
            cin >> x;
            add(l[1], x);
        }
        else if (op == "D")
        {
            cin >> k;
            remove(k + 1);//第 k 个插入元素对应的索引为 k + 1
        }
        else if (op == "IL")
        {
            cin >> k >> x;
            add(l[k + 1], x);// 第 k 个插入元素对应的索引为 k + 1， l[k + 1] 为链表中上一个位置对应的索引
        }
        else
        {
            cin >> k >> x;
            add(k + 1, x);//第 k 个插入元素对应的索引为 k + 1
        }
    }
    for(int i = r[0]; i != 1; i = r[i]) cout<<e[i]<<" ";
    cout<<endl;
    return 0;
}

栈

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>

using namespace std;
const int N =1000010;
int stk[N],tt =-1;//栈不难，用一个数组就能模拟了,tt表示栈顶指针
//入栈
void push(int x)
{
    stk[++tt] = x;//不能用tt++
}
//出栈
void pop()
{
    tt--;
}

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

表达式求值

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>

using namespace std;

//存储运算数 运算符
stack<int> num;
stack<char> op;
//建立映射来判断运算优先级
unordered_map<char, int> cmp = {
    {'+', 1}, {'-', 1} , {'*', 2}, {'/', 2}
};
//模拟一次算术操作
void eval(void){
    int b = num.top();  num.pop();
    int a = num.top();  num.pop();
    char opr = op.top();    op.pop();

    int x;
    if(opr == '+')  x = a + b;
    else if(opr == '-') x = a - b;
    else if(opr == '*') x= a * b;
    else    x = a / b;
    num.push(x);
}

int main(){
    string str;
    cin >> str;

    for(int i = 0; i < str.size(); i++){
        char c = str[i];
        //读入运算数
        if(isdigit(c)){
            int j = i, x = 0;
            while( j < str.size() && isdigit(str[j])){
                //j++ 迭代不能忘 
                x = x *  10 + str[j ++] - '0';
            }
            num.push(x);
            //由于每轮循环有i++,我们需要倒指向最后一个数字
            i = j - 1;
        }else if( c == '(' ){
            //标记一下，括号内数据
            op.push(c);
        }else if( c == ')' ){
            //括号的优先级，先算括号
            while( op.size() && op.top() != '(' )   eval();
            //左括号可以弹出
            op.pop();
        }else{
            //得先把乘除法算了再算加减
            //这里必须得带等于号 我们这题都是正整数计算
            // 0 - 5 + 3 
            //如果不算，上式会被错误计算成 -8
            while( op.size() && cmp[op.top()] >= cmp[c])    eval();
            //压入新运算符
            op.push(c);
        }
    }
    //清理低优先级操作
    while(op.size())    eval();
    cout << num.top() << endl;
    return 0;
}

队列

模板

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数,很巧妙，用空间换时间h++就是将队头指针往后移动了，虽然没改变原本队头元素的值，却让队头元素脱离了队列的范围内
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt)
{

}

模拟队列

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>


using namespace std;
const int N =1000010;
int q[N],hh,tt = 0;//hh是队头，tt是队尾
void push(int x)
{
    q[tt++] = x;
}
void pop()
{
    hh++;
}
bool empty()
{
    return tt<=hh;   
}

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

单调栈

//思路清晰，遇到大的就出栈，直至栈空就输出-1
#include<iostream>
using namespace std;

int stk[100010],tt;
int main()
{
    int n;
    cin>>n;
   while(n--)
   {
       int x;
       cin>>x;
       while (tt && stk[tt] >= x) tt -- ;//如果栈顶元素大于当前待入栈元素，则出栈
       if(!tt) cout<<-1<<" ";
       else cout<<stk[tt]<<" ";
       stk[++tt]  =x;
   }
    
    return 0;
}

滑动窗口

#include<iostream>
using namespace std;
const int N =1000010;
int a[N],q[N];//a存放内容，q存放坐标
int n,k;
//单调队列就是要保持最小值一定在队头
int main()
{
    cin>>n>>k;
    for(int i =0;i<n;i++) cin>>a[i];
    int hh =0,tt =-1;
    for(int i =0;i<n;i++)
    {
        if(hh<=tt&&i-k+1>q[hh])
            hh++;//滑动窗口踢出队头
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;//a的值大于i的值时，弹出
        q[++tt] =i;
        if(i>=k-1) cout<<a[q[hh]]<<" ";
    }
    cout<<endl;
    hh = 0,tt = -1;
    for(int i =0;i<n;i++)
    {
        if(hh<=tt&&i-k+1>q[hh])
            hh++;//滑动窗口踢出队头
        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;//a的值大于i的值时，弹出
        q[++tt] =i;
        if(i>=k-1) cout<<a[q[hh]]<<" ";
    }
    return 0;
}

大名鼎鼎的KMP

kmp就是字符串匹配的一种方法，暴力在匹配不成功后需要重头开始匹配，KMP在匹配不成功后会按照相应规则退回到某一位置k，此时k前的字符串一定能匹配成功。
这个是输出字符串匹配的起始位置到末尾位置的

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>


using namespace std;
const int N = 1000010;
string s,p; 
int n,m;
int ne[N];//next数组，kmp的匹配回退数组,表示当前位上字符串相同前缀和后缀最高位数j
//通过位数j可以找到字符串回退的最小位置，假设s在第i位和匹配串的k位匹配失败。
//因为后缀和前缀相同保证了i前j位都一定和p串后缀相等，p串后缀和前缀相等，所以i前j位和p串前缀相等，因此只需退回到ne[k]上然后比较k+1和当前i位即可
//可以看作s串匹配错误的前j位就是和p的后缀相同的前缀

int main()
{
    cin>>n>>p>>m>>s;
    //next数组构造过程
    for(int i = 1,j = 0;i<p.size();i++)
    {
        while(j&&p[i]!=p[j]) j = ne[j];
        if(p[i] ==p[j]) j++;
        ne[j] = i;
    }

    //kmp匹配过程
    for(int i =0,j=0;i<s.size();i++)
    {
        while(j&&s[i]!=p[j]) j = ne[j-1];//不匹配则按规则回退
        if(s[i]==p[j])    j++;
        if(j==n)
        cout<<i-j+1<<" "<<i;  
    }
}

KMP字符串

#include <bits/stdc++.h>

using namespace std;
const int N = 1000010;
//char s[N],p[N]; 
string s,p;
int n,m;
int ne[N];//next数组，kmp的匹配回退数组,表示当前位上字符串相同前缀和后缀最高位数j
//通过位数j可以找到字符串回退的最小位置，假设s在第i位和匹配串的k位匹配失败。
//因为后缀和前缀相同保证了i前j位都一定和p串后缀相等，p串后缀和前缀相等，所以i前j位和p串前缀相等，因此只需退回到ne[k]上然后比较k+1和当前i位即可
//可以看作s串匹配错误的前j位就是和p的后缀相同的前缀

int main()
{
    cin >> n >> p >> m >> s;

    // p[0...0] 的区间内一定没有相等前后缀
    ne[0] = -1;//ne数组里的是下标位置，所以当不存在相同前后缀时为-1

    // 构造模板串的 next 数组
    for (int i = 1, j = -1; i < n; i ++)
    {
        while (j != -1 && p[i] != p[j + 1])
        {
            // 若前后缀匹配不成功
            // 反复令 j 回退，直至到 -1 或是 s[i] == s[j + 1]
            j = ne[j];
        }
        if (p[i] == p[j + 1]) 
        {
            j ++; // 匹配成功时，最长相等前后缀变长，最长相等前后缀最后一位变大
        }
        ne[i] = j; // 令 ne[i] = j，以方便计算 next[i + 1]
    }

    // kmp start !
    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) // 模板串匹配完成，第一个匹配字符下标为 0，故到 n - 1
       {
           // 匹配成功时，文本串结束位置减去模式串长度即为起始位置
           cout << i - j << ' ';

           // 模板串在模式串中出现的位置可能是重叠的
           // 需要让 j 回退到一定位置，再让 i 加 1 继续进行比较
           // 回退到 ne[j] 可以保证 j 最大，即已经成功匹配的部分最长
           j = ne[j]; 
       }
    }

   return 0;
}

Trie字典树

字典树也叫前缀树，典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

Trie字符串统计

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>


using namespace std;
const int N = 1000010;
int idx;
int son[N][26],cnt[N];//son记录字母，cnt记录单词出现数量
char str[N];
void insert(char 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];
    }
    cnt[p]++;
}
int query(char 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];
    }
    return cnt[p];
}
int main()
{
    int n; cin>>n;
    while (n--) {
        string op; cin>>op>>str;
        if (op[0] == 'I') insert(str);
        else cout<<query(str)<<endl;
    }
    return 0;
}

最大异或对

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>


using namespace std;
const int N = 1000010,M = N*30;
int idx;
int son[M][2],cnt[N];//son记录字母，cnt记录单词出现数量
void insert(int x)
{
    int p =0;
    for(int i=30;i>=0;i--)
    {
        int u = x>>i&1;//取X的第i位的二进制数是什么
        if(!son[p][u]) son[p][u] =++idx;//不能++idx,否则导致第一轮为0
        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])//如果当前层有对应的不相同的数,p就指向当前层数其他位置
        {
            p = son[p][!u];
            res=res*2+1;
        }else
        {
            p = son[p][u];
            res = res*2+0;
        } 
    }
    return res;
}
int main()
{
    
    int n;
    cin>>n;
    idx=0;
    for(int i=0;i<n;i++)
    {
        cin>>cnt[i];
        insert(cnt[i]);
    }
    int res=0;
    for(int i=0;i<n;i++)
    {   
        res=max(res,query(cnt[i]));  ///search(a[i])查找的是a[i]值的最大与或值
    }
    cout<<res<<endl;
    return 0;
}

并查集

并查集是用来管理元素分组的算法。并查集可以高效的对元素进行分组（合并在一起），并且能快速的查询两个元素是否属于同一组。当许多组元素需要合并在一起时，只需将各组元素的老大合并在一起即可，也就是让其中一个根指向另一个根，就使得两棵树合并成了一棵树，也就把两个组合并为了一个组。当我们要查询两个元素是否属于同一个组时，我们需要沿着各个节点往上向树的根进行查询，如果最终发现两个元素的根相同，那么他们就属于同一个组。反之，则不属于同一个组。并查集还有路径压缩的优化—将查询到的集合直接指向根节点，下次查询时只需O(1)的复杂度即可

模板

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);


(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

合并集合

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>


using namespace std;
const int N = 1000010,M = N*30;
int p[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 = 1;i<=n;i++)
    p[i] = i;
    
   while(m--)
   {
    string op;
    int a,b;
    cin>>op>>a>>b;
    cout<<op<<endl;
    if(op=="M")
    {
        p[find(a)]  =find(b);//合并树
    }else
    {
        if(find(a)==find(b))
        cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }

   }
   return 0;


}

连通块中点的数量)

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>


using namespace std;
const int N = 1000010,M = N*30;
int p[N], p_size[N];//size存放的是根节点相同的点的数目

int find (int x)
{
    if(p[x]!=x) p[x] =  find(p[x]);//压缩节点,很漂亮的递归操作,不符合条件就往上找
    return p[x];//只用根节点的值才会等于x
}
int main()
{
    
   int n,m;
   cin>>n>>m;
   for(int i = 1;i<=n;i++)
   {
       p[i] = i;
       p_size[i] = 1;
   }
    
   while(m--)
   {
    string op;
    int a,b;
    cin>>op;
    //cout<<op<<endl;
    if(op=="C")
    {
        cin>>a>>b;
        if(find(a)==find(b)) continue;//特判，如果根节点一样就不操作
        p_size[find(b)]+=p_size[find(a)];//更新连通块中点的数目
        p[find(a)]  =find(b);//合并树
    }else if(op=="Q1")
    {
        cin>>a>>b;
        if(find(a)==find(b))
        cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }else
    {
        cin>>a;
        cout<<p_size[find(a)]<<endl;
    }

   }
   return 0;


}

食物链
很有含金量的一题

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>


using namespace std;
const int N = 1000010,M = N*30;
int p[N],d[N];
int find (int x)//三类环形，因此可以使用到根节点的距离来判断类别，模0是同类，模1吃模0的，模2吃模1的，模0吃模2的
{
    if(p[x]!=x)//p[x]里装的是父节点
    {
        int t = find(p[x]);//找到根节点
        d[x] += d[p[x]];//d[x]表示到父节点的距离，加上父节点到根节点的距离
        p[x] = t;//压缩
    }
    return p[x];
}
int main()
{
    
   int n,m,res=0;
   cin>>n>>m;
   for(int i = 1;i<=n;i++)
    p[i] = i;
    
   while(m--)
   {
    int op;
    int a,b;
    cin>>op>>a>>b;
    if(a>n||b>n) res++;
    else
    {
        int px = find(a), py = find(b);
        if(op==1)
        {
            if(px==py&&(d[a]-d[b])%3)//距离之差模3存在说明不是同类
            res++;
            else if(px!=py)//不是同一个块就合并
            {
                p[px] = py;//将x合并到y中
                d[px] = d[b] - d[a];
            }
            
        }else
        {
            if(px==py&&(d[a] - d[b] - 1) % 3)//距离之差多一相当于a吃b，所以减去1模3后存在就不是a吃b的关系了
            res++;
            else if (px != py)
                {
                    p[px] = py;
                    d[px] = d[b] + 1 - d[a];
                }
        }   
        
    }
    
   }
   cout<<res;
   return 0;


}

堆

堆就是一棵完全二叉树，用数组储存。根节点一定比左右节点大或小。
根节点为x，则2x为左儿子，2x+1是右儿子
模板

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    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 (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

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

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);//可以用错位相减来推断时间复杂度
//因为是完全二叉树，所以n/2开始代表从第一个非叶子节点开始，类似长满荷花要三十天，有一半荷花的时候是第29天一样

堆排序

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
using namespace std;
const int N = 1000010,M = N*30;
int h[N];
int len;
void down(int x)
{
    int t = x;
    if(x*2<=len&&h[x*2]<h[t]) t = x*2;//如果左节点存子并且数比根节点小更新最小点
    if(x*2+1<=len&&h[x*2+1]<h[t]) t = x*2+1;//同上
    if(t!=x)//如果不满足根节点最小就要让根节点和最小点交换
    {
        swap(h[x],h[t]);
        down(t);
    }
}
int main()
{
    
   int n,m;
   cin>>n>>m;
   len = n;
   for(int i =1;i<=n;i++)
   cin>>h[i];
   for(int i =n/2;i>0;i--)
   down(i);
   while(m--)
   {
    cout<<h[1]<<" ";
    //删除头节点—将尾节点覆盖再down更新一遍后删除尾节点即可
    h[1] = h[len];
    len--;
    down(1);

   }
   return 0;
}

模拟堆)

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>


using namespace std;
const int N = 1000010,M = N*30;
int h[N],ph[N],hp[N];//ph和hp互为映射，ph[k] = i来指明，第k个数字在h[]中对应的i是多少,即ph存放的是在堆中的下标
//但是对于ph[k_1] = a和ph[k_2] = b来说，a和b是它们存放的值，不能通过值来找下标，也就是找不k_1,k_2是多少，于是引入hp[a] = k_2，hp[b] = k_2，则可以实现反向的操作
int len;
void heap_swap(int a,int b)//交换要保证存放在堆中的下标和数值索引也一起交换
{
    swap(ph[hp[a]] ,ph[hp[b]]);//交换两个对应ph的值,因为ph[hp[a]]为hp[a] = i，所以ph[k] = i的意思
    swap(hp[a],hp[b]);
    swap(h[a],h[b]);//一般只用交换节点就行，这里是题目要求
}

void down(int x)
{
    int t = x;
    if(x*2<=len&&h[x*2]<h[t]) t = x*2;//如果左节点存子并且数比根节点小更新最小点
    if(x*2+1<=len&&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()
{
    
   int n,m = 0;
   cin>>n;
   while(n--)
   {
    string op;
    cin>>op;
    int k,x;
    if(op == "I")
    {
        cin>>x;
        len++;
        m++;
        ph[m] = len;hp[len] = m;
        h[len] = x;
        up(len);//将插入的数往上移动到合适的位置
    }
    else if(op =="PM")
    {
        cout<<h[1]<<endl;
    }else if(op=="DM")
    {
        heap_swap(1,len);//删除逻辑就是将尾节点覆盖头节点后删除尾节点再重新构建堆，因为尾部好删除
        len--;
        down(1);
    }else if(op=="D")
    {
        cin>>k;
        k = ph[k];
        heap_swap(k,len);
        len--;
        up(k);
        down(k);//down和up二选一自动执行
    }else
    {
        cin>>k>>x;
        k = ph[k];
        h[k] =x ;
        up(k);
        down(k);
    }
   }
   
   
   return 0;

   




}

Hash哈希表

(1) 拉链法
    int h[N], e[N], ne[N], idx;//每个h[i]上都是一个链表，想象成小学按班级排队一样

    // 向哈希表中插入一个数
    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;

        return false;
    }

(2) 开放寻址法
    int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

模拟散列表

//拉链法
#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
#include<cstring>


using namespace std;
const int N = 100003,M = N*30;//100003是有讲究的，100003是100000后第一个质数，这样的远离0的质数可以最小概率引起哈希冲突
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++;//插入后更新h[k]上的链表头指针
}
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;
    }
    return false;
}
int main()
{
    int n,x;
    cin>>n;
    memset(h,-1,sizeof h);//相当于初始化数组所有位为-1
    while(n--)
    {
        string op;
        cin>>op;
        if(op=="I")
        {

            cin>>x;
            insert(x);
        }else
        {
            cin>>x;
            if(find(x))
                cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
#include<cstring>


using namespace std;
//开放寻址法N一般为数据范围的两到三倍，flag是不在范围内的数据用于判断位置是否为空
const int N = 200003,flag = 0x3f3f3f3f;
int h[N];
 // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
    int k =(x%N+N)%N;
    while(h[k]!=flag&&h[k]!=x)
    {
        k++;
        if(k==N)
        k = 0;//走到头了重新开始找
    }
    return k;

    
}
int main()
{
    int n,x;
    cin>>n;
    memset(h,0x3f,sizeof h);//相当于按字节初始化数组所有位为-1
    while(n--)
    {
        string op;
        cin>>op>>x;
        int k = find(x);
        if(op=="I")
        {
            h[k] = x;
        }else
        {
            if(h[k]!=flag)
            cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }
    return 0;
}

字符串哈希
适用于快速判断字符串是否相等的情况

//思路就像设定一个特殊的密码方式一样，例如(12-10)/1 = 2；（12*10-10*10）/1*10 =2一样，故可以判断这两个区间上的值相等
#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
#include<cstring>
using namespace std;
const int N = 1000010,k = 131;//p就是设定好的密码方式，设定为131通常更好
typedef unsigned long long ULL;
int n,m;
char str[N];
ULL h[N],p[N];//如果超过范围就相当于取模了

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    cin>>n>>m>>str+1;
    p[0] = 1;
    for(int i =1;i<=n;i++)
    {
        h[i] = h[i-1]*k+str[i];
        p[i] = p[i-1]*k;
    }
    while(m--)
    {
        int r1,l1,r2,l2;
        cin>>r1>>l1>>r2>>l2;
        if(get(r1,l1)==get(r2,l2))
        cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    
    return 0;
}

搜索与图论

邻接表的模板

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

// 初始化
idx = 0;
memset(h, -1, sizeof h);

DFS

深度优先搜索算法（Depth First Search，简称DFS）：一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(n)。
dfs不具有最短性。

排列数字)

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
#include<cstring>
using namespace std;
const int N = 1000010;
int n;
int path[N];
bool st[N];//判断是否被用过
void dfs(int x)
{
    if(x==n)
    {
        for(int i = 0;i<n;i++)
        cout<<path[i]<<" ";
        cout<<endl;
        return;
    }
    for(int i = 1;i<=n;i++)
    {
        if(!st[i])
        {
        path[x] = i;
        st[i] = true;
        dfs(x+1);
        st[i] =false;//回溯
        }
    }
    
}
int main()
{
    cin>>n;
    dfs(0);
    return 0;
}

n-皇后问题

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
#include<cstring>
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool dg[N],udg[N],col[N];//col是行，dg是从左向右的对角线，udg是从右向左的对角线
void dfs(int x)
{
    if(x==n)
    {
        for(int i =0;i<n;i++)
            puts(g[i]);
        cout<<endl;
    }
    for(int i =0;i<n;i++)
    {
        if(!col[i]&&!dg[x+i]&&!udg[n-x+i])//直线y=x+b-》b = y-x可推，另一条也是，只是为了防止负数加了个n
        {
            g[x][i]='Q';
            col[i] = dg[x+i] = udg[n-x+i] = true;
            dfs(x+1);
            col[i] = dg[x+i] = udg[n-x+i] = false;//回溯
            g[x][i]='.';
        }
    }
    
}
int main()
{
    cin>>n;
    for(int i =0;i<n;i++)
    {
        for(int j =0;j<n;j++)
            g[i][j] = '.';
    }
    dfs(0);
    return 0;
}

//法2
#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
#include<cstring>
using namespace std;
const int N = 10;
int n;
char g[N][N];
bool row[N],dg[N*2],udg[N*2],col[N];//col是列，dg是从左向右的对角线，udg是从右向左的对角线
void dfs(int x,int y,int s)
{
    if(s>n)
    {
        return;
    }
    if(y==n) y=0,x++;
    if(x==n)
    {
        if(s==n)
        {
            for(int i =0;i<n;i++)
            puts(g[i]);
            cout<<endl;
        }
        return;
    }
    g[x][y] = '.';
    //不放
    dfs(x,y+1,s);

    //放
    if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n])
    {
        row[x] = col[y] = dg[x+y] = udg[x-y+n] = true;
        g[x][y] = 'Q';
        dfs(x,y+1,s+1);
        g[x][y] = '.';
        row[x] = col[y] = dg[x+y] = udg[x-y+n] = false;
    }
    
    
}
int main()
{
    cin>>n;
    
    dfs(0,0,0);
    return 0;
}

BFS

走迷宫

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
#include<cstring>
#include<queue>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n, m;
int g[N][N], d[N][N];//g记录题目，d记录是否走过
//bfs的思想就是一层一层扩散，第一个发现答案的自然就是符合要求的最小答案了
int bfs()
{
    queue<PII> q;
    d[0][0] = 0;//开始
    q.push({0,0});
    int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};//方向
    while(q.size())
    {
        auto t= q.front();
        q.pop();
        for(int i = 0;i<4;i++)
        {
            int x =t.first+dx[i],y = t.second+dy[i];
            if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1)//符合条件就往不同方向扩散
            {
                d[x][y] = d[t.first][t.second]+1;
                q.push({x,y});
            }
        }
    }
    return d[n-1][m-1];

}

int main()
{
    
    cin>>n>>m;
    for(int i =0;i<n;i++)
        for(int j =0;j<m;j++)
        {
             cin >> g[i][j];
             d[i][j] = -1;//初始化
        }
    cout<<bfs()<<endl;
    return 0;
}

八数码非常好的一道bfs题，传统的bfs，但是考察了二维坐标到一维坐标的转换，是个很好的算法技巧。

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
const int N = 110;
unordered_map<string,int> cnt;//哈希表保存每一次数据
string s;
queue<string> q;
void bfs()
{
    cnt[s] = 0;
    q.push(s);
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//移动坐标
    while(!q.empty())
    {
        string t = q.front();
        q.pop();
        if(t== "12345678x")
        {
            cout<<cnt[t]<<endl;
            return;
        }
        int now = cnt[t];//取得当前的数据方便修改
        int pos = t.find('x');//获取x的地址
        int a = pos/3,b = pos%3;//转换坐标
        for(int i =0;i<4;i++)
        {
            int x = a+dx[i],y = b+dy[i];//扩散
            if(x>=0&&y>=0&&x<=2&&y<=2)
            {
                swap(t[pos], t[3 * x + y]);//实现字符串中的交换
                if(cnt.find(t)==cnt.end())//如果是一条新的数据就加入到哈希表中
                {
                    cnt[t]= now+1;
                    q.push(t);
                }
                swap(t[pos], t[3 * x + y]);//回溯
            }
        }
    }
    cout<<-1;

}

int main()
{
    for(int i =0;i<9;i++)
    {
        char c;
        cin>>c;
        s+=c;
    }
    bfs();
    return 0;
}

树与图的深度优先遍历

模板

int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

树的重心

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
const int N = 100010, M = N * 2;
int n;
int h[N],e[M],ne[M],idx;
int ans = N;
bool st[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;//h储存的是a这条链表上的头节点，ne存储列表的索引值，e存放数据
    //插入的时候，像链表的头插法一样，e的第idx位存储数据，ne第idx位存放的是第a条链表的头节点，即h[a]，
    //然后更新这条链表上的头节点的下标值即h[a]=idx++；
}
//树的结构输出出来是这样的
// 1:->4->7->2  表示1连着4，7，2这几个结点
// 2:->5->8->1
// 3:->9->4
// 4:->6->3->1
// 5:->2
// 6:->4
// 7:->1
// 8:->2
// 9:->3
int dfs(int u)
{
    st[u] = true;
    int size = 0,sum =1;
    for(int i = h[u];i!=-1;i = ne[i])//找到这条链上的某一点，遍历这条链
    {
        int j = e[i];
        if(!st[j])
        {
        int s = dfs(j);
        size = max(size,s);// 记录最大联通子图的节点数
        sum +=s;//以j为根的树的节点数，用来推出前面断开的总的节点数，因为图的特性就是只有一条前驱多个后继
        //所以除了总数-后继所有的结点数之和等于剩下唯一一个分支的节点总数和
        }
        
    }
    size = max(size,n-sum);
    ans = min(ans,size);
    return sum;
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i =0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);//无向表互联
    }
    dfs(1);
    cout<<ans;
    return 0;
}

树与图的广度优先遍历

图中点的层次

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
const int N = 100010, M = N * 2;
int n,m;
int h[N],e[M],ne[M],idx;

int d[N];//标记用

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;//h储存的是a这条链表上的头节点，ne存储列表的索引值，e存放数据
    //插入的时候，像链表的头插法一样，e的第idx位存储数据，ne第idx位存放的是第a条链表的头节点，即h[a]，
    //然后更新这条链表上的头节点的下标值即h[a]=idx++；
}
//树的结构输出出来是这样的
// 1:->4->7->2  表示1连着4，7，2这几个结点
// 2:->5->8->1
// 3:->9->4
// 4:->6->3->1
// 5:->2
// 6:->4
// 7:->1
// 8:->2
// 9:->3
int bfs()//类似二叉树的层序遍历
{
   memset(d, -1 ,sizeof d);
   queue<int> q;
   d[1] = 0;
   q.push(1);
   while(q.size())
   {
    int t = q.front();
    q.pop();
    for(int i =h[t];i!=-1;i++)
    {
        int j = e[i];
        if(d[j]==-1)
        {
            d[j] = d[t]+1;
            q.push(j);
        }
    }
   }
   return d[n];
}

int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i =0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    
    cout<<bfs();
    return 0;
}

拓扑排序

拓扑排序的实现原理
定义两个辅助数组结构分别用来存放各顶点入度和记录拓扑排序的顶点序号。从第一个无入度的顶点开始，将所有无入度的顶点依次输出并从已有图中摘除，同时将此结点与其他结点所依附的边摘除，最终输出的顶点序列就是拓扑排序序列，此处需要注意的是：有些有向无环图的拓扑排序序列的结果并不唯一
简而言之就是
一个有向图，如果图中有入度为 0 的点，就把这个点删掉，同时也删掉这个点所连的边。
一直进行上面出处理，如果所有点都能被删掉，则这个图可以进行拓扑排序。

bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}

一个有向无环图，一定至少存在一入度为0的点，有鸽巢原理可证，设有n个点单向，若走到第n+1时,则说明必定有一个点重复。

有向图的拓扑序列

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
const int N = 100010, M = N * 2;
int n,m;
int e[N],ne[N],h[N],idx,d[N],q[N];//d[N]用来存储每个点的入度,q[N]是模拟队列

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

bool topsort()
{
    int hh=0,tt=-1;
    for(int i =1;i<=n;i++)
    {
        if(!d[i]) q[++tt] = i;//找到一个度为0的点 
    }
    while(hh<=tt)
    {
        int t = q[hh++];//包含了取队首元素和出队操作
        for(int i =h[t];i!=-1;i = ne[i])
        {
            int j = e[i];
            if(--d[j]==0)//就是删除t指向的数的边，入度也就自动减少了
            q[++tt] = j;//入度为0加入队列
        }
    }
    return tt==n-1;//进过队了就完成了，否则表示出现了环
}


int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i =0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;//入度变化
    }
    if(topsort())
    {
        for(int i = 0;i<n;i++)
        cout<<q[i]<<" ";//排序后结果就是q出队的顺序，由于是数组模拟队列，所以从第一位开始到hh前一位的数据就是答案
        cout<<endl;
    }else cout<<-1;
    return 0;
}

Dijkstra迪杰斯特拉最短路

有点贪心的意思，就是不断找到当前点能到的点里的最小点，再不断重复直到最后就能找到最小路

#include<iostream>
//#include<bits/stdc++.h>//万能头文件
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<stack>
#include<cstring>
#include<queue>
#include<map>
using namespace std;

const int N =510;
int n,m;
int g[N][N];//存放图
int dist[N];//保存源点到其余各个节点的距离
bool st[N];
int dijstra()
{
    memset(dist,0x3f,sizeof dist);//dist一开始所有的值都是无穷，表示没找到最小路
    dist[1]=0;//源点到源点的距离为 0
    for(int i =0;i<n-1;i++)
    {
        int t = -1;
        for(int j =1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||dist[t]>dist[j]))//找到一个未确定最小值且距离离原点最短的点
            t = j;
        }

        for(int j =1;j<=n;j++)//更新找到的点的最小值
            dist[j] = min(dist[j],dist[t]+g[t][j]);

        st[t] = true;
    }
    if(dist[n]==0x3f3f3f3f) return -1;//如果最后值是无穷说明没找到最短路
    else return dist[n];   
}
int main()
{
    cin>>n>>m;
    memset(g, 0x3f, sizeof g);//初始化
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = min(g[a][b],c);//迪杰斯特拉算法不能有负权边，所以最小是0
    }
    cout<<dijstra()<<endl;
    return 0;

}

查找距离最近的点的操作是On次方，可以用堆来优化查找后复杂度降为O1，至此整个可以优化为Omlogn复杂度，m是边数
使用堆优化的迪杰斯特拉算法，直接抄大佬的了

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

using namespace std;

typedef pair<int, int> PII;//堆里存储距离和节点编号

const int N = 1e6 + 10;

int n, m;//节点数量和边数
int h[N], w[N], e[N], ne[N], idx;//邻接表存储图
int dist[N];//存储距离
bool st[N];//存储状态

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

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);//距离初始化为无穷大
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;//小根堆
    heap.push({0, 1});//插入距离和节点编号

    while (heap.size())
    {
        auto t = heap.top();//取距离源点最近的点
        heap.pop();

        int ver = t.second, distance = t.first;//ver:节点编号，distance:源点距离ver 的距离

        if (st[ver]) continue;//如果距离已经确定，则跳过该点
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])//更新ver所指向的节点距离
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});//距离变小，则入堆
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    cout << dijkstra() << endl;

    return 0;
}

Dijkstra求最短路 II)

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>//堆的头文件

using namespace std;

typedef pair<int, int> PII;//堆里存储距离和节点编号

const int N = 1e6 + 10;
int n, m;//节点数量和边数
int h[N], w[N], e[N], ne[N], idx;//邻接矩阵存储图,w是存储权
int dist[N];//存储距离
bool st[N];//存储状态

void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int djs()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    priority_queue<PII,vector<PII>,greater<PII>> heap;//小根堆
    heap.push({0,1});//插入距离和节点
    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second,distance =t.first;//ver:节点编号，distance:源点距离ver 的距离

        if(st[ver]) continue;//已经有确定值了，就跳过
        st[ver] = true;
        for(int i = h[ver];i!= -1;i=ne[i])
        {
            int j = e[i];
            if(dist[j]>dist[ver]+w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j],j});//找到更小的就入堆
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a, b, c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout << djs() << endl;

    return 0;
}

bellman-ford求最短路

基本原理：逐遍的对图中每一个边去迭代计算起始点到其余各点的最短路径，执行N-1遍，最终得到起始点到其余各点的最短路径。（N为连通图结点数）
有边数限制的最短路

#include<iostream>
#include<cstring>

using namespace std;

const int N = 510, M = 10010;

struct Edge { //使用结构体存储边，不用定义一大堆数组去加边
    int a;
    int b;
    int w;
} edges[M];//把每个边保存下来即可
int dist[N];
int back[N];//备份数组防止串联
int n, m, k;//k代表最短路径最多包涵k条边

void bellman_ford() {
    memset(dist, 0x3f, sizeof dist); //dist初始化位无穷，八字节3f3f3f3f大于1e9
    dist[1] = 0;
    for (int i = 0; i < k; i++) {//k次循环
        memcpy(back, dist, sizeof dist);//
        for (int j = 0; j < m; j++) {//遍历所有边，而dijkstra是遍历所有顶点n*n
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], back[a] + w);
            //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
        }
    }
}

int main() {
    cin>>n>>m>>k;
    for(int i =0;i<m;i++)
    {
        int a,b,w;
        cin>>a>>b>>w;
        edges[i] = {a,b,w};
    }
    bellman_ford();
    if(dist[n]>0x3f3f3f3f/2) cout<<"impossible";//避免两点都无穷大，权为其他数字导致最后结果为无穷大-某个数不等于无穷大的情况
    else cout<<dist[n];
    return 0;
    
}

spfa求最短路

spfa求最短路

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

const int N = 100010;
int h[N], e[N], w[N], ne[N], idx;//邻接表，存储图
int st[N];//标记顶点是不是在队列中
int dist[N];//保存最短路径的值
int q[N], hh, tt = -1;//队列

void add(int a, int b, int c){//图中添加边和边的端点
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void spfa(){
    q[++tt]  =1;
    dist[1] = 0;
    st[1] = 1;
    while(tt>=hh)
    {
        int a = q[hh++];
        st[a] = 0;
        for(int i = h[a];i!=-1;i = ne[i])
        {
            int b = e[i],c = w[i];
            if(dist[b]>dist[a]+c)
            {
                dist[b] = dist[a]+c;
                if(!st[b])
                {
                    q[++tt] = b;
                    st[b] =1;
                }
            }
        }
    }
}
int main(){
    memset(h, -1, sizeof h);//初始化邻接表
    memset(dist, 0x3f, sizeof dist);//初始化距离
    int n, m;//保存点的数量和边的数量
    cin >> n >> m;
    for(int i = 0; i < m; i++){//读入每条边和边的端点
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b, w);//加入到邻接表
    }
    spfa();
    if(dist[n] == 0x3f3f3f3f )//如果到n点的距离是无穷，则不能到达 
        cout << "impossible";
    else cout << dist[n];//否则能到达，输出距离
    return 0;
}

Floyd求最短路

简单粗暴

Floyd求最短路)

#include<iostream>
using namespace std;

const int N = 210, INF = 1e9;

int n,m,k;
int d[N][N];
void floyd()
{
    for(int k =1;k<=n;k++)
       for(int i =1;i<=n;i++)
         for(int j=1;j<=n;j++)
            d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
    cin>>n>>m>>k;
    for(int i =1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j) d[i][j] =0;
            else d[i][j] = INF;
    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        d[x][y] = min(d[x][y], z);
    }
    floyd();
    while(k--)
    {
        int a,b;
        cin>>a>>b;
        int t = d[a][b];
        if(t>INF/2) cout<<"impossible"<<endl;
        else cout<<t<<endl;
    }
    return 0;
}

Prim算法求最小生成树

类似迪杰斯特拉算法，采用的都是贪心的思想

Prim算法求最小生成树)

//直接照搬海绵宝宝大佬的题解了，写的很详细

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

const int N = 510;
int g[N][N];//存储图
int dt[N];//存储各个节点到生成树的距离
int st[N];//节点是否被加入到生成树中
int pre[N];//节点的前去节点
int n, m;//n 个节点，m 条边

void prim()
{
    memset(dt,0x3f, sizeof(dt));//初始化距离数组为一个很大的数（10亿左右）
    int res= 0;
    dt[1] = 0;//从 1 号节点开始生成 
    for(int i = 0; i < n; i++)//每次循环选出一个点加入到生成树
    {
        int t = -1;
        for(int j = 1; j <= n; j++)//每个节点一次判断
        {
            if(!st[j] && (t == -1 || dt[j] < dt[t]))//如果没有在树中，且到树的距离最短，则选择该点
                t = j;
        }

        //2022.6.1 发现测试用例加强后，需要判断孤立点了
        //如果孤立点，直返输出不能，然后退出
        if(dt[t] == 0x3f3f3f3f) {
            cout << "impossible";
            return;
        }


        st[t] = 1;// 选择该点
        res += dt[t];
        for(int i = 1; i <= n; i++)//更新生成树外的点到生成树的距离
        {
            if(dt[i] > g[t][i] && !st[i])//从 t 到节点 i 的距离小于原来距离，则更新。
            {
                dt[i] = g[t][i];//更新距离
                pre[i] = t;//从 t 到 i 的距离更短，i 的前驱变为 t.
            }
        }
    }

    cout << res;

}

void getPath()//输出各个边
{
    for(int i = n; i > 1; i--)//n 个节点，所以有 n-1 条边。

    {
        cout << i <<" " << pre[i] << " "<< endl;// i 是节点编号，pre[i] 是 i 节点的前驱节点。他们构成一条边。
    }
}

int main()
{
    memset(g, 0x3f, sizeof(g));//各个点之间的距离初始化成很大的数
    cin >> n >> m;//输入节点数和边数
    while(m --)
    {
        int a, b, w;
        cin >> a >> b >> w;//输出边的两个顶点和权重
        g[a][b] = g[b][a] = min(g[a][b],w);//存储权重
    }

    prim();//求最下生成树
    //getPath();//输出路径
    return 0;
}

动态规划

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

01背包问题)二维写法

#include<iostream>
#include<algorithm>
using namespace std;
const int N= 1005;
int v[N];
int w[N];
int f[N][N];

int main()
{
  int m, n;
  cin >> m >> n;
  for(int i = 1; i <= m; i++)
  {
    cin >> v[i] >> w[i];
  }
  for(int i =1;i<=m;i++)
  {
      for(int j =1;j<=n;j++)
      {
          if(j<v[i])
          {
              f[i][j] = f[i-1][j];
          }
          else f[i][j] =max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
      }
  }
  cout << f[m][n] << endl;

  system("pause");
  return 0;
}

一维写法，注意要从大到小遍历,具体看大佬的解释)

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int w[N], v[N];
int dp[N];

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

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= w[i]; j--)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);

    cout << dp[m] << "\n";

    return 0;
}

完全背包问题)正常dp二维写法

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i =1;i<=n;i++)
    {
        for(int j =1;j<=m;j++)
        {
            f[i][j] = f[i-1][j];//不选
            if(j>=v[i])//选
                f[i][j] =max(f[i-1][j],f[i][j-v[i]]+w[i]);//注意和一维相似但不同。
            
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

具体不同看

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , …..)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2v] + w , f[i-1,j-3v]+2*w , …..)
由上两式，可得出如下递推关系：
f[i][j]=max(f[i,j-v]+w , f[i-1] [j])

一维写法

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
    for(int i =1;i<=n;i++)
    {
        for(int j =v[i];j<=m;j++)
        {
                f[j] =max(f[j],f[j-v[i]]+w[i]);//不用考虑从大到小遍历，因为这里表达式时f[i][j-v[i]],不同于01背包的f[i-1][j-v[i]]
        }
    }
    cout << f[m] << endl;
    return 0;
}

多重背包问题 I)

多重背包问题暴力写法

 
 
#include <iostream>
#include <algorithm>
#define N 110
using namespace std;
 
int n,m;
int v[N],w[N],s[N];
int f[N][N];
int main()
{
    cin>>n>>m;
    for(int i =1;i<=n;i++)  cin>>v[i]>>w[i]>>s[i];
    for(int i =1;i<=n;i++)
        for(int j =1;j<=m;j++)
            for(int k =0;k<=s[i]&&k*v[i]<=j;k++)
                f[i][j] = max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
                
    cout<<f[n][m]<<endl;
    return 0;
}

多重背包问题优化

这个二进制优化思路相当好，原本枚举需要一个一个数，使用二进制的话可以极大降低枚举的次数。如找到1023，一个一个数要1023次，但是从1+2+4+8…+512这么数就只用了常数项次数。

证明：1+2 = 3，可以表示0~3，1+2+4可以表示0~7，1+2+4+8可以表示0~15….

这么做的目的本质上就是压缩查找范围，也就能达到优化的目的了。

#include<iostream>
using namespace std;

const int N = 12010, M = 2010;
int n,m;
int v[N], w[N]; //逐一枚举最大是N*logS
int f[M]; // 体积<M

int main()
{
    cin>>n>>m;
    int cnt = 0; //分组的组别
    for(int i =1;i<=n;i++)
    {
        int a,b,s;
        cin>>a>>b>>s;
        int k =1;// 组别里面的个数
        while(k<=s)
        {
            cnt++;
            v[cnt]=a*k; //整体体积
            w[cnt] = b * k; // 整体价值
            s-=k;
            k*=2;
        }
        if(s)//如果s还有剩余就再加一组
        {
            cnt++;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
        
    }
    n = cnt ; //枚举次数正式由个数变成组别数
    
    //一维01背包优化
    for(int i =1;i<=n;i++)
        for(int j =m;j>=v[i];j--)
            f[j] = max(f[j],f[j-v[i]]+w[i]);
    
    cout<<f[m]<<endl;
    return 0;

}