数据结构与算法

仔细再顺一遍数据结构和算法
输入输出规模超过一百万时考虑使用scanf
出现RE或者Segement Fault 可以逐行删掉代码看看是哪里的问题
如何判断下标从0或1开始：如果下标有i-1的情况，建议从1开始

数组

数组在内存中的存储方式？
- 数组是存放在连续内存空间上的相同类型数据的集合。可以通过下标索引快速获取到对应下标的数据。
- C++中二维数组在地址空间也是连续的
数组的增删？
- 增删复杂，需要移动其它元素的地址
- 数组的元素不能删除，只能覆盖
- C++的vector底层实现是array，它是容器，严格上来说不是数组

常识补充

do while，do中的语句无论是否满足while条件，都会执行一次
l + r >> 1表示右移一位，即除以2向下取整
数据输入规模较大，建议用scanf

基础算法

排序算法

排序算法的稳定性：如果一个序列中右两个一样的值，那么排序后两个相同的值的左右顺序没有发生相对的变化，则是稳定的

快速排序(分治法)

快排模板不能改下标哦

确定分界点(q[l],q[r]或q[(l+r)/2])或随机取
- 分界点取q[l] 则递归时取l,j以及j+1,r j做边界，不能取右边界
- 分界点取q[r] 则递归时取l,i-1以及i,r r做边界，不能取左边界
调整区间：左：所有小于等于x，右：大于等于x
递归处理左右段
【不稳定的，如何变成稳定的？再增加一个信息<value,sub>】

代码：

比较暴力的方法：新开两个数组，扫一遍原来的数组，然后左右合并

不开辟空间的算法：使用双指针

左边指针一直向右扫，直到第一个大于等于x的数出现
右边指针一直向左扫，直到第一个小于等于x的数出现
交换两个指针的内容
两个指针相遇，则排序成功【x放在哪里】
一个问题，如果最后quicksort取
do while好处：即使不满足条件也要至少执行一次

模板：

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    //q：基准
    int i = l - 1, j = r + 1, x = q[l + r >> 1]; //l + r >> 1表示右移一位，即除以2向下取整
    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);   //由于使用dowhile，导致j偏移到本来是i的位置，因此子序列被j分割
}

使用随机化减小时间复杂度

模板(带随机)

#include <iostream>
using namespace std;
const int N=1e6+10;
int n;
int q[N];

void quick_sort(int q[],int l,int r){
    if(l>=r) return;    //区间长度为1，直接返回;l==r也可以
    int x=q[l],i=l-1,j=r+1; //避免do while出现原地不动的情况()
    int rnd_idx = rand() % (r - l + 1) + l; //随机取；如果不随机就去掉交换l
    swap(q[l], q[rnd_idx]);
    while(i<j){
        do i++;while(q[i]<x);//防止死循环，交换后必须要指针前移
        //也可以写成 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(){
    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;
}

应用：快速选择算法求第k小的数

思路1：直接快排再选，nlogn(时间复杂度比较高)
快速选择算法(O(n)):由于快排每次都把数组分为两部分(长度为sl的左半边以及长度为sr的右半边)，如果k<=sl，那么我们应该递归左边；如果k>sl，那么第k小的数一定在右边(是右半边的第k-sl个数)，只需要递归一般边即可，而不必像快排一样两边都递归
时间复杂度分析：n+n/2+n/4+…=n(1+1/2+1/4)<=2n 时间复杂度为O(n)

int quick_findk(int l,int r,int k,int q[]){
    if(l==r) return q[l]; //区间里一定会有数的，不会像快排一样，出现有一个区间是空(l>r)的情况
    int x=q[l],i=l-1,j=r+1;
    while(i<j){
        while(q[++i]<x);
        while(q[--j]>x);
        if(i<j) swap(q[i],q[j]);
    }
    int sl=j-l+1;
    if(k<=sl) return quick_findk(l,j,k,q);
    return quick_findk(j+1,r,k-sl,q);
}

一次递归之后i和j的相对位置：1.i==j 2.i=j+1

归并排序(分治法)

确定分界点mid=(l+r)/2
递归排序产生左、右两个有序数组
归并：合二为一

时间复杂度：O(n(logn))【递归层数】

代码

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];
}

拓展：求逆序对的数量

逆序对的定义如下：对于数列的第i个和第j个元素，如果满足 i<j且a[i]>a[j]，则其为一个逆序对；否则不是。下标小的反而比下标大的大。
解题思路：使用归并排序的思路
1
2
3
1. [L,R]=>[L,mid],[mid+1,R] 2. 递归排序[L,mid]和[mid+1,R] 3. 归并，将左右两个有序序列合并成一个有序序列
所有逆序对可以分为三类：1.两个数同时出现在左半边(merge_sort(L,mid)) 2. 两个数同时出现在右半边(merge_sort(mid+1,R)) 3. 一个数左一个数右(归并的过程，每次归并的时候，记录比r[j]大的数字有sj个，sj=mid-i+1)
题目数据可能会超过int，因此需要用long

long long merge_sort(int l,int r, int q[]){
    if(l>=r) return 0;
    int mid =l+r>>1;
    long long res = merge_sort(l,mid,q)+merge_sort(mid+1,r,q);

    //归并
    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++];//下标大的更小,是逆序对，记录
            res+=mid-i+1;//由于左右两半边均已经有序，这时候mid-i+1范围内的所有数字都比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;
}

二分排序

二分模板注意+1等等地方
有单调性一定可以二分，但可以二分的题目不一定非得有单调性

所谓二分就是找到一个性质，将整个序列二分成为两个边界(边界不重合)

整数二分：
1. 方法一：检查红色部分的性质；查找右边界（动左边界，必须+1防止死循环）
  1. mid=(l+r+1)/2
  2. 检查，如果check(mid)=true：那么答案所在的范围为[mid,r]，下次一就令l=mid
    如果check(mid)=false,那么答案所在的范围为[l,mid-1],下一次就令r=mid-1(mid不满足条件，不需要将其加入)\
  1
  2
  3
  4
  5
  while(l<r){ int mid=l+r+1 >> 1; if(check(mid)) l=mid; else r=mid-1; }
2. 方法二：检查绿色部分性质；查找左边界（动右边界）
  1. mid=(l+r)/2
  2. 检查，如果check(mid)=true,那么答案范围为[l,mid],下一次令r=mid
    如果check(mid)=false,那么答案范围为[mid+1,r],下一次令l=mid+1
  1
  2
  3
  4
  5
  while(l<r){ int mid=l+r>>1; if(check(mid)) r=mid; else l=mid+1; }
每次更新，如果是l=mid 就要补上mid=(l+r+1)/2，如果是r=mid就不必补上+1
1. 解释：
  - 为什么l=mid的时候需要补上1？
    - A：假设l=r-1的情况，此时mid=l，如果mid通过check，下一次更新，l=mid=l，那么下一次循环还是[l,r]，陷入循环；如果mid=(l+r+1)/2,那么此时mid=r，下次一更新便是[r,r]便不会出现死循环。
  - 如何使用？根据划分的结果是l=mid还是r=mid，使用对应的模板
  - 题目可能会无解但是二分的模板是一定有解的，无解一定是二分之后判断无解
2. 使用到二分的几种情况以及二分的模板的使用方法：
  - 找到大于等于某个数字的最小数【满足某个条件的第一个数字；左边界】
  - 找到小于等于某个数的最大数【满足某个条件的最后一个数字；右边界】
  - 查找最大值【满足边界性质的右边界】
  - 查找最小值【满足边界性质的左边界】153. 寻找旋转排序数组中的最小值查找符合：当前值小于右边界的最小值
  - 查找一个符合条件的值（可以任意使用某个模板，但是check的条件必须要加上等号）；模板的停止一定是l=r的时候，停止的地方一定是等于目标值的（当判断条件中包含等号时）
3. 补充：
  - 无脑二分，就是最简单最脱俗不考虑边界条件的情况 33. 搜索旋转排序数组
    - 主要思路就是：while循环条件是l<=R
    - 然后对于每个情况都分大于、小于、等于三种情况讨论
      - 等于单独拆出一个分支，return
      - 大于、小于的情况做状态判断
浮点数二分(找一个满足要求的浮点数)
- 浮点数二分不需要整除
- 当区间很小的时候，就认为找到了答案(如，r-l<<10^-6)
- 例题:数的平方根
  - 思路：浮点数一定在0和max(x,1)范围内【取max1是因为小于1的数字中，平方根总是比它本身要大的，所以必须要从1开始搜索；如0.01的】，二分搜索0和max(x,1)区间内的数，如果mid*mid是大于等于x的，那么最后的答案一定在l~mid之间，且由于是浮点数二分，不需要处理边界问题
  1
  2
  3
  4
  5
  6
  double l=0,r=x; while(r-l>1e-6){ double mid=(l+r)/2; if(mid*mid>=x) r=mid; else l=mid; }
- 例题：数的三次方根
  - 思路：同平方根类似，用二分查找三次方根：如果m^3>=x，那么r=m，反之则l=m；如果此时l-r<1e-8,则视为找到。
  1
  2
  3
  4
  5
  6
  double l=0,r=x>1:x?1; while(r-l>1e-8){ double mid=(l+r)/2; if(mid*mid*mid>=x) r=mid; else l=mid; }

高精度运算

C++ python无需高精度
因为是模板，所以会比较长

C++中大整数的存储
- 大整数每一位存在数组中，使用模式：个位存在数组的下标为0处;便于数组的扩展(进位导致高位增加，只要数组扩展就可以)
  1
  2
  3
  十进制：123456789 数组下标：0 1 2 3 4 5 6 7 8 实际存放：1 2 3 4 5 6 7 8 9

大整数加法

A+B 数量级:10^6
算法流程：A+B+t(进位)

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

//C=A+B
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;  //t变为进位后剩余的数字
    }
    if(t) C.push_back(t);//所有的数字都加完之后还有进位
    return C;
}


int main(){
    string a,b;
    vector<int> A,B;
    cin>>a>>b;
    //大整数用数组存，逆序遍历
    //若 A="123456";A=[6,5,4,3,2,1]
    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(a[b]-'0');
    auto C=add(A,B);
    for(int i=C.size()-1;i>=0;i--) printf("%d",c[i]);
    return 0;
}

大整数减法

A-B数量级：10^6
算法流程：先判断A和B的大小关系若A>=B,直接计算A-B；反之，计算-(B-A)；每一位：A-B-t(上一位的借位):如果大于等于0，直接计算，如果小于0，则计算A-B+10；

#include <iostream>
using namespace std;

//判断A是否大于等于B
bool cmp(vector<int> &A,vector<int> &B){
    if(A.size()!=B.size()) return A.size()?B.size();
    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); //如果t>0，直接返回t；如果t<0 返回t+10
        if (t<0) t=1;//小于0，被借位；借位只有0、1之分
        else t=0;
    }
    //去除前导0;C.size()>1保证有一个0
    while(C.size()>1 && C.back()==0) C.pop_back();
    return C;
}

大整数与小整数相乘

A*a A<=10^6 a<=10000
思路：由于是大整数与小整数相乘，这里直接用大整数的每一位和小整数相乘，计算结果，再加上进位。小整数是b；A*b+t

vector<int> mul(vector<int> &A,int b){
    vector<int> C;
    int t=0;
    for(int i=0;i<A.size() || t;i++){ //当i没有处理完或者进位没有处理完的时候都进入循环
        if(i<A.size()) t+=A[i]*b;
        C.push_back(t%10);
        t /= 10;    //存储进位
    }
    return C;
}
//输入结果：a用string(大整数) b用int(小整数)

大整数与小整数相除 A/a

每次从高位做除法，进行下一位，余数乘以10之后加上下一位数字，然后整除除数，计算出余数(数字-余数*除数)

#include <algorithm>
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=r%b;
    }
    reverse(C.begin().C.end());//除法把个位存在下标大的一端了
    // 去除余数前导0
    while(C.size()>1 && C.back()==0) c.pop_back();
    return C;

}

前缀和与差分

前缀和

下标有-1操作的时候，一般会使数组从1开始。

前缀和【下标从1开始，可以定义s[0]，少一些边界判断条件】如果有：a1+a2+…+an;则前缀和si=a1+a2+…+ai
1
2
S[i] = a[1] + a[2] + ... a[i] a[l] + ... + a[r] = S[r] - S[l - 1]
如何求si：使用for循环，s[i]=s[i-1]+a[i]；其中s[0]=0
前缀和作用：可以快速求出[l,r]区间的前缀和，即s[r]-s[l-1].时间O(1)，比直接计算O(n)省去了很多复杂度；
求解过程：求解前缀和题目，需要先预处理，再使用公式计算[l,r]区间的和

实操：795.一维前缀和

#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int a[N],s[N];
int main(){
    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;
}

实操：子矩阵的和(二维前缀和)

aij表示原数组；sij表示以ij为右下角，(1,1)为左上角的矩形中所有元素的和
子矩阵和之间的推导关系:
- s_ij表示以ij为右下角，(1,1)为左上角的矩形中所有元素的和
- 求以x1,y1为左上角;x2,y2为右下角的矩阵中所有元素的和：要求以 $s_{x_2,y_2}-s_{x_2,y_{1}-1}-s_{x_1-1,y_2}+s_{x_1-1,y_1-1}$
- 如何计算s_ij：两重循环 $s_{ij}=s_{i-1,j}+s_{i,j-1}-s{i-1,j-1}+a_{ij}$ 注意aij是一个元素(一个矩形的面积)

796

#include <iostream>
using namespace std;

const int N=1010;
int n,m,q;
int a[N][N],s[N][N];

int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    //计算sij
    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];
        }
    }
    //q次询问
    while(q--){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
    }
    return 0;
}

差分

差分是前缀和的逆运算

有a1,a2,…,an，构造b1,b2,…,bn,使得ai=b1+b1+…+bi;b称为a的差分，a称为b的前缀和
一维差分：b1=a1;b2=a2-a1;b3=a3-a2…;bn=an-a_{n-1}
用O(n)的时间得出a；
差分的应用：在O(1)的时间内求出[l,r]区间内的所有元素均加一个相同的数的结果。只需要让bl+c；br-c即可。bl+c，bl之后的所有前缀和a都会加上c，br-c，br之后的所有前缀和a都会减去c===>只需要O(1)的时间就可以让数组中的所有的数都加上一个值
用差分理解前缀和：根据刚刚的思路,如果b1，b2，…,bn是一个全0的数组，可以把前缀和a1,a2,…,an分别看作是[1,1]区间的所有元素均加了a1，[2,2]区间的所有元素均加了a2,…,[n,n]区间的元素都加了an

应用：797.一维差分

#include <iostream>
 using namespace std;
 const int N=100010;

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

 int main(){
     scanf("%d%d",&n,&m);
     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
     //把原数组的数插回去
     for(int i=1;i<=n;i++) insert(i,i,a[i]);
     while(m--){
         int l,r,c;
         scanf("%d%d%d",&l,&r,&c);
         insert(l,r,c);
         
     }

     for(int i=1;i<=n;i++) b[i]+=b[i-1];
     for(int i=1;i<=n;i++) printf("%d ",b[i]);

     return 0;
 }

应用：798.二维差分

差分核心操作：将以(x1,y1)为左上角,(x2,y2)为右下角的子矩阵中的所有数a[i,j]都加上C：只要对于差分数组，进行操作即可实现通过o(1)的时间完成操作(而不需要逐层遍历)。
原矩阵aij；构造差分：bij；如果想让以x1,y1,x2,y2分别为左上角右下角的矩形内所有前缀和统一加上一个c，那么只需要将 $b_{x_1,y_1}+=c;b_{x_2+1,y}-=c;b_{x_1,y_2}-=c;b_{x_2+1，y_2+1}+=c$
求解过程：先根据数组构造差分数组，然后再应用公式求解。
O(n)时间复杂度变成O(1)
理解bij：给定一个a数组，a数组是b数组的前缀和；b数组是a数组构造的逆运算。。

#include<iostream>
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(){
    scanf("%d%d%d",&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++)
        {
            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);
    }
    //求前缀和：结果放在a中
    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];
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%d ",a[i][j]);   
        }
        puts("");
    }
    return 0;
}

双指针

归并排序属于双指针算法
类别：1 两个指针指向两个序列 2 两个指针指向一个序列
一般用法：

for(i=0,j=0;i<n;i++)
{
    while(j<i && check(i,j))j++;
    //每道题具体分析
}

核心思想：将暴力算法O n^2优化为O（n）（应用某些单调的性质）

简单应用：重新输出 abc def ghi，将每个单词重新输出并且占一行

for(int i=0;i<n;i+ +){
    int j=i;
    while(j<n&&str[j]!= ' ')j++;
    for(int k=i;k<j;k++)cout<<str[k];
    cout<<endl;
    i=j;
}

双指针一般都先找一个朴素算法，再优化之

打卡题目最长连续不重复子序列

暴力：先枚举起点再枚举终点,ij指针是最长不重复子序列的边界

双指针：枚举i：i在右侧，j在左侧;i表示子序列的终点，j表示子序列往左最远能到达的地方

单调性：i，j是单调变化的，i右移之后，j不可能左移，只能右移(如果j可以左移，那么表示j和i-1区间没有重复元素，这个和i移动的条件相悖)
check函数的定义：开一个数组(题目数据在10000，那么就开一个10000大小的数组)，动态记录当前区间的数字出现多少次，如果当前下标的数字出现大于1次，那么j向右动，直到和a[i]不重复
可以用哈希表来存储，更加节省空间

#include<iostream>
using namespace std;
const int N =1e5+10;

int n;
int a[N],s[N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    int res=0;
    for(int i=0,j=0;i<n;i++){
        s[a[i]]++;
        while(s[a[i]]>1){ //指针不断往前指，直到j在与i重复的元素的后面
            s[a[j]] --;
            j++; 
        }
        res=max(res,i-j+1);
    }
    cout<<res<<endl;
    return 0;
}

位运算

n的二进制表示中，第k位是几(个位是第0位)
- 先把第k位移到最后一位，n>>k(n右移k)
- 看个位是几 x&1
- 结合1和2两步:n>>k&1
- 比如，十进制的10(1010)右移三位的结果就是 1

lowbit(x)返回x的最后一位1(最右一位1)

举例：lowbit(101000)=1000
实现方法：x&(-x)=x&(_x+1);-x=x+1(x取反+1)
应用：统计x中1的个数：不断进行lowbit，并且把x的最后一位1减掉

#include<iostream>
using namespace std;
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++;//每次减去x的最后一位1
        cout<<res<<" ";
    }
}

离散化

特指整数的有序离散化(有序离散化就是说，离散化之后，原本小的元素对应的元素也小，原来大的元素对应的元素也大)
离散化的两个问题：1. a[]中可能有重复元素，需要去重 2. 需要能快速映射，且有序离散化(排序)，如何算出a[i]离散化后的值(可以用二分)。
- 第一个问题：使用库函数：unique ; alls.erase(unique(alls.begin(),alls.end()),alls.end())
例子：如果数组a[]有如下数：1,3,100,2000,500000;将其映射到0,1,2,3,4的过程就是离散化
又一个例子：如果数组的下标：0-x,其中存放一系列的数，通过二分搜索找到数组中存放的数的下标

模板：

vector<int>alls;
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());//去除重复元素
//二分求出对应离散化的值
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，从1开始映射
}

unique函数的实现：

返回一个vector迭代器，双指针思路

//1112223345
vector<int> ::iterator unique(vector<int> &a){
    int j=0;
    for(int i=0;i<a.size();i++)
        if(!i || a[i]!=a[i-1]) //是第一个数或者和前一个数字不相等
            a[j++]=a[i];
    //结束之后，a[0]~a[j-1]都是不重复的数字

    return a.begin()+j;
}

应用:区间的和

这道题跨度很大：坐标的范围是2*10^{9，但是其中需要用到的坐标只有2*10}5，最多用到3*10^5个数字==>稀疏，可以使用离散化
思路：将坐标轴的值映射到从1开始的自然数，然后将其存储到数组a中，如果要求l到r之间的数的和，将其离散化为kl和kr，再求a[kl]到a[kr]之间的所有数的和；求a[kl]到a[kr]之间的所有数的和 可以使用求前缀和的问题解决
代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=300010;//插入操作，1e5个数字，查询，一左一右，2*1e5

typedef pair<int,int> PII;

int n,m;
int a[N],s[N];//s[N]表示前缀和
vector<int> alls;//存放所有需要用到的下标

//插入
vector<PII> 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; //映射到从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});
        
        alls.push_back(x);
        
    }
    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        query.push_back({l,r});
        
        alls.push_back(l);
        alls.push_back(r);
    }
    //alls去重，离散化
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end()); //下标：0-x,其中存放一系列的数，通过二分搜索找到数组中存放的数的下标
    
    for(auto item : add)//构造a[i]数组以用于计算前缀和
    {
        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);
        cout<<s[r]-s[l-1]<<endl;
    }
}

区间合并

思路：

将所有区间按照左端点排序，
维护一个区间st ed，新扫描到的区间有三种可能：
1. 在st ed内部
2. st在内部，ed在外部
3. st ed均在维护区间的外部
对于以上三种情况，有三种更新区间的方法
1. 还是本来的区间
2. 区间延长
3. 维护区间并上一个区间(而且可以保证，之后的所有区间的左端点都是在这个区间的后面)===那么当前这个维护区间之后一定不会被更新了，这个区间可以确定并拿出，将这个新区间作为待维护的区间(st ed)

代码

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

typedef pair<int,int> PII;//存储左右端点

const int N=100010;

int n;
vector<PII> segs;

void merge(vector<PII> &segs){
    vector<PII> res;
    sort(segs.begin(),segs.end());//C++中，pair会优先以第一个对象排序，再按照第二个对象排序
    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;
    
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int l,r;
        cin>>l>>r;
        segs.push_back({l,r});
        
    }
    merge(segs);
    cout<<segs.size()<<endl;
    return 0;
    
}

数据结构

以数组模拟为主

链表

说明：动态链表可以使用结构体实现，但是在笔试过程中，new一个对象很慢，因此算法题推荐使用数组模拟链表

单链表

常用邻接表实现；邻接表最常用来存储图和树

单链表表示：通过两个数组e[N] (存放内容) ne[N] (存放next指针，下一个指针的下标)

例如：head->3->5->7->9->null，使用数组模拟结果为：

1
2
3

head=0//表示头结点
e[0]=3, e[1]=5, e[2]=7, e[3]=9
ne[0]=1,ne[2]=2,ne[3]=3,ne[4]=-1

初始化

int head,e[N],ne[N],idx;//表示头结点下标，idx表示当前用到了哪个点(指向下一个空位)
void init()
{
    head=-1;
    idx=0;
}

插入到头结点：

//先把新节点连接到旧头前，然后再把头指针指向新的头结点
void insert_to_head(int x){
    e[idx]=x;
    ne[idx]=head;
    head=idx;
    idx++;
}

插入到指定位置：插入到指定点的后面：O(1)时间复杂度；插入到指定点的前面(需要O(n)的复杂度遍历，找到前一个结点，才能更改前一个结点的ne指针从而达到删除的目的)

//将x插入到下标为第k的结点的后面
void add(int x,int k){
    e[idx]=x;
    ne[idx]=ne[k];//当前点的下一个指针指向原来这个位置的点
    ne[k]=idx;//第k个结点的ne指向idx
    idx++;
}

删除指定位置:将下标为k的结点的后一个删除：直接让他的next指针改向即可；算法题不会管空间的回收

1
2
3

void remove(int k){
    ne[k]=ne[ne[k]];//算法题不会管空间的回收
}

实操:实现一个链表

实现一个单链表，链表初始为空，支持三种操作：
向链表头插入一个数；
删除第k个插入的数后面的一个数；(第一次插入，下标0)即删除下标为k-1的数后面的数
在第k插入的数后插入一个数。 在下标k-1的结点后面插入一个数
注意，在该题，因为不回收内存，其实第k次插入就隐含了下标信息

#include <iostream>
using namespace std;
const int N=100010;
int head,e[N],ne[N],idx;
void init(){
    head=-1;
    idx=0;
}
void insert_to_head(int x){
    e[idx]=x;
    ne[idx]=head;
    head=idx;
    idx++;
}
void add(int x,int k){
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}
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;
            insert_to_head(x);
        }
        else if(op=='D'){
            cin >> k;
            if (!k) head = ne[head];
            else remove(k - 1);
        }
        else if(op=='I'){
            cin>>k>>x;
            add(k-1,x);
        }
    }
    for(int i=head;i!=-1; i=ne[i]){
        cout<<e[i]<<" ";
    
    }
}

双链表

双链表有前向指针和后向指针，分别记为l[N] (前向指针)，r[N] (后向指针)
同时，为了方便，头节点e[0]和尾结点e[1]统一存储在数组首

链表初始化：

void init(){
    //head指针是e[0]，tail指针是e[1]
    l[1]=0;
    r[0]=1;
    idx=2;
}

插入一个点：在某个点的右侧插入一个点；在某个点的左侧插入一个点=在插入这个点的前一个点的右侧插入一个点(add(x,l[k]))

void add(int x,int k){
    e[idx]=x;
    l[idx]=k;
    r[idx]=r[k];
    l[r[k]]=idx;//一定要先更改后一个结点的前向指针
    r[k]=idx;//再使用r[k]
    idx++;
}

插入一个点：在某个点的左侧插入这个点：

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

头插、尾插

void insert_head(int x){//头插
    e[idx]=x;
    l[idx]=0;
    r[idx]=r[0];
    l[r[0]]=idx;
    r[0]=idx;
    idx++;
}
void inset_tail(int x) //尾插
{
    e[idx]=x;
    l[idx]=l[1];
    r[idx]=1;
    r[l[1]]=idx;
    l[1]=idx;
    idx++;
}

删除第k个点：

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

栈和队列

数组模拟栈和队列；栈：先进后出；队列：先进先出

模拟栈：这种写法：栈从下标1开始，如果tail=0就表示栈为空

#include <iostream>
using namespace std;
const int N=100010;
int stk[N],tt;//一个栈顶指针
//插入
stk[++tt]=x;
//弹出
tt--;
//判断栈是否为空
if(tt>0) not empty;
else empty;
//栈顶
stk[tt];

栈应用：求运算符优先级

中缀表达式运算顺序:中缀表达式就是二叉树的中序遍历。已知二叉树中序遍历可以使用栈实现，故此题目使用栈来实现。具体实现方法：
1. 从左到右扫描中缀表达式。
2. 如果遇到操作数（数字），则将其压入操作数栈。
3. 如果遇到操作符（如 +, -, *, /），执行以下操作：
  a. 如果操作符栈为空或栈顶元素为左括号 (，则将操作符压入操作符栈。
  b. 如果新操作符的优先级高于操作符栈顶的操作符，也将新操作符压入操作符栈。
  c. 如果新操作符的优先级小于或等于操作符栈顶的操作符，从操作数栈中弹出两个操作数，从操作符栈中弹出一个操作符，执行相应的计算，并将结果压入操作数栈。然后，将新操作符压入操作符栈。重复此过程，直到新操作符可以被压入操作符栈。
4. 如果遇到左括号 (，将其压入操作符栈。
5. 如果遇到右括号 )，重复执行以下操作，直到遇到左括号 (：
  a. 从操作数栈中弹出两个操作数。
  b. 从操作符栈中弹出一个操作符。
  c. 执行相应的计算，并将结果压入操作数栈。
  d. 在执行完这些操作后，弹出操作符栈顶的左括号 (。
6. 当扫描完整个中缀表达式后，如果操作符栈仍然包含操作符，重复执行以下操作，直到操作符栈为空：
  a. 从操作数栈中弹出两个操作数。
  b. 从操作符栈中弹出一个操作符。
  c. 执行相应的计算，并将结果压入操作数栈。
7. 操作数栈中剩余的最后一个元素就是中缀表达式的计算结果。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
stack<int> num;
stack<char> op;
void eval(){//通过栈运算
    auto b=num.top();num.pop();
    auto a=num.top();num.pop();
    auto c=op.top();op.pop();
    int x;
    if(c=='+') x=a+b;
    else if(c=='-') x=a-b;
    else if(c=='*') x=a*b;
    else if(c=='/') x=a/b;
    num.push(x);
}
int main(){
    unordered_map<char,int> pr{{'+',1},{'-',1},{'*',2},{'/',2}};
    string str;
    cin>>str;
    for(int i=0;i<str.size();i++){
        auto c=str[i];
        if(isdigit(c)){
            int x=0,j=i;
            while(j<str.size() && isdigit(str[j]))
                x=x*10+str[j++]-'0';
            i=j-1;
            num.push(x);
        }
        else if(c=='(') op.push('(');
        else if(c==')'){
            while(op.top()!='(') eval(); //用末尾运算符操作末尾两个数
            op.pop();
        }
        else {
            while(op.size()&& pr[op.top()]>=pr[c]) eval();
            op.push(c);
        }
    }
    while(op.size()) eval();
    cout<<num.top()<<endl;
}

模拟队列

int q[N],hh,tt=-1;//队头初始化为0，队尾初始化为-1，队尾小于队头，因此队列是空的
//插入
q[++tt]=x; 
//弹出:队头在下标小的位置，因此弹出的时候队头下标应该是变大的(往队尾走)
hh++;
//判断是否为空：如果队头的下标永远是小于等于队尾的，那么一定是有元素的
if(hh<=tt) not empty; 
else empty;
//取出队头元素
q[hh];

单调栈

常用：给定一个序列，求这个序列中，每个数字最近的比它大/小的数的位置；如果要找3 4 2 7 5 这个序列中，左边所有数字中最近的比它小的数字，结果是-1 3 -1 2 2

单调栈相关题目的解题思路和双指针差不多，先想暴力的做法，然后再优化(尝试是否可以使用双指针思路)

暴力思路：外层循环遍历每一个元素，内层循环从该元素下标开始，向左移动，直到找到一个比ai小的数
单调栈思路：存入栈中，且如果ax的下标小于ay，但是ax大于ay，则ax一定不会作为答案输出(对于大于ax的数p来说，最近的小于p的数一定是ay)，那么ax就一定可以在栈中删除(寻找答案的时候，ax不可能作为答案输出)【维护栈是严格单调递减的】
代码;读入较慢，可以加一些优化；时间复杂度：每个元素进栈一次，出栈一次，整个算法时间复杂度是O(n)

#inlcude<iostream>
using namespace std;
int n;
int stk[N],tt;
int main(){
    //优化:cin优化和scanf优化二选一
    //cin.tie(0);
    //ios::sync_with_stdio(false);
    cin>>n;
    //scanf("%d",&n);
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        //scanf("%d",&x);
        //删除所有栈顶部比x大的数
        while(tt && stk[tt]>=x) tt--;
        //直到有一个数比x小,符合输出条件
        if(tt) cout<<stk[tt]<<' ';
        else cout<<-1<<' ';
        //print("%d",stk[tt])

        stk[++ tt ]=x;
    }
    return 0;
}

单调队列：最常应用,求滑动窗口中的最大值和最小值

滑动窗口类型的问题可以使用单调栈进行优化
- 队列中存储：滑动窗口中的元素，当前窗口中的所有元素；用队列维护窗口
- 暴力做法：每次都在遍历队列里的元素O(nk)
- 单调队列做法：队列中的元素是单调递增(减)的，对于单调递增的队列来说，这里规定队头的元素比队尾的元素要小，从队头到队尾依次递增。每次滑动窗口内的滑动的时候，如果新进入队列的数字比队列中最小的数字(队头)小，那么就删除靠近队头的大元素，维持滑动窗口队列内元素的单调性；单调队列中的元素大小是单调的！

总结：单调栈和单调队列问题：都先考虑用栈和队列暴力模拟问题，然后再看暴力算法中无用的点，把所有无用的元素都删除，检查是否有单调性，如果有，则进行优化(极值：取端点,找值：二分);
注意：滑动窗口队列中存储的是下标(可以判断窗口大小)，单调栈中存储的是值

代码：

#include<iostream>
using namespace std;
const int N=1e6+10;
int n,k;
int a[N],q[N];
int main(){
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&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--;
        q[++ tt]=i;//当前数插入队列（记录下标）
        //从前k个数字开始输出，如果数字不足k个，不需要输出最大/最小值
        if(i>=k-1) printf("%d ",a[q[hh]]);
    }
    puts("");
    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--;
        q[++ tt]=i;//当前数插入队列（记录下标）
        //从前k个数字开始输出，如果数字不足k个，不需要输出最大/最小值
        if(i>=k-1) printf("%d ",a[q[hh]]);
    }
    puts("");
}

KMP：求子串出现的位置
字符串S和模式串P，模式串P在字符串S中多次作为子串出现，求模式串P在字符串S中所有出现的位置的起始下标

暴力枚举的做法:

S[N],p[M]
for(int i=1;i<n;i++){
    bool flag=true;
    for(int j=1;j<=m;j++){//j是指匹配正确的字串的长度
        if(s[i+j-1]!=p[j]){
            flag=false;
            break;
        }
    }
}

KMP算法的思路

将模式串整体移动，计算匹配指针最少往后移动多少，使得模式串的前半串找到下一串匹配的地方(如上图所示，红框内，字串相同)，需要预处理出，以某个点为终点的后缀和以第一个字符为起点的前缀相等的最大长度是多少
next数组的含义：next[i]=j表示以i为终点的后缀和从1开始，长度为j的前缀相等，且后缀长度最长（为j），即p[1,j]=p[i-j+1,i]
next数组的作用：如果匹配失败，那么直接比较next[j]中下标的元素，而不必从1开始(相当于快速跳过了许多比较)
代码

#include <iostream>
using namespace std;
const int N =1e5+10, M=1e6+10;
int m,n;
char p[N],s[M];
int ne[N];
int main(){
    cin >> n >> p + 1 >> m >> s + 1;
    //求ne过程，和匹配过程类似,每次匹配失败也退回到ne[j]重新匹配
    //ne从1开始，所有的数组下标都是从1开始
    //ne[1]=0，表示这是字符串头
    for(int i=2,j=0;i<=n;i++){
        while(j && p[i]!=p[j+1]) j=ne[j];
        if(p[i]==p[j+1]) j++;
        ne[i]=j;
    }
    //匹配过程
    //这里i从1开始，j下标从0开始
    for(int i=1,j=0;i<=m;i++){
        //j！=0表示没有退到模式串的开头
        while(j&&s[i]!=p[j+1]) j=ne[j];
        if(s[i]==p[j+1]) j++;
        if(j==n){
            printf("%d ",i-n);
            j=ne[j];//匹配成功，
        }
    }
}

举例：next数组：

S="abababc"
P="abababab"
ne=[x,0,0,1,2,3,4,5,6]
并比较S[7]的时候，发现不相等；此时i=7，j=6；跳到j=ne[j]，比较i和j+1

Trie树

用法：用于高效地存储和查找字符串集合的数据结构（一般使用到Trie树的题目，字母的类型不会很多）
举例：abcdef abdef aced bcdf bcff cdaa bcdc ，存储到Trie树中：（有结束标记）
例题：两种操作：1. 插入字符串 2. 询问一个字符串在集合中出现多少次

#include<iostream>
using namespace std;
const int N=1e5+10;
//cnt[x]：存以x结尾的字符串有多少个
//idx：存当前用到哪个下标;idx初始化为0;下标是0的点，既是根节点，又是空节点
int son[N][26],cnt[N],idx;
//son存储每个节点的所有儿子；只能是26个，因为字符集合就是26
//如果x是一个结点，那么son[x][n]存储的就是结点x的第n个儿子
char str[N];
void insert(char str[])//存储
{
    int p=0;//根节点
    for(int i=0;str[i];i++){
        int u=str[i]-'a'; //小写字母映射到数字(son是int类型)
        if(!son[p][u])//不存在儿子，即没有被插入过，那么重新创建一个新的
            son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]++;//以p为结尾的数又多了一个
}
/**
//插入abc；idx a=0；idx b=1;idx c =2;
u=0 son[0][0]=1;
p=1; u=1; son[1][1]=2;
p=2; son[2][2]=3;
cnt[3]=1;
//插入 ab idx a=3;idx b=4
u=0;son[0][0]!=0;p=son[0][0]=1;//指向下一个
u=1;son[1][1]!=0;p=son[1][1]=2;
cnt[2]=1;
//插入 abcd ab idx a=5;idx b=6;idx c=7;idx d=8

*/



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;
    scanf("%d",&n);
    while(n--){
        char op[2];
        scanf("%s%s",op,str);
        if(op[0]=='I') insert(str);
        else printf("%d\n",query(str));
    }
    return 0;

}

最大异或树：Trie树存数字

暴力：第一重循环，枚举第一个数；第二重循环，枚举第二个数；直到找到最大的值，可以按顺序枚举，保证不重复
长度为31位的二进制数字，每次选择能使高位异或为1的
暴力的优化：用Trie树优化，每次找到叶节点即为找到，每次从Trie树寻找与目标值异或最大值的数(先查找，再将目标值插入到Trie树)【不需要先全部插入，而是一边插入一边查找】
代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10,M=31*N;
int n;
int a[N];
int son[M][2],idx=0;//N个31位的数，一共需要N*31位的空间存放
void insert(int x){
    int p=0;
    for(int i=30;i>=0;i--){
        int u = x>>i &1;//取出第i位的二进制数(从高位开始取)
        if(!son[p][u]) son[p][u]=++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]){ 
            p=son[p][!u];
            res=res*2+!u;//二进制，res是指结果从高位开始找，每次低位就是res*2左移一位，加上新的二进制数
        }
        else {
            p=son[p][u];
            res=res*2+u;
        }
    }
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    int res=0;
    for(int i=0;i<n;i++){
        insert(a[i]);
        int t=query(a[i]);
        res=max(res,a[i]^t);
    }
    printf("%d\n",res);
}

并查集

涉及到集合合并的问题可以使用并查集

并查集作用：1. 可以快速将两个集合合并,近乎O(1) 2. 询问两个元素是否在一个集合中近乎O(1)
- 如果不使用并查集：用数组存储x属于哪个数组，则对于需求2，可以进行快速判断；对于需求1，则很麻烦，把所有的元素属于的集合都要改，至少要O(n)的时间
基本原理：以树的形式维护所有的集合，每个集合的编号是它根节点的编号，每个点都存储了它的父节点p[x]，当想要知道每个结点属于的集合，则只需要查找到当前节点的根节点即可
- 如何判断树根：即p[x]==x
- 如何求x的集合的编号：while(p[x]!=x)x=p[x]；【时间复杂度高】
  - 优化：路径压缩：所有的节点接到根节点上
  - 优化：按秩合并：矮的树接到高的树上
- 如何合并两个集合：px是x的集合编号，py是y的集合编号，p[x]=py即可
代码实现：

#include<iostream>
using namespace std;
const int N=100010;
int p[N];//父节点数组，存每个元素的父节点是谁，x表示的是下标

int find(int x){//返回下标为x所在集合的编号(祖宗结点)+路径压缩
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
//初始：每个元素都是一个集合，树根是自己
int main(){
    int m,n;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--){
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);//scanf读字符串会直接忽略中间的空格和回车，用scanf读入一个字母
        //用scanf("%c %d%d",&op,&a,&b)应该也可以
        if(op[0]=='M'){//合并,a祖宗节点的父亲=b的祖宗节点
            p[find(a)]=find(b);
        }
        else {
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
        }
    }
}

并查集的拓展：

维护每个集合的元素个数

例题:连通块中点的数量:在无向、无边图中连线；连通块：可以从a到b，从b到a

思路：用集合维护两个连通块，维护使用size[N]保存每个连通块的大小

            #include<iostream>
using namespace std;
const int N=100010;
int p[N],psize[N];//父节点数组，存每个元素的父节点是谁

int find(int x){//返回x所在集合的编号(祖宗结点)+路径压缩
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
//初始：每个元素都是一个集合，树根是自己
int main(){
    int m,n;
    scanf("%d%d",&n,&m);
    //初始化，每个连通块的大小都是1
    for(int i=1;i<=n;i++) {
        psize[i]=1;
        p[i]=i;
    }
    while(m--){
        char op[3];//务必要留一个空间给空格
        int a,b;
        scanf("%s",op);
        if(op[0]=='C'){//合并,a祖宗节点的父亲=b的祖宗节点
            scanf("%d%d",&a,&b);
            if(find(a)==find(b)) continue;
            psize[find(b)]+=psize[find(a)];
            p[find(a)]=find(b);
        }
        else if(op[1]=='1') {
            scanf("%d%d",&a,&b);
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
        }
        else{
            scanf("%d",&a);
            printf("%d\n",psize[find(a)]);

        }
    }
}

作业：食物链：需要额外维护什么信息？提示：需要额外维护每个点到根节点的距离【即，维护一个并查集，记录每个节点和根节点的关系】

一个点到根节点距离是1：表示他可以吃根节点；如果一个点到根节点距离是2，则表示它可以吃到根节点距离是1的点，即它可以吃1，它被根节点吃；如果一个点到根节点距离是3，则表示它和根节点是同类；
所有点和根节点之间的距离有三种：通过模3可求，模三余1，表示它可以吃根节点；余2表示可以被根节点吃；余0表示和根节点是同类
距离初始化为0，路径压缩的时候额外
代码实现：

#include<iostream>
using namespace std;
const int N=50010;

int n,m;
int p[N],d[N];
int find(int x){
    if(p[x]!=x){
        int t=find(p[x]);//直接指向根节点
        d[x]+=d[p[x]];//d[p[x]]存储x父节点到根节点的距离；d[x]存储x到父节点的距离；相加：x到根节点距离
        p[x]=t;
    }
    return p[x];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;

    int res=0;
    while(m--){
        int t,x,y;
        scanf("%d%d%d",&t,&x,&y);
        if(x>n || y>n) res++;
        else{
            int px=find(x),py=find(y);
            if(t==1){//同类
            //已经在一棵树上,判断到根节点距离
                if(px==py && (d[x]-d[y])%3)  res++;
                else if(px!=py) {
                    p[px]=py;
                    d[px]=d[y]-d[x];
                }
            }
            else {//t=2
                //x吃y，x到根的距离比y到根的距离多1 (dx-dy-1)%3=0
                if(px==py && (d[x]-d[y]-1)%3) res++;
                else if(px!=py){
                    p[px]=py;
                    //(d[x]+?-d[y]-1)%3=0 因此d[x]
                    d[px]=d[y]+1-d[x];//长度保证被吃关系
                }
            }
        }

    }
    printf("%d\n",res);
}

堆

堆的基本结构：完全二叉树(STL里的堆是优先队列)
- 小根堆：每个点都是小于等于左右儿子的，根节点是小于等于左右子树的最小值的，因此根节点就是最小值
- 堆的存储：使用一维数组(x的左儿子：2x，x的右儿子：2x+1)
- 堆的基本操作
  - down(x):(节点的值变大)，节点向下移，每次都找最小值与它交换
  - up(x):(节点值变小)，节点向上移，每次看和父节点的大小，比父节点小就交换

建堆：建堆时间复杂度：O(n) 从n/2的位置开始
插入一个数 heap[++size]=x;up(size);
求集合中的最小值 heap[1];
删除最小值，堆顶一个元素删除，把最后一个元素覆盖到堆顶，然后再向下调整；heap[1]=heap[size];size–;down(1);
删除任意一个元素 heap[k]=heap[size];size–;down(k),up(k); 区分，heap[k]是变大还是变小了，分别调用（其实直接调用两个没什么问题）
修改任意一个元素 heap[k]=x;down(k),up(k);

堆排序

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int m,n;
int h[N],cnt;
void down(int u){
    int t=u;//存储需要交换到u位置的元素的下标
    if(u*2<=cnt && h[u*2]<h[t]) t=u*2;
    if(u*2+1<=cnt && h[u*2+1]<h[t]) t=u*2+1;
    if(u!=t){
        swap(h[u],h[t]);
        down(t);
    }
}
void up(int u){
    int t=u;
    while(u/2 && h[u/2]>h[u]){
        swap(h[u/2],h[u]);
        u/=2;
    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&h[i]);
    cnt=n;
    //数组存二叉树的特性，n/2之后的节点全都是叶子节点
    for(int i=n/2;i;i--) down(i);//从1/2开始down,O(n)时间复杂度，上限O(logn)
    while(m--){
        printf("%d ",h[1]);
        h[1]=h[cnt];
        cnt--;
        down(1);
    }
}

模拟堆:要更改第k个插入的数字，需要额外的数组来记录插入的顺序；使用ph[j]=k来记录第j个插入的元素的值的下标(在堆中)是k；hp[k]=j来记录第下标为k的数是第j个插入的【Dijstra算法需要用到带指针的】;ph从下标映射到堆；hp从堆映射到下标

heap_swap：重写的交换，同时维护了ph和hp数组

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
int m,n;
int h[N],ph[N],hp[N],cnt;
void heap_swap(int a,int b){
    //ph中，下标表示的是插入顺序，里面存插入的数
    //hp中，下标表示的是插入的数，里面存插入的顺序
    swap(ph[hp[a]],ph[hp[b]]);//交换postoheap中，交换两个
    swap(hp[a],hp[b]);//交换heaptopos数组中，a和b对应的插入顺序值
    swap(h[a],h[b]);//交换堆中的两个数字的值
}
void down(int u){
    int t=u;//存储需要交换到u位置的元素的下标
    if(u*2<=cnt && h[u*2]<h[t]) t=u*2;
    if(u*2+1<=cnt && 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/2]>h[u]){
        heap_swap(u,u/2);
        u/=2;
    }
}
int main(){
    int n;
        scanf("%d",&n);
        while(n--){
            char op[10];
            int k,x;
            scanf("%s",op);
            if(!strcmp(op,"I")){
                scanf("%d",&x);
                cnt++;
                m++; //第m个插入的数
                ph[m]=cnt; 
                hp[cnt]=m;
                h[cnt]=x;
                up(cnt);
            }
            else if(!strcmp(op,"PM")) printf("%d\n",h[1]);
            else if(!strcmp(op,"DM")){
                heap_swap(1,cnt);
                cnt--;
                down(1);
            }
            else if(!strcmp(op,"D")){ //删除
                scanf("%d",&k);
                k=ph[k];
                heap_swap(k,cnt);
                cnt--;
                down(k),up(k);
            }
            else {
                scanf("%d%d",&k,&x);
                k=ph[k];
                h[k]=x;
                down(k),up(k);
            }
        }
}

哈希表

哈希表的操作一般是添加和查找，删除是逻辑删除

存储结构

哈希函数：将值域较大的数映射到较小的数中；哈希函数一般直接取模，其中取模质数,该指数要离2的幂次较远

//寻找质数
for(int i=100000;;i++){
    bool flag=true;
    for(int j=2;j*j<i;j++){
        if(i%j==0){
            flag=false;
            break;
        }
        if(flag){
            cout<<i<<endl;
            break;
        }
    }
}

哈希函数，负数模：k=(x%N+N)%N，C++中，负数的模还是负数，需要先模再加再取模

处理冲突：两个不同的数映射到同一个数：有两种方法避免冲突

开放寻址法：处理冲突的思路：数组的长度是题目范围的2-3倍；如果h(x)=k,且k处有数字，那么向后找，直到找到第一个空位为止；查找：从k向后找，直到找到最后或者找到一个空位结束；删除依然是打一个标记，逻辑删除;这个代码有个bug:如果数组全满了的话，那么find就会死循环

代码实现：

#include <cstring>
#include <iostream>
using namespace std;
const int N=200003,null=0x3f3f3f3f;
//开放寻址法，查找和插入都需要进行find操作
//找一个大于2*输入大小的质数;Null表示空:这里取0x3f填充int字节，int四个字节=2*4=8个十六进制位
int h[N];

int find(int x){ //x在hash表，则返回的是x在hash表的位置，如果不再hash表，则k为x应该存储的位置
    int k=(x%N+N)%N;
    while(h[k]!=null && h[k]!=x){
        k++;
        if(k==N) k=0;//k==N表示已经到了数组的最末端，则要从数组头开始看，继续查找
    }
    return k;
}
int main(){
    int n;
    scanf("%d",&n);
    memset(h,0x3f,sizeof h);
    //memset按照字节赋值，因此每个字节都赋3f,转换成int类型就是0x3f3f3f3f
    while(n--){
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        int k=find(x);
        if(*op=='I') h[k]=x;
        else {
            if(h[k]!=null) puts("Yes");
            else puts("No");
        }
    }
}

拉链法：如果存在冲突，则使用链将冲突的数全都存储(存储在单链表中)；查找：直接查找k对应的链即可

代码实现

#include <cstring>
#include <iostream>
using namespace std;
const int N=100003;//哈希，模数取质数
int h[N],e[N],ne[N],idx;
//h[N]:记录每条链表的头指针 e[N],ne[N]链表

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;
    scanf("%d",&n);
    memset(h,-1,sizeof h);
    while(n--){
        char op[2];
        int x;
        scanf("%s%d",op,&x);
        if(op[0]=='I') insert(x);
        else {
            if(find(x)) puts("Yes");
            else puts("No");
        }
    }
}

字符串的哈希方式

字符串前缀哈希法：
0. 定义字符串的hash：建立一个字符到数字的映射(如，A=1，B=2…)接着将字符串看作是一个p进制的数，比如ABCD就是(1234)p=1*p^3+2*p2+3*p^1+4*1,然后将该数字取模Q，模数Q一般要尽量小=>可将字符串映射到0-q的数字
- 注意：不能将字符映射成0,如果A=0，则AA=0，出现冲突
- 注意：如果不存在冲突，则当p=131或13331时，Q=2^64,一般不会出现冲突；即进行字符串哈希的时候不需要考虑冲突，也就不需要解决冲突
1. 首先预处理出所有前缀的哈希：h[0]=0;h[x]表示前x个字符的hash
  - h[i]=h[i-1]*p+str[i]
2. 根据前缀算出字符串哈希值：
  - 已知h[R]以及h[L-1],求h[L-R]【L<R】
  - 其中，h[L-1]最高位p^{{L-2},最低位p}0;h[R]最高位p^{R-1} 最低位p^{0,因此需要将h[L-1]的结果左移与h[R]对齐，即h[L-1]*p}{R-L+1}，将其左移结果与h[R]相减即可得到h[L-R]
  - h[L-R]=h[R]-h[L-1]*p^{R-L+1}
  - 技巧：由于Q一般取2^64 即unsigned long long，那么就不需要取模，直接将其转换为unsigned long long即可

字符串哈希的用法：询问两个区间的字符串是否相同

#include <iostream>
using namespace std;
typedef unsigned long long ULL;
const int N=100010,P=131;
int n,m;
char str[N];
ULL h[N],p[N]; //h存放前缀和
ULL get (int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}
int main(){
    scanf("%d%d%s",&n,&m,str+1);
    p[0]=1;
    for(int i=1;i<=n;i++){//预先计算p的幂次
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+str[i]; 
    }
    while(m--){
        int l1,l2,r1,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);

        if(get(l1,r1)==get(l2,r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

STL

直接拿C++实现的数据结构

pair

存储二元组

pair的初始化：

pair<int,string>p;
p=make_pair(10,"a");
p=(20,"abc");
//pair存储三个属性
pair<int,pair<int,int>>p;

定义：pair<int,string>
pair.first取得第一个元素(例子里看就是int类型的)
pair.second取得第二个元素
支持比较运算，按照字典序比，以first为第一关键字，second为第二关键字

vector

变长数组，倍增思想
由于系统为程序分配空间时所需的时间和申请空间的次数有关，因此在使用变长数组的时候，我们应该减少分配空间的次数，可以浪费空间
- vctor的倍增思想：每次数组长度不足，就将数组长度*2分配新空间并且把旧元素重新复制到新空间，大大减少了申请的次数，倍增思想可以减少分配空间的时间复杂度，平均下来每个空间的开辟时间是O(1)的
定义长度为n(也可以不指定n)的vectorvector<int> a(n);定义二维vectorvector<int> a[n];;将vector长度为10，数字初始化为3vector<int> a(10,3);
a.size() 返回元素个数 O(1)
a.empty() 返回是否为空 true 空 O(1)
a.clear() 清空
a.front();a.back()返回第一个/最后一个数
a.push_back()推入;a.pop_back()弹出
a.begin()迭代器(类型vecor::iterator)：第0个数;a.end()迭代器：最后一个数的后一个位置,a[a.size()]
C11新增的迭代 for(auto x:a)
vector的比较运算：按照字典序比，如33333<444

string

字符串
string.size() empty() clear()
支持加法，+=等
substr(start,len)起始下标、长度；不标长度，则直接输出到最后
c_str()可以返回存储字符串的指针

queue priority_queue

queue
- size(),empty(),push()队尾插入,pop()返回队头元素,front()返回队头元素,back()返回队尾元素
- 没有clear函数，如果需要情况，那么直接重新构造即可q=queue<int>()
priority_queue,优先队列默认大根堆
- push pop top
- 如何变成小根堆？
  - 插入数字的时候插入它的相反数，正数变负数heap.push(-x)
  - 直接定义小根堆：priority_queue<int,vector<int>,greater<int>> heap;

stack

push(),top(),pop(),empty(),size()

deque

双端队列，队头队尾都可以插入、删除
size(),empty(),clear(),front(),back(),push_back(),pop_back();push_front()/pop_front()
效率低

set,map,multiset,multimap

基于平衡二叉树(红黑树)，动态维护有序序列
set中不能有重复元素，multiset可以有重复元素
均支持：size(),empty(),clear(),begin(),end(),++/–返回前驱和后继，时间复杂度O(logn)
set multiset
- insert()插入数
- find()朝朝一个数，如果不存在，返回end迭代器
- count()返回某个数的个数，通过键来寻找，有返回1，没有返回0
- erase()
  - 输入一个数x，则删除所有的x O(k+logn)
  - 输入一个迭代器，则删除这个迭代器
- 核心操作：lower_bound()返回大于等于x的最小的数的迭代器，upper_bound()返回大于x的最小的数的迭代器
map multimap
- insert() 插入的数是一个pair
- erase() 输入pair或迭代器
- find()
- 核心操作：key做下标[]，可以像数组一样使用，但是时间复杂度是O(logn)
- lower_bound(),upper_bound()

unordered_set,unordered_map,unordered_multiset,unordered_multimap

哈希表
使用方法和有序的是差不多的，但是不能支持lower_bound(),upper_bound()，因为无序的,也不支持迭代器的++ –

bitset

压位

最常使用，bool数组省空间

1 2	`bitset<10000> S;//定义一个长度为10000的bitset ~s;//取反`

支持==,!=,[],count()返回有多少个1，
any()判断是否至少有一个1,none() 判断是否全为空
set() 所有位置置为1
set(k,v)把第k位变成v
reset()把所有位变成0
flip()等价于~取反
flip(k)把第k位取反

搜索与图论

DFS

DFS和BFS的比较
- 数据结构：DFS使用栈，BFS使用队列
- 空间：DFS空间O(h),BFS空间O(2^h)
- BFS第一次扩展的点一定是最短路径，DFS搜索到的点不具有最短路径;
每个DFS一定对应一个搜索树，DFS可以理解成递归
回溯：回溯需要注意恢复现场
剪枝：提前判断，直接回溯

例题：排列数字，按照字典序输出所有的排列方法

代码实现

#include<iostream>
using namespace std;
const int N=10;
int n;
int path[N];
bool st[N];//记录该点是否已经被使用 true表示被使用
void dfs(int u){//u表示层数
    if(u==n){ //
        for(int i=0;i<n;i++) printf("%d ",path[i]);
        puts("");
        return;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){//i没有被使用
            path[u]=i;//将i放入当前路径
            st[i]=true;
            dfs(u+1);
            //恢复现场，递归结束后一定要恢复
            path[u]=0;//可以不恢复，因为每次for循环都会直接给path赋值
            st[i]=false;
        }
    }
}
int main(){
    cin>>n;
    dfs(0); //层数
}

例题：n皇后问题：涉及剪枝

搜索顺序1：按行枚举每一行皇后的位置(全排列思路)，需要剪枝

#include <iostream>
using namespace std;
const int N=20;
int n;
char g[N][N];
bool col[N],dg[N],udg[N];
//行：col[n]第n列是否有皇后、对角线:dg[n]第n条是否有皇后、反对角线
void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++) puts(g[i]);
        puts("");
        return;
    }
    for(int i=0;i<n;i++){//第u层皇后摆放位置的枚举
        if(!col[i] && !dg[u+i] && !udg[n-u+i]){
            //对角线与反对角线如何计算：与行u相交的对角线y=u+i，反对角线n-u+i y=-u+i 由于避免-u+i变为负数，因此再加上n
            g[u][i]='Q';
            col[i]=dg[u+i]=udg[n-u+i]=true;
            dfs(u+1);
            col[i]=dg[u+i]=udg[n-u+i]=false;
            g[u][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：枚举每一个棋盘中的格子，选择放或不放

void dfs(int x,int y,int s){
    if(y==n) y=0,x++;
    if(x==n){
        if(s==n){
            for(int i=0;i<n;i++) puts(g[i]);
            puts("");
        }
        return;
    }
    //不放皇后
    dfs(x,y+1,s);
    //放皇后
    if(!row[x]&&!col[y] && !dg[x+y] && !udg[x-y+n]){
        g[x][y]='Q';
        row[x]=col[y] =dg[x+y] =udg[x-y+n]=true;
        dfs(x,y+1,s+1);
        row[x]=col[y] =dg[x+y] =udg[x-y+n]=false;
        g[x][y]='.';
    }
}

BFS

BFS可以搜索到最短路径(当边的权重为1时才可以使用)
- 思路：每次将初始值放入队列，while队列不为空，则取出队头并扩展t
DP是一种特殊的最短路问题

例题：走迷宫：从起点到终点的距离

第n步，把每个距离为n的点全部遍历，直到扩展到终点
代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m;
int g[N][N];//存储图(迷宫)
int d[N][N];//每个点到起点的距离
//队列：数组实现，也可以直接用STL里的queue实现
PII q[N*N];
//如果需要记录路径
PII Prev[N*N];
int bfs(){
    int hh=0,tt=0;//队头和队尾
    q[0]={0,0}; //初始化
    memset(d,-1,sizeof d);//初始化距离d
    d[0][0]=0;

    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    while(hh<=tt){
        auto t=q[hh++]; //每次取出队头
        //判断上+(-1,0)下+(1,0)左+(0,-1)右+(0,1)是否可以走
        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;
                Prev[x][y]=t;
                q[++tt]={x,y};
            }
        }
    }
    //输出路径，从最后一个点向前找
    //int x=n-1,y=m-1;
    //while(x || y){
    //    cout<<x<<" "<<y<<endl;
    //    auto t=prev[x][y];
    //    x=t.first,y=t.second;
    //}
    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];
        }
    }
    cout<<bfs()<<endl;
    return 0;
}

八数码：

思路：将棋盘状态看成一个节点，找到从初始状态到最终状态的最短路径
- 状态的表示：每个状态都是一个9*9的矩阵(如何将状态存入queue，如何定义距离)
- 直接用字符串表示状态，距离dist使用unordered_map表示
- 状态转移：由字符串变为矩阵，并且移动
代码实现:

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
int bfs(string start){
    string end="12345678x";

    queue<string> q;
    unordered_map<string,int> d;
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

    q.push(start);
    d[start]=0;
    while(q.size()){
        auto t=q.front();
        q.pop();

        int distance=d[t];

        if(t==end) return distance;
        //状态转移
        int k=t.find("x");
        int x=k/3,y=k%3;
        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){
                swap(t[k],t[a*3+b]);
                if(!d.count(t)){ //看有没有到达过这个状态，如果已经到达就无需更新距离
                    d[t]=distance+1;
                    q.push(t);
                }
                swap(t[k],t[a*3+b]); //状态还原
            }
        }

    }
    return -1;
}

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

树和图

树和图的存储方式：

树是无环连通图
图分为有向图和无向图，无向图可以看作特殊的有向图(即如果ab之间有路径，则可理解为a到b和b到a都有边)，因此无向图问题可以转换为有向图
有向图的呈现方式：
- 邻接矩阵：g[a,b] 表示a到b的边，空间复杂度N^2(是稠密的)
- 邻接表：每个节点都有一个单链表，存储该节点可以到达的所有点；如果要添加边，只需要头差起点的单链表即可
树和图深度优先遍历和宽度优先遍历：时间复杂度O(m+n)
代码实现(树的邻接表存储)

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010,M=N*2;
int h[N],e[M],ne[M],idx;//n个单链表，N个头;e[i]记录有向图中的终点
bool st[N];//记录哪些点被遍历过
void add(int a,int b){//a所在的单链表总插入b
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u){
    st[u]=true;
    //遍历所有出边
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]) dfs(j);//递归其实就是利用了栈
    }
}
int main(){
    memset(h,-1,sizeof h);
}

例题分析：树的深度优先遍历：树的重心

无向边：因此每个边在有向图中其实是两条边
重心：对于每个点，都求出删去它之后，剩余点的点数的最大值，再找出其中最小的，即可得出。如何快速求出每个点删除后剩余点数的最大值：通过DFS求出每个子树中点的数量(该点的子节点分别都是一个联通块，剩余的部分可以构成一个连通块，有n-size(以删去点为根的子树的节点个数))
代码实现

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010,M=N*2;
int h[N],e[M],ne[M],idx;//n个单链表，N个头;e[i]记录有向图中的终点
int ans=N;//全局答案时最小的最大值，因此这里初始化为N
int n;
bool st[N];//记录哪些点被遍历过
void add(int a,int b){//a所在的单链表总插入b
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int dfs(int u){
    st[u]=true;
    int sum=1,res=0;//sum:当前子树的大小(该子树的每个子树大小+1根节点)；res:每个连通块大小的最大值
    //遍历所有出边
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j])//没有遍历过
        {
            int s=dfs(j);//递归其实就是利用了栈
            res=max(res,s);//选最大的子树
            sum+=s;//当前子树的大小需要加上每个子树的大小
        }
    }
    res=max(res,n-sum);//n-sum是去除以该点位根的子树的节点个数
    ans=min(ans,res);
    return sum;
}
int main(){
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    dfs(1);
    cout<<ans<<endl;
}

例题分析：树的宽度优先遍历：图中点的层次

思路：使用宽搜，当第一次发现先这个点，就是找到啦从起点到该点的最短距离
代码实现:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int bfs(){
    int hh=0,tt=0;
    q[0]=1;
    memset(d,-1,sizeof d);
    d[1]=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]==-1){//第一次被搜索到，更新距离
                d[j]=d[t]+1;
                q[++tt]=j;
            }
        }
    }
    return d[n];
}
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);
    }
    cout<<bfs()<<endl;
    return 0;
}

拓扑排序

有向图有拓扑序列，所有的边都是从前面指向后面的
并不是所有的图都有拓扑序列（不能有环），一个有向无环图一定存在拓扑序列；有向无环图被称为拓扑图
一个有向无环图一定至少存在一个入度为0的点
拓扑排序：
1. 首先将所有入度为0的点入队
2. 当队列不为空时
  - 取出队头t，枚举t的所有出边
  - 删除从t出的所有边(t->j)
  - 将终点的入度减去d[j]–;
  - 如果有新的入度为0的点d[j]==0，则j入队
拓扑排序不一定是唯一的

代码实现：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100010;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[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;
    }
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            d[j]--;
            if(d[j]==0) q[++tt]=j;

        }
    }
    return tt==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);
        d[b]++;
    }
    if(topsort()){
        //排序结束之后，队列数组中的顺序正好就是答案
        for(int i=0;i<n;i++) printf("%d ",q[i]);
        puts("");
    }
    else puts("-1");
}

最短路

稠密图使用邻接矩阵，稀疏图用邻接表
关于有向图和无向图：无向图转换为有向图(出+入边)即可使用算法
重边和自环：重边：两个点之间有多条边；自环：从自己出发又回到自己的边
- 重边和自环在最短路问题的解决方法：重边只需要保存权最小的边即可；自环则直接删去边即可
最短路问题的分类：
- n表示点的数量；m表示边的数量；稠密图就是指边很多；反之是稀疏图
- 单源最短路：求从一个点到其它所有点的最短距离
  - 所有边权都是正数
    - 朴素Dijkstra算法 O(n^2)【适合稠密图】
    - 堆优化版的Dijkstra算法 O(mlogn);一般适用于稀疏图，如果稠密图用堆优化的Dijkstra算法：则时间复杂度就是O(n^2logn)
  - 存在负权边
    - Bellman-Ford算法 O(nm)
    - SPFA 一般情况下(O(m),最坏情况O(nm))
- 多源汇最短路：求不同起点到其他点的最短路
  - Floyd算法 O(n^3)
- 源点：起点；汇点：终点
最短路问题难点在于建图

朴素Dijkstra算法

使用邻接矩阵
算法步骤
- 集合s：所有当前已经确定最短距离的点
1. 初始化距离：dist[1]=0，dist[i]=正无穷;即只有起点的距离被确定
2. for i=0~n【每次迭代都能找到x到一个点的最短距离】
  - 找到一个不在s中的、距离最近的点t【找距离最小值】
  - 将t加入到s中
  - 用t更新其它点的距离
    - 更新方式,如果t是有一个指向x的出边：如果dist[x]>dist[t]+n（dist[x]是此前统计的内容，dist[t]是从起点到t的距离+n表示从起点到t再到x的距离）
代码实现：

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

const int N=510;
int n,m;
int g[N][N];
int dist[N];//距离
bool st[N];//表示每个点的最短路径是否被确定
int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<n-1;i++){ //t==n-1，即最后一个点不用再继续搜索，它到其它点的距离也一定大于已确定的内容
        int t=-1;
        for(int j=1;j<=n;j++){//找答案前没有确定最短路且距离最近的点
            if(!st[j] && (t==-1 ||dist[t]>dist[j])) 
                t=j;
        }
        st[t]=true;//t加入集合s
        for(int j=1;j<=n;j++)//更新距离
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}


int main(){
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);//保留长度最短边
    }
    int t=dijkstra();
    printf("%d\n",t);
    return 0;
}

堆优化版的Dijkstra算法

朴素版本的算法中，找最小距离n^2时间；使用堆可以优化成mlogn【堆中维护的是点的信息，时间复杂度为logn，又因为要修改m次，因此时间复杂度为mlogn】
堆
- 手写堆，可以保证堆中始终都只有n个数
- 优先队列【可能会存在冗余】：由于堆不支持修改其中的元素，因此每次修改就要往里插入新的数据，堆中的元素可能是m(因此时间复杂度会变成mlogm)
算法步骤
- 集合s：所有当前已经确定最短距离的点
1. 初始化距离：dist[1]=0，dist[i]=正无穷;即只有起点的距离被确定
2. for i=0~n【每次迭代都能找到x到一个点的最短距离】
  - 找到一个不在s中的、距离最近的点t【找距离最小值】；使用堆找可能会有冗余
  - 将t加入到s中
  - 用t更新其它点的距离
    - 更新方式,如果t是有一个指向x的出边：如果dist[x]>dist[t]+n（dist[x]是此前统计的内容，dist[t]是从起点到t的距离+n表示从起点到t再到x的距离）
代码实现（有点像宽搜）

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

const int N=1e6+10;
int n,m,idx;
int h[N],e[N],ne[N],w[N];//稀疏图，邻接表形式存储;h存储每个节点对应的出边，e存储出边的终点，ne存储下一个出边的位置，w表示边的权重
int dist[N];//距离
bool st[N];//表示每个点的最短路径是否被确定

typedef pair<int, int> PII;

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;
        if(st[ver]) continue;
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i]){ //每次遍历了从t出去的所有边
            int j=e[i];
            if(dist[j]>distance+w[i]){
                dist[j]=distance+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);//对重复的边不进行处理，因为邻接表会记录每个边的信息
    }
    int t=dijkstra();
    printf("%d\n",t);
    return 0;
}

Bellman-Ford算法

边的存储：使用结构体struct{int a,b,w}edge[m];
使用前提：不存在负权回路(即一个回路上的所有边的权重之和不可能是负数)
限制边数的最短路径需要用该算法解决
应用1：求是否存在负权回路：迭代k次后，求出不超过k条边的最短路径的距离，如果第n次迭代又更新了，则表示存在某条路径，该路径上有n条边，则意味着有n+1个点，则这个路径中一定存在环且是负环
算法思路：时间复杂度O(nm)
- for循环n次 //迭代k次，dist数组指的是从1号点经过不超过k条边所走到的所有边的最短距离
  - 每次for循环所有的边 a b w （起点a，终点b，权重w）【松弛操作】
    - dist[b]=min(dist[b],dist[a]+w);
- 循环之后，对于所有距离都满足:dist[b]<=dist[a]+w;【三角不等式】
代码实现：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,M=10010;
int m,n,k;
int dist[N],backup[N];
struct Edge{
    int a,b,w;
}edges[M];

void bellman_ford(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<k;i++){
        memcpy(backup,dist,sizeof dist);//一定要备份一下，防止串联的发生（只能使用上一次更新的结果来更新整个dist数组，如果不备份，则可能新更改的内容直接被使用
        //遍历数组
        for(int j=0;j<m;j++){
            int a=edges[j].a,b=edges[j].b,w=edges[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
    //不能使用这种判断有没有路径的方法，可能存在为-1的路径
    // if(dist[n]>0x3f3f3f3f/2) return -1;
    // return dist[n];
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<m;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i]={a,b,w};
    }
    bellman_ford();
    if(dist[n]>0x3f3f3f3f/2){
        puts("impossible");
    }
    else printf("%d\n",dist[n]);
    return 0;
}

SPFA算法

只要没有负环就可以使用该算法，最坏O(nm)
正权图的问题，可以用Dijkstra算法的，SPFA也可以使用
SPFA算法是BF算法的优化，使用宽搜进行优化(使用队列)
- 先将第一个点放在queue中
- while queue非空
  1. 取出队头t
  2. 更新t的所有出边,将其出边的终点都加入队列
代码实现：

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

const int N=1e5+10;
int n,m,idx;
int h[N],e[N],ne[N],w[N];//稀疏图，邻接表形式存储;h存储每个节点对应的出边，e存储出边的终点，ne存储下一个出边的位置，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 ++;
}

void spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    queue<int> q;
    q.push(1);
    st[1]=true;//记录点是否被存入队列中 

    while(q.size()){
        int t=q.front();
        q.pop();

        st[t]=false;//主要是优化，避免一次遍历中出现多个点，提高效率
        //更新所有邻边
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){ //最短路径有调整且j不在队列中，才将其加入队列
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
}


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);//对重复的边不进行处理，因为邻接表会记录每个边的信息
    }
    spfa();
    if(dist[n]==0x3f3f3f3f) puts("impossible");
    else printf("%d\n",dist[n]);
    return 0;
}

SPFA算法求负环：利用抽屉原理

使用dist[x]表示节点1到节点x的距离；使用cnt[x]表示当前最短路的边数
每次更新：dist[x]=dist[t]+w[i];cnt[x]=cnt[x]+1;
如果cnt[x]>=n，则表示从1-x至少经过n+1个点，由于抽屉原理，则一定存在两个相同的点，路径上存在一个环，且是负环
代码实现：

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

const int M=1e4+10,N=2010;
int n,m,idx;
int h[N],e[M],ne[M],w[M],cnt[N];//稀疏图，邻接表形式存储;h存储每个节点对应的出边，e存储出边的终点，ne存储下一个出边的位置，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 ++;
}

bool spfa(){

    //无需初始化，求负环无需指定起点
    queue<int> q;
    //负环有可能不是从1开始，因此要把所有的点都加入到队列中
    for(int i=1;i<=n;i++){
        st[i]=true;
        q.push(i);
    }

    while(q.size()){
        int t=q.front();
        q.pop();

        st[t]=false;//主要是优化，避免一次遍历中出现多个点，提高效率
        //更新所有邻边
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return true;
                if(!st[j]){ //最短路径有调整且j不在队列中，才将其加入队列
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}


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);//对重复的边不进行处理，因为邻接表会记录每个边的信息
    }
    if(spfa()) puts("Yes");
    else puts("No");
    return 0;
}

Floyd算法

使用邻接矩阵存储图；用了dp的思路
算法思路：三重循环;初始：d[i,j]存储i到j的边权
- for(k=1;k<=n;k++)
  - for(i=1;i<=n;i++)
    - for(j=1;j<=n;j++)
      - d[i,j]=min(d[i][j],d[i][k]+d[k][j]);
- 结束：d[i,j]存储i到j的最短路径的长度
代码实现：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N =210,INF=1e9;
int n,m,Q;
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(){
    scanf("%d%d%d",&n,&m,&Q);
    
    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 a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        //处理重边
        d[a][b]=min(d[a][b],w);
    }
    floyd();

    while(Q--){
        int a,b;
        scanf("%d%d",&a,&b);
        //不存在通路的情况，可能会比INF小一些
        if(d[a][b]>INF/2) puts("impossible");
        else printf("%d\n",d[a][b]);

    }
    return 0;
}

最小生成树

基本都是无向图
算法概览：
- Prim算法
  - 朴素版：稠密图 O(n^2)
  - 堆优化版本：O(mlogn) [不常用]
- Kruskal算法时间复杂度：O(mlogm) 先排序再做稀疏图

Prim算法

朴素版Prim算法：

算法过程：集合中存储加入最小生成树的点

dist[i]<- 正无穷
for (i=0;i<n;i++)
    找到集合外距离最近的点t
    用t更新其它点到集合的距离===与Dijkstra算法不同的点(怎么找？看点有多少条边连向集合内部的点，最短的一条就是它到集合的距离)
    st[t]=true;

生成树是每次选中的点的距离对应的边

最小生成树：边的正负没有关系
代码实现：

#include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510,INF=0x3f3f3f3f;
int m,n;
int g[N][N];
int dist[N];
bool st[N];
int prim(){
    memset(dist,0x3f,sizeof dist);
    int res=0;
    for(int i=0;i<n;i++){ 
        int t=-1;
        for(int j=1;j<=n;j++){ //找距离集合最小距离的点，如果是第一个，则直接加入
            if(!st[j] && (t==-1 || dist[t]>dist[j]))
                t=j;
        }
        if(i && dist[t]==INF) return INF; //不是第一个数且有一个点剩余
        if(i) res+=dist[t];//必须要先累加再更新，不然负自环可能会导致dist[j]减小
        //如果先更新，存在自环x->x，且恰好自环的权小，则会使得自环更新dist[x]
        for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);

        st[t]=true;
    }
    return res;
}
int main(){
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=g[b][a]=min(g[a][b],c); //处理无向图
    }
    int t=prim();
    if(t==INF) puts("impossible");
    else printf("%d\n",t);
    return 0;
}

堆优化版本==思路麻烦，代码长
- 堆维护dist数组，找最小点O(1),总共需要O(n),更新其它点的最小距离，需要O(mlogn)【m条边*树高logn】;更新st数组总共需要O(n)

Kruskal算法

基本思路【并查集】
- 先将所有边按照权重从小到大排序O(mlogm)
- 枚举每条边，a-b 权重c O(m)
  - 如果a b不连通，将这条边加入集合中
- 总时间复杂度O(mlogm)

代码实现

#include<iostream>
#include<algorithm>
using namespace std;
const int N=200010;
int m,n;
int p[N];
struct Edge{
    int a,b,w;
    bool operator<(const Edge &W)const{ //重载小于号方便排序
        return w<W.w;
    }
} edges[N];
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main(){
    int res=0,cnt=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i]={a,b,w};
    }
    sort(edges,edges+m);
    for(int i=1;i<=n;i++) p[i]=i;//初始化并查集，每个点的p都是自己

    for(int i=0;i<m;i++){
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        a=find(a),b=find(b);
        if(a!=b){
            p[a]=b;
            res+=w;
            cnt++;
        }
    }
    if(cnt<n-1) puts("impossible");
    else printf("%d\n",res);

}

二分图

算法概览：
- 染色法：判别是否是二分图 DFS O(m+n)
- 匈牙利算法：求最大匹配 O(mn) 实际运行时间远小于该时间

染色法

利用图论的性质：一个图是二分图当且仅当图中不含奇数环
- 奇数环：环中点的数量是奇数
对于二分图，一定可以通过染色过程且不会出现矛盾
染色法：从前向后遍历一个点，如果i为染色，则通过dfs染色i
代码实现：

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010,M=200010;
int n,m;
int h[N],e[M],ne[M],idx;
int color[N];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx ++;
}
bool dfs(int u,int c){
    color[u]=c;//遍历到就染色
    for(int i=h[u];i!=-1;i=ne[i]){//一个连通图内，只需要从“起点”开始遍历即可
        int j=e[i];
        if(!color[j]){
            //如果是1，则染成2；如果是2则染成1
            if (!dfs(j,3-c)) return false;
        }
        else if(color[j]==c) return false;
    }
    return true;
}
int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    bool flag=true;
    for(int i=1;i<=n;i++){//考虑非连通图，保证遍历每个点
        if(!color[i]){ //如果i未染色
            if(!dfs(i,1)){ //则从开始进行深度优先遍历
                flag=false;
                break;
            }
        }
    }
    if(flag) puts("Yes");
    else puts("No");
}

匈牙利算法

算法思路：找最大的匹配数量【所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配】
- 如果每次有冲突，则尝试更改已有匹配，直到无法更改或匹配成功
- O(n*m) n表示遍历做半部分匹配的n个点，m表示右半部分匹配的点，每n个点最多要遍历m次寻找匹配
代码实现：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510,M=100010;
int n1,n2,m;
int h[N],e[M],ne[M],idx;
int match[N];//match[j]=i表示右半部分的点j和i匹配
bool st[N];//防止重复搜点
void add(int a,int b){
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
bool find(int x){
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]){
            st[j]=true;
            if(match[j]==0 || find(match[j])){
                match[j]=x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    scanf("%d%d%d",&n1,&n2,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    int res=0;
    for(int i=1;i<=n1;i++){
        memset(st,false,sizeof st);
        if(find(i)) res++;
    }
    printf("%d\n",res);
}

动态规划

DP的时间复杂度：状态数量*转移数量

背包问题汇总

背包不一定装满

01背包问题
- N个物品，一个容量为V的背包，每件物品只用一次，使得选出来的物品总价值最大
- 特点：每件物品最多只用一次
完全背包问题
- 每件物品有无限个
多重背包问题
- 每个物品最多有si个
分组背包
- 物品有n组，每组有若干个，每个组中只能选择一个物品

思考动态规划问题的方式
从两个角度考虑：分别是状态表示 f(i,j) 以及状态计算
- 状态表示：
  - 集合：dp问题中的每个状态都可以看成一个集合；使用fij表示一个集合
  - 集合的属性：一般有三种：最大值、最小值、元素的数量
- 状态计算【集合划分】：对应集合的划分
  - 例如：01背包问题会把f(i,j)根据是否包含i物品划分为两个集合
  - 原则：不重、不漏(必须满足)【求最大最小值，可以重复；求数量，不能重复】
- dp优化：对动态规划的代码或方程进行变形
- 背包问题先不优化

01背包问题

有N件物品和一个容量是V的背包，每件物品只能用一次；每个物品的v是体积，w是价值
01背包问题的状态表示：
- 集合：是所有选法的集合，且选法满足：
  1. 只从前i个物品中选
  2. 选出物品的总体积小于等于j
- fij表示该集合中，所有选法的价值最大值
01背包问题的状态计算【集合划分】：根据是否包含i物品划分为两个集合
- 不含i：从1-i,体积为j且不包含i的集合===最大值f(i-1,j)
- 包含i：从1-i,体积为j且包含i的集合===f(i,j)：求f(i,j)时，先将所有选法中的第i个物品去除(从1-i-1中选择，且最大体积不超过j-vi)，即f(i-1,j-vi)+wi【去掉第i个物品的最大值加上第i个物品也是最大值】
- 最终，f(i,j)=max(f(i-1,j),f(i-1,j-vi))
01背包问题的结果：f(n,v)前n个物品中选择体积不超过v的物品的价值最大值
代码实现

#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];
    //f[0][0-m]0件物品，初始状态默认是0，直接从1开始
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            f[i][j]=f[i-1][j];//不选的方案一定存在，选择的方案可能不存在，如果当前物品大于重量，则方案会不存在
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

代码优化

分析：计算f(i,j)只用到了f(i-1)这一层，且对于j，f(i,j)使用到的j都是小于等于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];
    //f[0][0-m]0件物品，初始状态默认是0，直接从1开始
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){//由于j小于v[i]会直接滑过，因此可以直接从v[i]开始
            //f[j]=f[j];//不选的方案一定存在，选择的方案可能不存在，如果当前物品大于重量，则方案会不存在
            //从大到小枚举体积，f[j-v[i]]不会先被更新
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m]<<endl;
    return 0;
}

完全背包问题

和01背包的差别：状态转移方程的区别：01背包从第i-1层转移，完全背包从i层的j-v转移；优化后的一维代码，01背包和完全背包的差别只在于最后循环的顺序
状态表示 f(i,j)
- 集合：所有只考虑前i个物品且总体积不大于j的所有选法
- 属性：总价值的最大值
状态计算：按照第i个物品选择数量进行划分，因此在此将集合划分为n个
- 第一个子集：第i个物品不选择：f(i,j)=f(i-1,j)
- 第k个子集：绕一下求解：
  1. 去掉k个物品i
  2. 求Max，f(i-1,j-k*v[i])
  3. f(i,j)=f(i-1,j-k*v[i])+k*w[i]

朴素算法：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int v[N],w[N];
int f[N][N];
int n,m;
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=0;j<=m;j++)
            for(int k=0;k*v[i]<=j;k++)
                f[i][j]=max(f[i][j],f[i-1][i-k*v[i]]+w[i]*k);
    cout<<f[n][m]<<endl;
}

优化：优化成两维:观察递推公式之间的关系

f[i,j]=Max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2*v]+2*w...,f[i-1,j-k*v]+k*w)
f[i,j-v]=Max( f[i-1,j-v],f[i-1,j-2*v]+w,...,f[i-1,j-k*v]+(k-1)*w)
注意，j最多减到k*v个，不能更大，因此下方的f[i,j-v]转移方程中不可能存在可以放进大于k个的物品的情况
观察上式子，f[i,j-v]的推导公式中，f[i,j]非0集合处的式子都比f[i,j-v]的多加了一个wf[i][j-v]的最大值
因此：f[i,j]计算公式的后半部分等于f[i,j-v]+w, f[i][j]=Max(f[i-1][j],f[i][j-v]+w)
代码实现

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int v[N],w[N];
int f[N][N];
int n,m;
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=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
        }
    cout<<f[n][m]<<endl;
}

优化：由于完全背包状态转移方程只依赖第i层

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int v[N],w[N];
int f[N];
int n,m;
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++) //j从小到大枚举，不会有先后被覆盖的问题
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    cout<<f[n][m]<<endl;
}

多重背包问题

状态表示f(i,j)
- 集合：所有只从前i个物品中选且总体积不超过j的选法
- 属性：最大值
状态计算：按照物品i选几个分类,分类成s[i]个
- f[i,j]=Max(f[i-1][j-k*v[i]]+w[i]*k)(k=0,1,2…,s[i])

朴素算法：和朴素版本的完全背包问题差别不大，最内层k替换成s[i]即可

for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++)
    for(int j=0;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-k*v[i]]+w[i]*k);

优化：

1 2	`f[i,j]=max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w...,f[i-1,j-sv]+sw) f[i,j-v]=max( ,f[i-1,j-v] ,f[i-1,j-2v]+w,...,f[i-1,j-sv]+(s-1)w,f[i-1][j-(s+1)v]+sw)`

多重背包的j可能大于k+1个物品i所需要的空间
二进制优化方式：将s拆成二进制和的形式
- s的范围是0-1023 可以使用二进制数来表示 1,2,4,8,…512
- 0-1023中的每个数字都可以使用这些二进制数字相加形成
- 如果是0-127 则可以用1,2,4,8…,32,64,73凑出
- 如何凑？1,2,4,8…,2^k,c 其中1+2+…+2^k可以凑出s（如果比s小，那就要额外再凑一个c使得最后结果之和为s,且c是严格小于2
  的k次方的)s=2^(k+1)-1+c
时间复杂度：从nvs优化为nvlogs
关于空间大小：一共有n件物品，每件物品有s[i]件，s小于等于2000，每个物品可以拆分成log2000个物品，因此需要至少1000*log2000大小的数组
代码实现：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=12010,M=2010;
int v[N],w[N];
int f[M];
int n,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>0){
            cnt++;
            v[cnt]=a*s;
            w[cnt]=b*s;
        }
    }
    n=cnt;
    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;
}

分组背包问题

如果状态转移方程依赖上层，则从大小枚举体积；如果依赖本层，则从小到大枚举体积

状态表示
- 集合：只从前i组物品中选，且总体积不大于j的所有选法
- 属性：价值的最大值
状态计算：枚举每组物品选不选、选哪个
- 第i组物品一个都不选：f[i-1,j]
- 选第i组物品中的第k个物品：f[i-1,j-v[i,k]]+w[i,k]
代码实现：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int v[N][N],w[N][N],s[N];
int f[N];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++)
        {
            cin>>v[i][j]>>w[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=0;j--){//从大到小枚举
            for(int k=0;k<s[i];k++)
                if(v[i][k]<=j)
                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
        }
    }
    cout<<f[m]<<endl;
}

线性DP问题

求解DP的时候按照线性顺序递推的可以称为线性DP；

数字三角形

题意：每次走，使得最后走出来的数字最大；这道题也可以从下向上做，这样代码会少一点
状态表示：f[i.j]可以用i表示行，j表示第几个
- 集合：所有从起点走到(i,j)的路径
- 属性：MAX

状态计算：所有起点到当前点的路径可以分为两类：从左上角的点来或从右上角的点来
- 来自左上角的最大路径：从起点走到左上角路径的最大值：f(i,j)=f(i-1,j-1)+a[i,j]
- 来自右上角的最大路径：从起点走到右上角的最大值：f(i,j)=f[i-1,j]+a[i,j]
题目注意：初始化的时候一定要注意，左右边界都要初始化（比如这题，如果第三行，就要初始化到第四列，不然边界未初始化值可能导致比较大小的结果不对）
代码实现

#include<iostream>
#include<algorithm>
using namespace std;
const int N=510,INF=1e9;
int a[N][N],f[N][N],n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            scanf("%d",&a[i][j]);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i+1;j++)
            f[i][j]=-INF;
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
    int res=-INF;
    for(int i=0;i<=n;i++) res=max(res,f[n][i]);
    cout<<res<<endl;
}

最长上升子序列

题意：求数字严格单调递增的子序列最长是多少
状态表示：【一维，二维，三维递增考虑】f[i]以i结尾的数组
- 集合：所有以第i个数结尾的上升子序列集合
- 属性：集合里每个以i结尾的所有上升子序列长度的最大值
状态计算：【集合划分】
- 所有以i为结尾的上升子序列一定包含i，不能再用是否有i作为分类
- 以倒数第二个数【即i之前的一个数字】作为分类，可以分为i类：0表示倒数第二个数是0，i-1表示倒数第二个数是i-1；每一类不一定都存在；f[i]=max(f[k]+1)(k=0,1,…,i-1)
时间复杂度：状态数量：n 转移数量 n O(n^2)
代码实现

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010,INF=1e9;
int a[N],f[N],n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        f[i]=1;//f[i]最小是1
        for(int j=1;j<i;j++){
            if(a[j]<a[i])// 如果满足上升要求
                f[i]=max(f[i],f[j]+1);
                //g[i]=j; // 记录每个状态的转移
        }
    }
    //int k=1;
    // for(int i=1;i<n;i++)
    //     if(f[k]<f[i]) //找到最优解
    //         k=i;
    //倒着推出f[k]
    // for(int i=0;i<f[k];i++){
    //     print("%d",a[k]);
    //     k=g[k];
    // }
    int res=0;
    for(int i=0;i<=n;i++) res=max(res,f[i]);
    cout<<res<<endl;
}

如何保存最长序列？只要存储每次的转移是如何转移过来的即可【看上面代码的注释部分】

最长上升子序列 II

原思路的冗余：如果上升子序列的个数相同，但是结尾的数字有大有小，那么可以按照结尾的数字从大到小排排序，只要存结尾数字最小的即可；
因此可以存储不同长度下，最小的上升子序列结尾【另开一个新数组q，q[i]存储长度为i的上升子序列的结尾最小值】
可以通过反证法，证明序列一定是严格单调递增的
最长上升子序列长度：a[i]接到最大的小于a[i]的数q[j]后面，那么a[i]为结尾的最长上升子序列大小=q[j]为结尾的最长上升子序列大小+1；接下来更新q[j+1]（因为q[j]一定是比a[i]大的）
代码实现

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n,a[N],q[N];
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    //二分小于某个数的最大数
    int len=0;
    q[0]=-2e9;//哨兵，如果要插入的数字是最小的数，哨兵可以控制插入的位置，保证第一个数字是可以被替换的
    for(int i=0;i<n;i++){
        int l=0,r=len;
        while(l<r){
            int mid=l+r+1>>1;
            if(q[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        len =max(len,r+1);
        q[r+1]=a[i]; //更新最小值
    }
    printf("%d\n",len);
    
}

最长公共子序列

注意：子序列不是子串；一般来说字符串的dp都可以这样做
状态表示：二维f[i,j]
- 集合：f[i,j]表示所有在第一个序列的前i个字母中出现且在第二个序列的前j个字母中出现的子序列
- 属性：最大值
状态计算：集合划分(难点)
- 以a[i] b[j]是否包含在子序列中作为划分依据；四种情况，二进制表示
  - 00：f[i-1][j-1]【一般情况下，这种类型不讨论，因为被涵盖在了f[i-1][j]和f[i][j-1]】
  - 01：f[i-1][j]所有在第一个字符串的前i-1个字符串中出现且在第二个字符串的前j个字符中出现的子序列的最大值；不一定包含b[j]，但是一定包含01的情况（a[i]不出现在子序列中，且b[j]出现在子序列中）【注意，此时f[i-1][j]和f[i-1][j-1]可能有重复；求最大值没关系】
  - 10：f[i][j-1]
  - 11：f[i-1][j-1]+1 【此时a[i]和b[j]一定相等】
代码实现：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
char a[N],b[N];
int f[N][N];
int main(){
    scanf("%d%d",&n,&m);
    scanf("%s%s",a+1,b+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    printf("%d\n",f[n][m]);   
}

编辑距离

n个长度不超过10的字符串 m次询问，求给定的n个字符串中有多少字符串可以在上限操作次数内经过操作变成询问字符串
一种求法：调用m*n次最短编辑距离直接做：10^6*100=108

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int m,n;
const int N=1010;
char A[N][20],B[20];
int f[N][N];
int main(){
    scanf("%d",&n);
    scanf("%d",&m);
    for(int i=1;i<=n;i++){
        scanf("%s",A[i]+1);
        A[i][0]='X';

    }
    while(m>0){
        int times;
        B[0]='X';
        scanf("%s",B+1);
        scanf("%d",&times);
        int res=0;
        for(int sub=1;sub<=n;sub++){
            int alen=strlen(A[sub])-1,blen=strlen(B)-1;
            for(int j=0;j<=blen;j++) f[0][j]=j;
            for(int i=0;i<=alen;i++) f[i][0]=i;
            for(int i=1;i<=alen;i++){
                for(int j=1;j<=blen;j++){
                    if(A[sub][i]==B[j]) f[i][j]=f[i-1][j-1];
                    else f[i][j]=f[i-1][j-1]+1;
                    int minCal=min(f[i-1][j],f[i][j-1]);
                    f[i][j]=min(minCal+1,f[i][j]);  
                }
            }
            if(f[alen][blen]<=times) res++;
        }
        cout<<res<<endl;
        m--;
    }
}

最短编辑距离

状态表示和最长公共子序列是类似的
思考：
状态表示：f[i,j] 表示集合：A的前i个变成B的前j个字符串最少需要进行的次数
状态计算：按照最后一步的操作方式分类
- 不需要操作：f[i,j]=f[i-1,j-1]
- 删除操作：f[i,j]=f[i-1,j]+1 //把将新插入的删除
- 插入操作：f[i,j]=f[i,j-1]+1 //插入一个和B[j]一样的字符
- 插入操作：f[i,j]=f[i-1,j-1]+1 //新插入的替换B[j]
代码实现：

#include<iostream>
#include<algorithm>
using namespace std;
int m,n;
const int N=1010;
char A[N],B[N];
int f[N][N];
int main(){
    scanf("%d",&n);
    scanf("%s",A+1);
    //可以写成 scanf("%d%s",&n,A+1);
    scanf("%d",&m);
    scanf("%s",B+1);
    //边界情况
    for(int j=0;j<=m;j++) f[0][j]=j;
    for(int i=0;i<=n;i++) f[i][0]=i;
    //动态规划
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(A[i]==B[j]) f[i][j]=f[i-1][j-1];
            else f[i][j]=f[i-1][j-1]+1;
            int minCal=min(f[i-1][j],f[i][j-1]);
            f[i][j]=min(minCal+1,f[i][j]);  
        }
    }
    cout<<f[n][m]<<endl;
}

区间DP

石子合并

N堆石子拍成一排，每堆石子有一定重量，每次只能合并相邻的而且合并会消耗合并石子的重量作为代价;求合并成一堆需要的最小体力
状态表示：区间f[i,j]【i到j的区间】
- 集合：所有将第i堆石子到第j堆石子合并成一堆的合并方式
- 属性：最小值
状态计算：
- 最后一定是将左右合并成一堆
- 以最后一次分界线的位置进行分类，有k-i+1类
- 最后一步的最小代价：f[i,j]=f[i,k]+f[k+1,j]+s[j]-s[i-1] （s是前缀和）
时间复杂度：状态个数：n^2 枚举次数：n n^3
代码实现【区间dp需要保证每次计算，需要依赖的状态已被计算好】按照区间长度，从小到大枚举

#include<iostream>
#include<algorithm>
using namespace std;
const int N=310,INF=1e9;
int n,s[N],f[N][N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&s[i]);
    for(int i=1;i<=n;i++) s[i]+=s[i-1];
    for(int len=2;len<=n;len++)//区间为1，代价是0
        for(int i=1;i+len-1<=n;i++){
            int l=i,r=i+len-1;
            f[l][r]=INF;
            for(int k=l;k<r;k++)
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }
    printf("%d\n",f[1][n]);
}

递归的dp是记忆化搜索

计数类DP

整数划分

背包做法：

把整数n看成是容量为n的背包，有n个物品体积分别是1-n，目标是恰好装满背包的方案数，且每个物品可以用无限次
状态表示：f[i,j]表示从1-i中选，总体积恰好是j的选法的数量
状态计算：根据第i个物品选择几个来分类
- 选0个：f[i-1,j] 选1个：f[i-1,j-i] 选2个：f[i-1,j-2i]…
虽然是可以过的，但是需要优化一下【完全背包优化】
f[i,j]=f[i-1][j]+f[i-1][j-i]+f[i-1][j-2i]+…+f[i-1][j-si]
f[i,j-i]= f[i-1][j-i]+f[i-1][j-2i]+…+f[i-1][j-is]//由于总体积不可能小于0，因此只能减到j-i*s
可以观察到，后面部分完全一样,f[i,j]=f[i-1][j]+f[i][j-i]
由于只与i-1有关，可以优化成一维的
代码实现

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010,mod=1e9+7;
int n;
int f[N];
int main(){
    cin>>n;
    f[0]=1;//选体积恰好是1，只有一种选法
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            f[j]=(f[j]+f[j-i]) %mod;
        
    
    cout<<f[n]<<endl;
}

其它做法：

状态表示f[i,j]:所有总和是i且恰好表示成j个数的和的方案的数量
状态计算：(比较难想)
- 分为两类：1. 方案中最小值是1 2. 方案中最小值大于1
- 最小值是1，则可以表示为f[i,j]=f[i-1.j-1]//加上一个1，和为j
- 最小值大于1：集合中每个数字都是严格大于1，那么集合中可以每个数都减去1，f[i,j]=f[i-j,j] //和是i-j，有j个数的方案
- f[i,j]=f[i-1,j-1]+f[i-1,j]
ans=f[n,1]+f[n,2]+…+f[n,n]
- 代码实现

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010,mod=1e9+7;
int n;
int f[N][N];
int main(){
    cin>>n;
    f[0][0]=1;//选体积恰好是1，只有一种选法
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            f[i][j]=(f[i-1][j-1]+f[i-j][j]) %mod;
    int res=0;
    for(int i=1;i<=n;i++) res=(res+f[n][i])%mod;
    
    cout<<res<<endl;
}

蒙德里安的梦想

N*M棋盘分成若干个1*2的长方形有多少种方案
结果：可能可以分割，可能无法分割

StudySHUSHU > 数据结构与算法

数据结构与算法

https://mapllle.site/2024/03/04/StudySHUSHU/DSandAlgo/

作者

MAple

发布于

2024年3月4日

许可协议

信息安全技术上一篇

前端其它下一篇

数据结构与算法

数组

常识补充

基础算法

排序算法

快速排序(分治法)

归并排序(分治法)

二分排序

高精度运算

前缀和与差分

前缀和

差分

双指针

打卡题目 最长连续不重复子序列

位运算

离散化

应用:区间的和

区间合并

数据结构

链表

单链表

双链表

栈和队列

Trie树

并查集

堆

哈希表

STL

pair

vector

string

queue priority_queue

stack

deque

set,map,multiset,multimap

unordered_set,unordered_map,unordered_multiset,unordered_multimap

bitset

搜索与图论

DFS

BFS

树和图

拓扑排序

最短路

朴素Dijkstra算法

堆优化版的Dijkstra算法

Bellman-Ford算法

SPFA算法

Floyd算法

最小生成树

Prim算法

Kruskal算法

二分图

染色法

匈牙利算法

动态规划

背包问题汇总

01背包问题

完全背包问题

多重背包问题

分组背包问题

线性DP问题

数字三角形

最长上升子序列

最长上升子序列 II

最长公共子序列

编辑距离

最短编辑距离

区间DP

石子合并

计数类DP

整数划分

蒙德里安的梦想

打卡题目最长连续不重复子序列