算法

前言

翻笔记的时候发现一不留神写了这么多字，所以想到来汇总一下所有的算法笔记，也算是记录自己的大一吧。

真正的败狗之路也就是在写了这么多笔记后竟然有望得到0个奖项。

祝笔试算法全过。🙌

第一章基础算法

快速排序与快速选择

快排的基本思想是分治

假设有一串左边界为l右边界为r的数组，用快排对其排序需要三步

1.确定一个数组内的值用来划分数组

这个数一般选用a[l],a[r],a[(l+r)/2]这三种（即左边界右边界和中间值）

2.对于原数组进行划分。

即以某一个位置为界限，该位置左边全都是小于分界值的，右边的数全都是大于分界值的。

在这一步中需要两个指针i和j分别从左右开始遍历数组。

以i从左边开始遍历，j从右边开始遍历为例。

如果i指向的数字小于分界值，则i右移一位继续判断；如果j指向的数大于分界值，则j左移一位继续判断

如果两边都不再执行指针的移动，则说明两边的指针指向的数与需要的条件恰恰相反，故交换这两个数，然后继续判断。

这样的过程保证了i指针左侧的值全是小于分界值的，j指针右侧的指针全是大于分界值的，故而当ij指针相遇或者ij指针互相穿过的时候，整个数组就完成了排序。

3.对分出的两个区域进行递归处理

即是对每一个区域再次进行步骤2的过程直到最后区域被缩减到一个即完成了排序

给出快排函数的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void quick_sort(int q[],int l,int r)
{
    if(l>=r) return ;
    int x=q[l],i=l-1,j=r+1;//是因为后面用了dowhile循环，是先移动再判断，故两个指针恰好在左右边界的两侧
    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);//即对右部分再次进行排序
    //根据以上代码可知，j不断向左移动后最终变为左边界-1，此时对于第一个递归l>j，会直接返回
    排序结束
}

4.快速选择

快选是在快排的基础上进行的，用于从中选出第k小（大同理）

根据快排的原理可以看出，每次左分区的数一定都小于右边界的数，故而想要选出第k小的数可以通过每个分区的长度去简化排序的次数

比如左边界的长度l1大于等于k，那么k一定会在左边界中，故只需要在左边界中进行递归，最终找到这个点数

如果左边界l1的长度小于k，那么k一定会在右边界中，故只需要在右边界中进行递归，但需要注意的是，在右边界中，应该是k-l2小的数。

需要注意的是，在每一次递归中都需要更新长度。

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int quick_choice(int l,int r,int k)
{
    if(l==r) return a[l];//最后区间缩小到只含一个数了那么这个数肯定就是答案
   //以下与快排相同
    int x=a[l],i=l-1,j=r+1;
    while(i<j)
    {
        do i++;while (a[i]<x);
        do j--;while (a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    
    
    int s1=j-l+1;//计算左边界长度
    
    //上面已经解释过为什么这么递归了
    if(s1>=k) return quick_choice(l,j,k);
    return quick_choice(j+1,r,k-s1);
}

归并排序

归并排序的基本思想也是分治，但不同于快排的是分界线就是数组的中间位置

1. 基本步骤

1.以中间位置为分界线，将数组分成两部分

2.递归两部分，使这两部分都变成有序序列

3.将这两部分有序序列合并成一个有序数组，从而完成排序

在合并的过程中需要使用双指针算法

即对于两个有序序列，分别设置一个指针指向最左侧（即指向最小的数字）

每次都判断两个指针指向的数字，哪边的数字小就把这个数字写进最终数组，并将这个指针移动，另一个指针依然不动

其中含有一种特殊情况是其中一个数组的指针已经指到了右边界，那么这个时候只需将另一个数组的剩余部分全部写入即可

现给出代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 k=0,i=l,j=mid+1;//k用于储存临时的答案数组的遍历，i为第一部分的指针，j为第二部分的指针
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j]) temp[k++]=a[i++];
        else temp[k++]=a[j++];
    }//该段与上面排序原理的解释一致
    
    while(i<=mid) temp[k++]=a[i++];
    while(j<=r) temp[k++]=a[j++];//这一段代码使得一部分结束循环后，剩余的数组的部分被全部写入答案
    
 
    for(i=l,j=0;i<=r;i++,j++) a[i]=temp[j];
    //将临时答案里的每个数复制到原数组里去 最后结束这个函数
}

回归头来进一步地看，其实归并排序中最重要的点还是它归并时候的思路即我们使用双指针去遍历两个数组不断比较指针指向的值使得答案数组有序的过程。

在很多关于两个序列合成一个序列的问题中都可以得到应用。

2.归并排序中求逆序对

假设一个数组中的每个数都与其位置组成一个二元数对<a[i],i>，那么逆序对的定义即是a[i]>a[j]&&i<j

可以知道，在归并排序的第三步合并数组时，对两个数组进行指针遍历的过程中，判断大小的过程中恰好可以用来判断逆序对。

在归并的过程中，最小的数字先写入，那么当我们在第一个序列里找到了一个a[i]>a[j]（第二序列中的一个数）时，先写入a[j]，那么a[i]后面的所有数都可以与a[j]构成一个逆序对（因为两个序列已经是有序的了）

所以我们只需要在归并过程中对大于的情况多加一条计算逆序对的即可

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int merge_sort(int a[],int l,int r)
{
    if(l>=r) return 0;

    int mid=(l+r)/2;
    int re=merge_sort(a,l,mid)+merge_sort(a,mid+1,r);//递归到最后得到所有逆序对对数
    int i=l,j=mid+1,k=0;
    int temp[10000];
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j]) {
            temp[k++]=a[i++];
        }
        else {
            temp[k++]=a[j++];
            re+=mid-i+1;//实现上面解释的逆序对查找方法
        }
    }
    
    while(i<=mid) temp[k++]=a[i++];
    while(j<=r) temp[k++]=a[j++];
    for(i=l,k=0;i<=r;i++,k++) a[i]=temp[k];//注意虽然这里的目的是求逆序对对数，但每次依然要更新a数组因为要递归得到，所以每一次都要递归到正确的数组
    return re;

}

整数二分

整数二分法的目的是通过不断二分整数所在的范围从而最后得到整数所在的位置。

二分的原理是以中间值将序列分为两部分，然后通过判断mid与条件的关系来逐渐缩小需要判断的范围，使得最后范围缩小到整数所在的位置。（同样地最后返回的值为l或r，因为最后它们相等或差别很小）

1.整数二分

通过对判断条件的选择，二分法的模板分为两种，以一个例子来看，比如我们需要在一段数组中找到x的范围，我们先确定mid（即中间值），如果mid>=x，那么可知x的范围一定在mid的左侧，那么就把右边界更新为mid，x的范围肯定就在l到mid之间；反之mid<x的话，可知一定在mid的右侧，所以将左边界更新为mid+1，x的范围肯定就在mid+1到r之间。

故而两种模板就分别是更新左边界和右边界的问题，根据更新的不同中间值的定义也不同，这一点在下面的代码中详细解释

注意二分法的前提是我们需要写一个判断的条件，现在我们假设这个判断条件是

在使用二分法解题时，首先要确定左右边界，然后最重要的一定是check判断条件的选择，要根据题意找出这个条件

1
2
3
4
5
6
7
bool check(int x)
{
    if(x>k) return true;
    return false;
}
//此处的k是需要输入的，即需要判断的数
//即这个数大就为真，小就为假
模板1
1
2
3
4
5
6
7
8
9
int bsearch1(int l,int r)
{
    while(l<r) {
        int mid = (l + r) / 2;//一定要注意mid的计算一定是要在while循环中进行的，才能每次更新
        if (check(a[mid])) r = mid;//这段即是上面判断的中间值比所找值大，所找值一定在左侧
        else l = mid + 1;
    }
    return l;
}
模板2
1
2
3
4
5
6
7
8
9
10
int bsearch(int l,int r)
{
	while(l<r)
	{
		int mid=(l+r+1)/2;
		if(check(a[mid])) l=mid;
		else r=mid-1;
	}
	return l;
}

可以看出来，整数二分的while条件是l<r，即这个序列中还含有元素

现在我们来看浮点数二分，最大的区别是我们需要用while条件去判断精度，一般地，题目要求保留几位小数我们就在while条件中多加两位，譬如说题目要求精度为两位小数，那么我们可以写r-l>0.0001

2.浮点二分：

同时还要注意的是，浮点二分中不存在复杂的边界问题，所以在更新边界的时候不用考虑加一减一的问题，模板如下

1
2
3
4
5
6
7
8
9
double bsearch(double ans)
{
	while(r-l<”精度的位数加2“)
	{
		double mid=(l+r)/2;
		if(check(mid)) l=mid;
		else r=mid;
	}
}//当然具体怎么换边界还是根据check函数以及题意来确定

现给出一道例题来展示浮点二分

image-20241023165205249

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cmath>
using namespace std;
double a,b,c,d;
double hanshu(double x)
{
    return a*pow(x,3)+b*pow(x,2)+c*x+d;
}
int main()
{
    cin>>a>>b>>c>>d;
    int cnt=0;
    for(int  i=-100;i<=100;i++)
    {
        double l=i;
        double r=i+1;//由于两根的差的绝对值大于等于1，故而每个长度为1的区间至多只有一个根，故基准的左右边界就是遍历的i和i+1
        double x1=hanshu(l);
        double x2=hanshu(r);
        if(x1==0) {
            printf("%.2f ",l);
            cnt++;
        }
        else if(x1*x2<0)//零点存在定理
        {

            while(r-l>=0.001)//通过while条件来控制二分法的精度
            {
                double  mid=(l+r)/2;
                if(hanshu(mid)*hanshu(l)<0) r=mid;
                else l=mid; //依旧是零点存在定理来更新，但注意这里mid的精度，不用+1，直接使用即可
            }
            printf("%.2f ",r);
            cnt++;
        }
        if(cnt==3) break;

    }
    return 0;
}

3.二分答案

二分答案即是用二分的方法枚举取得答案，很像是对二分的逆过程，不断对范围的左边界或右边界进行调整，以逐渐找到最满足要求的答案。

二分答案实际上也是一种枚举，但其使用需要条件，即序列必须是单调的闭区间。

二分答案实际上就是一个求最优解的过程，“最优解一定可行，但可行解不一定最优”，每次满足check函数就相当于找到了一个可行解，那么由于序列是有序的，所以知道这个可行解的前面（或后面）一定也都是可行解，从而缩小可行解的范围，最终得到那个最优解。

用一道例题说明问题

image-20241023172621700

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;
const int N=1000100;
int a[N];
int n,k;

bool find(long long x)
{
    long long ans=0;
    for(int i=0;i<n;i++) {
        ans+=a[i]/x;
    }
    if(ans>=k) return true;
    else return false;
}
//这里是寻找的更新边界的判断条件，即加和每一根木料可以分割多少个，判断最后的总值是否满足条件
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    long long l=0,r=100000001;//此题的数据范围是木材长度的最大值是100000000，所以不妨设一开始的范围是这个最值加1
    这也是二分找答案的初始步骤，即先找出最大的极限位置
    while(l+1<r)//即题目所说的，如果小于1cm则不切割直接输出0（这也是为什么要定义l为0，这样如果不进入循环的话就不用做一个特判，直接能输出0
    {
        long long mid=(l+r)/2;
        if(find(mid)) l=mid;//如果现在的长度已经大于或等于k了，就尝试能不能让长度再大一些，把起始值改成mid       
        else r=mid;//如果现在的长度还小于k，则应该减短长度，把最大值改成mid
    }
    //这里实际上就是不断更新不断尝试直到尝试不动（木块的长度越小就能切割越多块，反之越大块数越少）
    cout<< l <<endl;
    return 0;
}

当然其实二分答案法的最大难度还是在于check的寻找，一些经验是顾名思义地去枚举答案，再反过来看这个答案会影响什么，从而反推回去看某一个变量是否与题目限制冲突了。

高精度

高精度是针对特别大的数字之间的加法，数字的长度甚至可能是数字的位数小于等于十的九次方。

注意，高精度的四则运算的基本方法就是让计算机像人一样去计算！

由于数字可能特别大，所以我们以字符串的形式读入数字，并将每一位都扣出来储存进数组中，由于在进行高精度的运算时可能会有进位的问题出现，所以我们用动态长度的vector去储存

为了方便，正好在这里介绍一下vector的用法

vector是一种容器，区别于普通数组，vector的区别主要有二，一是可以储存管理不限于数的多种类型的数据，二是它的大小是根据需要实时更新，动态更新的，（因而也有人称其为动态数组），所以用vector一遍不会有溢出的风险，在使用中更加的灵活易用

1.vector的定义

首先需要加上一个头文件 #include

vector<储存的类型>容器名 如vectorv;

同时也可以用vector储存数组，如vectorv[n];

2.vector的常用函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//这些都是必会的成员函数
size()//返回返回容器中元素个数
begin()//返回头部迭代器
end()//返回尾部+1迭代器
rbegin()//返回逆首部迭代器
rend()//返回逆尾部-1迭代器
front()//返回首个元素
back()//返回尾部元素
push_back()//在末尾添加一个元素
emplace_back()//和push_back()是一样的作用
pop_back()//弹出最后一个元素
empty()//判断是否为空
insert()//在指定位置插入元素
erase()//在指定位置删除元素
clear()//清空容器

size函数可以用来判断vector的长度，不用单独用变量储存同时还可以适配变化的长度

push_back函数用来给vector加上元素（加在最后）

而其余的函数要用再去查吧

遍历vector就用与数组一样的方式即可

1.高精度加法

         一，用数组储存大数，用第一位储存个位数然后依此类推，可以便于在后续进位中直接加一位数（因为vector加元素是从最后一位开始的。

        二，用竖式加法的原理来

计算，即每一位相加，然后再判断是否需要进位，最后放在结果位的是加和对10取的模，然后进位是加和结果/10

所以我们需要三个vector，分别是第一个数，第二个数，和最终的结果，同时还需要一个变量t来记录每次的进位

现在看代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>

using namespace std;
//add函数表示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;//记录进位
    }
    if(t!=0) c.push_back(1);//如果最后一位还有进位，就在前面加1
    return c;
}

int main()
{
    string a,b;
    cin>>a>>b;//大数用字符串读入
    vector<int>m,n;
    for(int i=a.size()-1;i>=0;i--) m.push_back(a[i]-'0');
    for(int i=b.size()-1;i>=0;i--) n.push_back(b[i]-'0');//逆遍历储存进vector

    auto c=add(m,n); //auto变量编译器会自动推导属于哪种变量

    for(int i=c.size()-1;i>=0;i--) cout<<c[i];//逆遍历输出
    return 0;
}

2.高精度减法

一，高精度减法的大数储存方式与加法完全相同（可以确保在进行复合运算时的一致性）

二，一样是采用竖式相减，需要注意的就是不够借1的问题，那么实际上我们只需要用一个变量来记录借的这个数，在每次相减的时候都减去这个数即可

另外，在相减的过程中，由于可能借1可能不借1（可能够减可能不够减），所以我们用一种写法来统一这两种情况，即(t+10)%10

可以进行一些模拟计算来验证可以发现是全面的

还需要注意的一点是减法中我们需要考虑减数与被减数之间的大小关系，从而来判断最后的结果要不要加负号

现在直接来看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <vector>
#include <cmath>

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;
}
//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为借的位数
    {
        t = a[i] - t; //首先要减去借位
        if(i<b.size()) t -= b[i];//如果b还有位数则还要减去b的那一位数
        c.push_back((t+10)%10);  //这一步就是综合了数借1与否的情况
        if(t<0) t=1;	//如果t小于0说明是借了位的，所以下一位要减一
        else t=0; //没有借位
    }
    while(c.size()>1 && c.back() == 0) c.pop_back(); //去掉前导0，让最后的输出结果为数字的形式
    //如果c的长度只有一位且为0那么就不能去掉
    //因为vector中加入的数都在最后面，所以去掉数前面的0应该是从最后一位看起,pop_back用于弹出最后一位数即去掉它，以此可以把数字前所有0去掉
    return  c;

}
 int main()
 {
    string m,n;
    cin >> m >> n;
    vector<int>a,b;
    for(int i = m.length()-1;i>=0;i--) a.push_back(m[i]-'0');
    for(int i = n.length()-1;i>=0;i--) b.push_back(n[i]-'0');
    if(cmp(a,b)) {
        auto c=sub(a,b);
        for(int i=c.size()-1;i>=0;i--) printf("%d",c[i]);
    }
    else {
        auto c=sub(b,a);
        cout << "-";//如果a<b的话，就算b-a并且在前面加上一个负号
        for(int i=c.size()-1;i>=0;i--) printf("%d",c[i]);
    }
    return 0;
 }

3.高精度乘法

这里讨论的是一个高精度的特别大的数去乘以一个相对小的数（可以用int存下），基本思路是大数的每一位都乘以这个小数，然后放在该位的数是这个乘积被10取模的过程，而进位的则是这个乘积除以10的结果

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &a,int b)
{
    vector<int> c;
    int t=0;
    for(int i=0;i<a.size()||t;i++)
    {
        if(i<a.size()) t+=a[i]*b;
        c.push_back(t%10);
        t/=10;
    }
    return c;
}
//可以看出来跟加法的模板挺像的 是不是可以说乘法跟加法是同源的？？
int main()
{
    string m; int b;
    cin >> m >> b;
    vector<int>  a;
    for(int i=m.length()-1;i>=0;i--) a.push_back(m[i]-'0');
    auto  c=mul(a,b);
    for(int i=c.size()-1;i>=0;i--) cout<<c[i];
    return 0;
}

大数×大数的高精度乘法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstring>

using namespace std;

const int maxn=1e6+7;
char a1[maxn],b1[maxn];
int a[maxn],b[maxn],c[maxn*10],lena,lenb,lenc,x;
int main()
{
    scanf("%s",a1);
    scanf("%s",b1);
    lena=strlen(a1);
    lenb=strlen(b1);
    for(int i=0;i<lena;i++)a[lena-i]=a1[i]-'0';
    for(int i=0;i<lenb;i++)b[lenb-i]=b1[i]-'0';
    for(int i=1;i<=lena;i++)
    {
        x=0;
        for(int j=1;j<=lenb;j++)
        {
            c[i+j-1]=a[i]*b[j]+x+c[i+j-1];
            x=c[i+j-1]/10;
            c[i+j-1]%=10;
        }
        c[i+lenb]=x;
    }
    lenc=lena+lenb;
    while(c[lenc]==0&&lenc>1) lenc--;
    for(int i=lenc;i>=1;i--) cout<<c[i];
    return 0;
}

初始化
for (int i = 1; i <= lena; i++) {：外层循环遍历第一个整数 a 的每一位，从最低有效位（个位）开始，直到最高有效位。
x = 0;：每次内层循环开始时，将进位 x 重置为 0。
内层循环
for (int j = 1; j <= lenb; j++) {：内层循环遍历第二个整数 b 的每一位，同样从最低有效位开始。
c[i + j - 1] = a[i] * b[j] + x + c[i + j - 1];：计算当前位的乘积 a[i] * b[j]，加上之前的进位 x 和已经存在的 c[i + j - 1] 的值。这是因为高精度乘法的结果可能跨越多个位，需要累加之前的结果。
x = c[i + j - 1] / 10;：计算新的进位。如果 c[i + j - 1] 大于或等于 10，那么需要将十位以上的部分进位到更高一位。
c[i + j - 1] %= 10;：更新当前位，只保留个位上的数字。
处理最后的进位
c[i + lenb] = x;：在内层循环结束后，如果还有进位 x，则将其添加到 c 数组的下一个位置。
示例
假设 a = 123 和 b = 89，那么 lena = 3 和 lenb = ⅔。我们用数组表示这两个数，从最低有效位开始：

a 数组: [3, 2, 1]
b 数组: [9, 8]
乘法过程如下：

对于 a[1]（即 3）：
c[1 + 1 - 1] = 3 * 9 + 0 + 0 = 27，x = 27 / 10 = 2，c[1] = 27 % 10 = 7
c[1 + 2 - 1] = ¾ * 8 + 2 + 0 = 26，x = 26 / 10 = 2，c[2] = 26 % 10 = 6
c[1 + 2] = 2（处理最后的进位）
对于 a[2]（即 2）：
c[2 + 1 - 1] = 2 * 9 + 0 + 7 = 25，x = 25 / 10 = 2，c[2] = 25 % 10 = 5
c[2 + 2 - 1] = 2 * 8 + 2 + 6 = 24，x = 24 / 10 = 2，c[3] = 24 % 10 = 4
c[2 + 2] = 2（处理最后的进位）
对于 a[3]（即 1）：
c[3 + 1 - 1] = 1 * 9 + 0 + 5 = 14，x = 14 / 10 = 1，c[3] = 14 % 10 = 4
c[3 + 2 - 1] = 1 * 8 + 1 + 4 = 13，x = 13 / 10 = 1，c[4] = 13 % 10 = 3
c[3 + 2] = 1（处理最后的进位）
最终，c 数组为 [7, 6, 4, 3, 1]，倒序输出就是 10947，这是 123 * 89 的结果。

总结
这段代码通过模拟手工乘法的方式，逐步计算每一位的结果，并处理进位，最终得到高精度的乘法结果

4.高精度除法

与乘法类似的，这里讨论的高精度除法中，被除数是高精度的大数，而除数是一个相对小的数，同样可以用int去除

还需要说明的是，这里的除法还是整数除法，在此种我们输出商和余数

直接看代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> div(vector<int> &a,int b,int &r)
{
    vector<int> c;
    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());//在上面的运行过程中，对于c储存的数，高位的数是储存在第一位的，与高精度运算中储存大数的方式相反，故而我们用reverse将其翻转，以达到统一
    while(c.size()>1 && c.back()==0) c.pop_back();//去掉前导0
    return c;
}
int main()
{
    string m; int b;
    cin >> m >> b;
    vector<int>  a;
    for(int i=m.length()-1;i>=0;i--) a.push_back(m[i]-'0');
    int r=0;
    auto  c=div(a,b,r); //这个函数返回的是c，但是也会改变r
    for(int i=c.size()-1;i>=0;i--) cout<<c[i];
    cout<<endl<<r;
    return 0;
}

高精度的四则运算就大概如此，需要注意的就是让计算机像人一样处理数据的一种思想，同时要多熟练和理解这几个模板

前缀和

1.一维前缀和

首先我们定义一个数组a1,a2,a3,…,an，对于这个数组，有对应的前缀和数组s0,s1,s2,s3,…,sn，其中sn=a1+a2+…+an；

即前n个数的和即是sn

需要注意的是，前缀和对应的数组的下标志必须是从1开始数的，且s0是自定义的其为0

前缀和的求法

        一般的，对于si，si=s[i-1]+a[i]                   （不得不说，就是数列的前n项和那一套东西啊）

前缀和的应用，

        前缀和一般用于快速地得到某一个区间的和           **对于[l,r]的区间和，用s[r]-s[l-1]求得**

这也就解释了为什么数组的下标要从1开始，并且需要我们自己去定义s0=0，因为当我们求[1,10]的和时，实际上就是s10，但为了符合一般规律公式，我们应该写成s[10]-s[0]，其中s[o]=0，即就为s10

对前缀和数组的预处理

1
2
s[0]=0;
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];

一维的前缀和十分简单就略过例题吧

2.二维前缀和

二维前缀和实际上是在矩阵中求子矩阵的和 对于一个行列都从1开始的二维数组a[i,j]，对应地有s[i,j]来表示子矩阵的和

image-20241030210410949

例如，如图是s[3,3]所表示的范围，就是所有被标黄的方格内的数字的和，所以可以看出s[i,j]就是以11为左上角，ij为右下角的矩形

由于矩阵之间可能互相重叠，所以存在多加和多减的问题，需要就情况进行加减

计算前缀和数组

s[i,j]=s[i-1,j]+s[i,j-1]-s[i-1,j-1]+a[i,j]

计算(x1,y1)(x2,y2)这一子矩阵中所有和的值

s[x2,y2]-s[x-1,y2]-s[x2,y1-1]+s[x1-1,y1-1]

可以画图动态地理解一下，这里太麻烦了就不画了

差分

差分其实就是前缀和的逆运算

1.一维差分

假设有两个数组分别是a1,a2,a3,…,an和b1,b2,b3,…bn，使得ai=b1+b2+b3+…+bi

则称a数组是b数组的前缀和，b数组是a数组的差分

差分的应用

差分可以运用在需要对a数组中的一段数同时进行加减操作，比如我们要对a数组的l到r都加上一个c

由于a数组是b数组的前缀和，所以，如果我们让b[l]+c就会让a[l]到a[n]的所有数都加上c（因为这个阶段的数实际上都加了这个b[l]），那么为了保证r之后的数没有加c，同理只需要再进行一个操作，即b[r+1]-c,使得r+1到n的数最终没有发生变化。

代码

1
2
3
4
5
void insert(int l,int r,int c)
{
	b[l]+=c;
	b[r+1]-=c;
}
差分数组的构造

在差分中我们不用去考虑具体是怎么构造的，因为我们如果假设a数组全部为0，那么对应的b数组也全为0，当a数组的每一位i的值发生变化时，就相当于在i与i之间插入了一个值，所以构造差分数组的方法就是

1
for(int i=1;i<=n;i++) insert(i,i,a[i]);

好不容易弄懂了，啰嗦两句，为什么这样插入就能够构造出差分数组呢

因为实际上差分数组的构造是b[i]=a[i]-[i-1]，相当于对于每一个位数来说都加了一次减了一次，而这个insert函数中恰好就是一个先加后减的过程，因为左右边界是一样的，所以这次的r+1就会变成下一次的l，同时插入的数又发生了改变，所以这个过程会完全等价于b[i]=a[i]-[i-1]

在这里补充一点，如何使差分数组变成它对应的前缀和数组，只需要

1
for(int i=1;i<=n;i++) b[i]+=b[i-1];

当然啦，也可以继续用a数组去计算，用前缀和的公式即可

1
for(int i=1;i<=n;i++) a[i]=a[i-1]+b[i];

2.二维差分

同样的，有两个二维数组即两个矩阵，使得a矩阵是b矩阵的前缀和矩阵，那么b矩阵则是a矩阵的差分矩阵

可以与二维前缀和类比，其实就是同样的把运算变成整个矩阵的运算，所以不解释太多

应用

对于差分矩阵中的b[i,j]+c就相当于把a[[i,j]为左上角的那个矩阵全部加c，与前缀和一维到二维的转化方式是相同的，不赘述了

让前缀和数组中以x1，y1为左上角，x2，y2为右下角的矩阵中的所有数加上c

1
2
3
4
5
6
7
void insert(int x1,int y1,int x2,int y2,int c)
{
	b[x1,y1]+=c;
	b[x1,y2+1]-=c;
	b[x2+1,y1]-=c;
	b[x2+1,y2+1]+=c;
}
构造

同样进行n，m次插入操作即可

1
2
3
4
5
6
7
for(int i =  1;i<=n;i++)
{
	for(int j=1;j<=m;j++)
	{
		insert(i,j,i,j,c);
	}
}

最后计算前缀和数组某点矩阵的和的形式与前面的前缀和数组中方法完全相同，略过

离散化

首先清楚什么是离散化，离散化是指将一个连续的区间转化为一系列离散的点的过程

可以理解为一种思想，即我们在处理大量的连续的区间内的问题时，很多时候其实只有其中的一些点是需要的，那么这时我们就可以把这个连续的区间问题转化为求这些点的问题

那么我们如何处理这些离散的点就是此算法的关键，我们的想法是把这些离散的点（或这些点的坐标）映射成从1到n的有序的区间，从而在这个更小更简单的区间里去分析问题，同时由于其有序性也就可以在这个区间里使用遍历去解决问题

但需要注意的是，映射的过程中，待离散化的元素是可能重复的，比如进行操作的和区间的点重复了，所以每次还需要对这些离散的点进行去重，从而使得映射的值是唯一的。

然后来讨论如何求这个映射的问题，这里的映射实际就是找这些点在区间内的位置，所以可以用二分查找的方法去找到每一个值对应的点的位置

区间和

image-20241105101301168

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef pair<int,int> pa; //自定义 pair对 的名称，

vector<int> all;//储存所有需要离散化的值
vector<pa> add,qiu;//储存每次进行的操作，和每一次访问需要求的区间

const int N = 300010;
int n,m;
int a[N],s[N];
//用于找出需要离散的值的映射
int find(int x)
{
    int l = 0,r = all.size()-1;
    while(l<r)
    {
        int mid = l + r >> 1;
        if(all[mid] >= x)  r = mid;
        else l = mid + 1;
    }
    return r+1;
}

int main ()
{
//完成读入操作
    cin >> n >> m;
    for(int i = 0 ; i < n ;i ++)
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x,c});
        all.push_back(x);
    }
    for(int i = 0 ; i < m ; i ++)
    {
        int l,r;
        cin >> l >> r;
        qiu.push_back({l,r});
        all.push_back(l);
        all.push_back(r);
    }
//
    sort(all.begin(),all.end());
    all.erase(unique(all.begin(),all.end()),all.end());

    for(auto item:add)
    {
        int x = find(item.first);
        a[x]+=item.second;
    }

    for(int i = 1;i <= all.size() ; i ++) s[i]=s[i-1]+a[i];

    for(auto item : qiu)
    {
        int l = find(item.first);int r = find(item.second);
        cout << s[r] - s[l-1] << endl;
    }
    return 0;
}

区间合并

区间和并实际上就是一个求并集的过程

即每次当两个区间有交集的时候我们就对这两个区间取并集，把右边界更新成较大的那个

image-20241109181504217

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> pp;

int n;
const int N = 400020;  // 这里不需要这么大的常量，可以根据实际情况调整
vector<pp> all;

// 合并重叠区间
void merge(vector<pp> &all) {
    if (all.empty()) return;

    // 首先按起点排序
    sort(all.begin(), all.end());

    vector<pp> res;
    int l = all[0].first, r = all[0].second;

    for (size_t i = 1; i < all.size(); ++i) {
        if (all[i].first <= r) {
            // 当前区间与之前的区间重叠，更新右端点
            r = max(r, all[i].second);
        } else {
            // 当前区间与之前的区间不重叠，将之前的区间加入结果
            res.push_back({l, r});
            l = all[i].first;
            r = all[i].second;
        }
    }

    // 加入最后一个区间
    res.push_back({l, r});

    all = res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int q, p;
        cin >> q >> p;
        all.push_back({q, p});
    }

    // 合并重叠区间
    merge(all);

    // 计算所有燃烧位置的总长度
    int total_length = 0;
    for (const auto &interval : all) {
        total_length += interval.second - interval.first;
    }

    // 输出总长度
    cout << total_length << endl;

    return 0;
}

当然有些时候我们合并区间后还会添加前缀和等使用，视情况而定即可

第二章数据结构

栈和队列

栈和队列都是一种容器。其不同点在于存放的顺序和取用顺序的不同

image-20241112112018641

栈如图1，其元素只能从上口取出，所以先进去的元素会在最后才出来

队列如图2，其元素是从下端掉出的，所以先进去的元素会最先掉出来

用数组模拟栈和队列

1.栈

1
2
3
4
5
6
7
8
9
10
11
12
//栈的定义
int skt[N];//数组定义栈    int tt; //tt充当记录栈底的指针
//往栈中插入元素
skt[++tt] = x;      //因为元素是从下面涨到上面的
//弹出元素
tt --;
//判断栈是否为空
if(tt>0) not empty
else empty            //即当栈顶还存在时就不为空
//栈顶
skt[tt];

image-20241112164657033

2.队列

1
2
3
4
5
6
7
8
9
10
//队列的定义
int q[N]//数组定义队列      int hh,tt//分别表示头和尾，（就是习惯定义上的上和下哦，结合上面的图）,注意队列实在队尾插入其元素，在队头弹出元素
//插入
qq[++tt] = x //队尾，故而指针向下变大
//弹出元素
hh++  //指针右移，前面的元素就被弹出
//判断队列是否为空
if(hh<=tt) not empty
else empty

image-20241112164440317

3.使用场景的总结

如何在题目背景中抽离出栈和队列的背景？

    着重关注题目中元素的剔除方式：如果是先进先出则用队列储存，如果先进后出则用栈储存。

4.单调栈和单调队列

1.单调栈

单调栈适用的模型是求出数轴上左侧小于x且离x最近的数（右侧同理），image-20241113154629298

栈元素从顶端弹出，所以我们每次判断顶元素是否大于x，如果大于x就直接弹出，这样可以简便地使整个栈中地元素都是单调递增的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
const int N = 100020;
int skt[N], tt;
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        while (tt != 0 && skt[tt] >= x)
            tt--;
        if (tt != 0)
            cout << skt[tt] << " ";
        else
            cout << -1 << " ";
        skt[++tt] = x;
    }
    return 0;
}

2.单调队列

Trie树

Trie树是一种高效存储和查找字符串集合的数据结构，其用类似树枝的方式来储存字符串元素，即每一个节点后可能有若干个子节点，（最初的一个节点称为根节点），最后每一条路径就代表一个储存的字符串，同时，对于每一个字符串结束的节点可以做一个标记方便进行查询操作

大概的图示如下

image-20241118102053450

一道应用的例题，维护一个字符串集合，支持插入字符串x和查询字符串出现次数的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//对于一个字母组成的字符串，可以考虑将字母a~z映射成数字的0~25
//我们用p来记录当前节点，son数组来记录这个节点上的元素，idx用来记录当前使用的下标，下标是0的点既是根节点又是空节点
const int N = 100010;
int son[N][26], cnt[N], idx;

//插入操作
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;//那么就创造一个子节点，++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];
}

从这里可以看出trie树高效的原因在于其让前缀相同的字符串共用前缀从而提高了效率

在这里介绍一个有意思的地方，根据树的性质会发现它在储存二进制数字时有优势（相当于只由01构成的字符串）所以从某种程度上来讲，树能够用来储存计算机中的一切信息

并查集

trie树的另一个重要的操作是并查集，即两种操作，一是将编号为a和b的两个数所在的集合合并到有个集合中，二是查询编号为a，b的两个数是否在同一个集合中

image-20241118171513171

问题4：针对问题2的路径压缩优化 ： 

1
2
3
4
5
int find(int x)
{
	if(p[x]!=x) p[x] = find(p[x]);
	return p[x];
}

由上可以看出树中元素的关系是相互的，对于任意一个元素，我们既可以去寻找它的子节点也可以寻找它的父节点，区别是一个是创造路径，一个是对已有的树集合进行查找。–>见并查集操作

trie树可以用来作为集合来便于研究，一般地我们用根节点来做它的编号–>见合并集合

种类并查集

当题目中的元素之间有不同的关系时（如敌人和朋友），我们可以将原始的并查集扩大n倍（如果有n种关系），那么每一种并查集的含义都不一样，最后我们通过对每一个节点的父节点的比较来确定它们是什么关系。

初始化

1
2
3
4
5
6
//假设有n个元素,关系分为本身，猎物，天敌
for(int i = 1 ;i <= 3*n;i++)
{
	p[i] = i;
}
//假设这里的三种关系分别是本身，猎物与天敌，那么x为本身，x+n为猎物，x+2*n即为天敌

注意对关系之间的处理

关系一般是相互的，当我们确定了两种元素的关系之后，就要去合并对应的两棵树从而满足关系

1
2
3
4
//比如我们已知了x吃y，那么需要合并的关系如下
merge(x,y+2*n);//x是y的天敌
merge(x+n,y);//x的猎物是y
merge(x+2*n,y+n);//x的天敌是y的猎物（环形关系）

带权并查集

Q1 定义

在对并查集进行路径压缩和合并操作时，这些权值具有一定属性，即可将他们与父节点的关系，变化为与所在树的根结点关系。

也就是说。权值代表着当前节点和父节点之前的关系（即使经过了路径压缩），所以我们可以通过该节点与父节点这几件的关系来表示同一棵树下两个节点的关系。

Q3权值到底代表了什么

在题目对元素进行了种类的划分后，我们可以用权值的不同来区分种类的不同从而完成对种类的分辨。

故而这也是对种类并查集的一种处理方法。

Q2权值的转移

在合并操作中不能把权值直接进行赋值，而应该先推出需合并的两个节点a，b各自与根之间的关系才能实现树权值的连接

image-20241130142002673

而权值应该根据题目的要求而确定。

是的

好无聊

现在只能看你的笔记了

还可以帮你改改错

详见洛谷P2024食物链

堆

1.堆的定义

堆实际上是一个完全二叉树，完全二叉树的意思是除了最后一排节点之外，每一个节点都不为空并且每一个节点都含有两个子节点，并且最后一排节点从左到右顺序排列

堆分为小根堆和大根堆，小根堆的含义为根节点为整个堆中的最小值，并且从上到下元素逐渐变大；大根堆的含义是根节点为整个堆中的最大值，并且从上到下元素逐渐变小

2.根的存储

根是用一维数组储存的，存储规则如下

image-20241119112637430

故对于每一个堆我们用一维数组h[n]来定义，用size来记录这个堆或者说这个数组的长度

这种特殊的存储方式决定了堆的更改，添加，删除操作，即在数组的末尾进行元素的更改即可，详见下

3.堆的操作

 首先介绍实现堆的各种操作的*两个基本操作*，up和down  ，up即是让某个元素（或节点）向上调整，down即是让某个元素（或节点）向下调整

Q1如何实现down操作：

为了维护小根堆的从上到下元素从小到大的性质，我们在每一次down之前先找到该节点和它的两个子节点之间的最小值，再把这个最小值和这个元素交换，一直到无法操作即最小值就是这个元素为止

需要注意的是每次down操作的索引是脚标而不是元素的值哦

1
2
3
4
5
6
7
8
9
10
11
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)
	{
		swap(h[u],h[t]);
		down(t);
	}
}

Q2如何实现up操作：

基本逻辑原理同上，唯一不同的是，我们要让小的数往上走，需要判断往上走到什么时候

1
2
3
4
5
6
7
8
void up(int u)
{
	while(u / 2 && h[u / 2]>h[u])
	{
		swap(h[u/2],h[u]);
		u/=2;
	}
}

4.堆中的一些元素处理

Q1插入一个数

由于在数组中储存，所以加在末位最方便

1
2
heap[++size] = x;
up(size);

Q2求集合中的最小值

对于小根堆当然最小值就是根节点

1
heap[1];

Q3删除最小值

这里的删除其实是用覆盖来实现的，即我们让最后一个值覆盖第一个值，然后再把原来的最后一个值删去，就达到了删除最小值的要求

1
2
3
heap[1] = h[size];
size -- ;
down(1);

Q4删除任意一个元素

同理用覆盖法实现

1
2
3
heap[k] = heap[size];
size -- ;
down(k);

Q5修改任意一个元素

与前面不同的点在于，前面的点用最后一个值覆盖，故一定比原数大，为维护堆的性质只需要down一遍就可以了

而这里任意的修改大小不一定，所以我们选择down一遍再up一遍，其二只会执行一个，这样不管如何都会维持堆的性质

1
2
3
heap[k] = x;
dowm(k);
up(k);

特殊情况是当我们需要对第k个插入的元素进行处理时，需要额外维护两个数组，第一个数组用来记录插入顺序k指向的堆中的位置（即元素的下标），第二个数组用来记录堆中的元素的值对应的插入顺序

必须用两个相互的数组记录的原因是为了让堆在进行down和up操作的时候不会扰乱插入顺序与元素之间的关系

因此，在这样的情况下需要自己定义一个swap来进行交换

1
2
3
4
5
6
7
void heap_swap(int a,int b)
{
	swap(ph[hp[a]],ph[hp[b]]);
	swap(hp[a],hp[b]);
	swap(h[a],h[b]);
}
//在上述的各种操作中将swap转化为heap_swap即可

还需要补充一下在插入过程中怎么维护这几个数组

1
2
3
4
5
int size,m = 0;
cin >> x;
ph[m] = size; hp[size] = m;
h[size] = x;
up(size);

对顶堆

链表

顾名思义，链表就像一条链子一样排布，故特点是每一个节点与前后的关系，并且可以单独分析每一个节点

链表的主要作用

1.单链表->邻接表->用来储存树和图

2.双链表->用来优化某些问题

链表上给的数据存储结构单元就是节点，类似于数组中的位置。

每一个节点会包含：

1.它自身储存的数据

2.一个或两个用来指向下一个或上一个节点位置的链接

（在单向链表中，节点只记录后一节点的链接，而双向链表则前后都有）

用指针实现的链表

我们一般用struct结构体 来存储链表节点

1
2
3
4
5
6
struct Node{
	int value;
	Node *next;//指针来记录链接
	//如果是双向链表的话
	Node *prev;
}

一，单向链表

1.初始化

头节点指针赋值为空

1
Node *head = NULL;//NULL指针表示空节点，时标准库中值为0的一个常量

2.单向链表的方式

是从head节点开始到NULL指针结束，每个节点记录下一个节点是谁的数据结构

3.单向链表的插入

Q1如何在某个节点后添加一个节点

与上面说的同理，其实就是在两个链接间重建新的链接给它们搭一个桥，由于是单向的故我们只需要改变next指针即可

1
2
3
4
5
void Insert(Node *p.Node *now)//在p节点后插入now节点
{
	now->next = p->next;
	p->next = now;
}

Q2如何在头节点前插入节点

1
2
3
4
5
void Insert(Node *now)
{
	now->next = head;
	head = now;
}

4.单链表的删除

Q1在p节点之后删除now节点

1
2
3
4
5
void Delete(Node *p.Node *now)
{
	p->next = now->next;
	now->next = NULL;
}

Q2删除第一个节点（头节点）

直接改变头指针即可

1
2
3
4
void Delete()
{
		head = head->next;
}

5.链表的构建

现在以按顺序排列几个数字为例子来用链表解决问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>

using namespace std;

struct Node{
    int value;
    Node *next;
} a[81], *head;

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n;i++)
    {
        cin >> a[i].value;
        if(head == NULL || a[i].value < head->value)
        {
            a[i].next = head;
            head = &a[i];
        }
        else{
            for (Node *p = head; p; p = p->next)
            {
                if(p->value<a[i].value&&(p->next == NULL || p->next->value>a[i].value))
                {
                    a[i].next = p->next;
                    p->next = &a[i];
                    break;
                }
            }
        }

    }

    for (Node *p = head; p;p = p->next)
    {
        cout << p->value << " ";
    }
}

在用指针实现链表的时候重要的还是厘清指针与数值之间的关系以及指向，并且恰当地表示

二，双向链表

与单向链表最大的区别就是它会记录指向后面的指针和指向前面的指针

双向链表的所有操作中与单项联编不同的点就是需要额外去维护这个节点指向前面的prev指针，其他是完全同理的操作

1.初始化

除了头节点指针赋值为空外，也需要维护尾节点指针

1
Node *head = NULL,*tail = NULL;

2.在p节点后插入now节点

与单链表插入的区别只在于要重新维护一个prev指针

1
2
3
4
5
6
void Insert(Node *p,Node *now)
{
	Node *q = p->next;
	p->next = now; now->prev = p;
	now->next = q;q->prev = now;
}

在头节点前插入

1
2
3
4
5
6
void Insert(Node *now)
{
	now->next = head;
    head->prev = now;
    head = now;
}

在尾节点后插入也是完全同理的操作，只是维护的顺序不一样而已（一个插在前面一个插在后面）

3.删除一个now节点

1
2
3
4
5
6
void Delete(Node *now)
{
	Node *p = now->prev,*q = now->next;
	p->next = q;
	q->prev = p;
}

删除尾节点

1
2
3
4
5
void Delete(Node *now)
{
	tail = now->prev;
	tail->next = NULL;
}

删除头节点也完全同理，只是改变的是它的next指针而已

三，循环链表

即在单向链表的基础上将最后一个节点的next指针指向头节点，如果是双向链表的话就再将头节点的prev指向最后一个节点，从而行成的一个环状结构

循环链表正如其形状，最适用在环形问题上，如约瑟夫环

用数组模拟实现的链表

一，单向链表

1.模拟方式

同样地需要定义头节点，每个节点的value，和指向下一项的指针，但不同的是value和指针我们都分别用数组来实现，它们之间的联系用下标来实现。

1
2
3
const int N = 100010;
int head,e[N],ne[N],idx;
//head表示链表的头节点，数组e用来储存每个点的值，数组ne用来记录每个节点的next指针，idx作为一个索引指针，表示现在用到了哪一个点

从head指向的第一个节点开始，从0开始计数，这个计数就是这个节点的下标。最后一个节点指向的空节点令为-1.

对于头节点head来说，它的值即是它指向的节点的下标，所以初始化为-1是因为此时指向的是空节点。在对head进行赋值时，一般使用的是索引指针idx。

2.初始化
1
2
3
4
5
void chu()
{
	head = -1;
	idx = 0;
}
3.插入操作

在头节点后插入一个节点

1
2
3
4
5
6
7
void addtohead(int x)
{
	e[idx] = x;
	ne[idx] = head;
	head = idx;
	idx ++;//表示当前节点已经使用过了
}
**在下标为k的点后插入一个点**

1
2
3
4
5
6
7
void add(int k,int x)
{
	e[idx] = x;
	ne[idx] = ne[k];
	ne[k] = idx;
	idx ++;
}
4.删除操作
**在下标为k的点后删除节点**

1
2
3
4
void delete(int k)
{
	ne[k] = ne[ne[k]];//让它直接指向下下个就行了
}

二，双向链表

同样地，双向链表与单向链表的差别就是会同时维护左指针和右指针，我们只需要多开一个数组来表示左指针（前指针即可）

1.模拟方式

在这里为了方便，就不单独定义头节点和尾节点，而是用下标为0和1的两个点来表示边界即头节点和尾节点

1
2
3
const int N = 100010;
int e[N],l[N],r[N],idx;
//数组e用来储存每个点的值，数组r用来记录每个节点的next指针，数组l用来记录每个节点的prev指针，idx作为一个索引指针，表示现在用到了哪一个点
2.初始化
1
2
3
4
5
6
void chu()
{
	//0表示左端点，1表示右端点
	r[0] = 1,l[1] = 0;
	idx = 2;//01已经被占用了
}

由于在这里没有单独去令头尾节点，所以后面的几种操作我们都只介绍在下标为k的点左右进行操作进行即可。

3.插入操作
**在下标为k的点右边插入一个点**

1
2
3
4
5
6
7
8
9
void add(int k,int x)
{
	e[idx] = x;
	r[idx] = r[k];
	l[idx] = k;
	l[r[k]] = idx;
	r[k] = idx;
//一定要注意改变的顺序
}

我们只需要调用这个函数就可以实现在这个节点 的左边插入一个点

1
void add(l[k],int x);
4.删除操作
**在下标为k的点后删除节点**

1
2
3
4
5
6
void delete(int k)
{
	r[l[k]] = r[k];
	l[r[k]] = l[k];
	//同样地，只需要忽略被删除的点即可
}

在做链表相关的问题中，我们画出链表的图，就能理解以上这些操作的逻辑，也能便于自己写出来这些操作了。

哈希

1.简介

哈希函数实际上就是把一些想要查询的东西映射成一些更便于查找（一般就是数字）的函数

可以将想要查询的那个大集合映射到一个小集合中，这个小集合储存到数组中，就称为哈希表

2.值冲突解决方法

由于哈希是用某种关系让值映射到一个数组，故而有可能不同的数字会映射到同一个结果上去，故而需要处理这样的值冲突

Plan A 跳过法

发生冲突后往后找到第一个空位置插入值。可以定义这样的函数没让每次插入的位置往后＋任意的固定值

但这样的方法在面对一个很满的哈希表时，会耗费大量的时间复杂度在搜素空值上，这也就失去了哈希表的意义，所以一般我们不采用这样的方法

Plan B 容器法

为了让哈希表里的每个位置都能储存多个值，可以在每个位置都开一个容器来使得位置上可以储存多个值，这里可以开一张链表，更好地，可以开一个vector简单地处理这种动态储存空间

3.哈希函数的设计

（偏理论，看看得了）

image-20241125201633226

4.字符串哈希

1.用哈希函数将字符串转化为数字

对于字符串image-20241125203146729

哈希函数如下

image-20241125203118362

代码实现

1
2
3
4
5
6
int Hash(char s[],int n)
{
	int res = 0;
	for(int i = 1;i<=n;i++) res = (res * base + (s[i]-'a'+1))%p;
	return res;
}

2.函数的解释

ci跟字符串每个位置上字母有关的数字，一般地我们可以把a到z地数字映射到1~26（这也就是为什么上面会(s[i]-‘a’+1)）

base是指定的数1，一般是一个大于字符串中字符数量（大于ci的最大值）的素数，一般可以取101，137等等

p也是一个自己指定的数，一般是一个比较大的数，如可以取9999954

一般地，当两个字符串的哈希值相同的时候，我们可以认为这两个字符串相同，不用一位一位地进行比较，可以节省时间

3.求任意片段子串的哈希值

以上哈希函数的定义的好处是我们可以使用类似于前缀和的思想快速地得到任意子串的哈希值

First

用a数组记录下计算Hash（c）的中间过程。即

1
a[i] = 	Hash(s1s2...si);

那么对于任意子串 s[l,r] = s[l] s[l+1]…s[r] 的哈希值为

image-20241125205712064

代码实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Hash(char s[],int n)
{
	int res = 0;
	for(int i = 0;i<n;i++)
	{
		res = (res * base + (s[i]-'a'+1))%p;
		a[i] = res;
	}
	return res;
}

int partHash(int l ,int r)
{
	int t = a[l-1] * pow(base,r-l+1)%p;
	return (a[r]-t+p)%p;
}

5.stl库中的hash

在cpp的stl库中有一个数据结构unordered_map可以用来实现大多数的哈希表操作，主要原因是它可以很方便的在两个不同类型的元素之间建立起映射关系

1
unordered_map<K.V> hash//这里是自定义的名称

其中K为要储存的关键字信息的类型，V为与它相关联的一些信息的类型（即映射到的）

比如

1
2
3
4
5
6
7
8
9
10
11
12
13
unordered_map<string,int> hash;

int query(string name){ //查询被查找人的映射值
	if(hash.find(name) == hash.end) ...//这说明在hash表中没有这个人
	return hash[name]; //会返回映射值
}

int main()
{
	hash["ningning"] = 22;
	hash["tutu"] = 33;
	
}

unordered_map中的key值默认支持int double char string key vector等类型。（其他的类型可以自己先写一些函数来处理，在这里不做扩展了）

stl库中的数据结构

image-20241130162439962

第三章搜索与图论

树和图的存储（邻接表）

这里不多说

主要就是在一个数组中存储多个链表

后面题目会涉及到存储

存储方式主要是头插法

#include 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <cstring>  

using namespace std;  

const int N = 100010;  

int h[N], e[N], ne[N], idx;// h为头指针，因为有多个链表所以有多个头  
// 这个链表表示某个数可以直接到哪个数  
//比如1可以直接到3，4在链表表示1->3->4  
void add(int a, int b){// a为头，b为存的值  
    e[idx] = b;  
    ne[idx] = h[a];  
    h[a] = idx++;  
}  

int main()  
{  
    memset(h, -1, sizeof h);  
 }

1.DFS

什么是DFS？

DFS 通常指的是深度优先搜索（Depth-First Search），这是一种用于遍历或搜索树或图的算法。这种算法从根节点（在图的情况下，可以从任意一个顶点开始）开始，尽可能深地探索每个分支，直到达到无法继续深入为止，然后回溯到上一个节点并探索新的路径。这个过程会一直重复，直到所有的节点都被访问过。

有点递归的感觉

将过程想象成一棵树，每种情况都是一个分支

842. 排列数字 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>  
using namespace std;  
const int N=10;  
int n;  
int path[N];  
bool st[N];  
void dfs(int 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])  
    {  
        path[u]=i;  
        st[i]=true;  
        //往下递归  
        dfs(u+1);  
        //恢复现场  
        st[i]=false;  
    }  
}  

}  

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

2.BFS

BFS是广度优先搜索（Breadth-First Search）的缩写，它是一种用于遍历或搜索树或图的算法。这种算法从根节点（在图的情况下，可以是从任意一个顶点开始）开始，然后探索所有与之相邻的节点，之后再对这些节点中未被访问过的邻居进行同样的操作，直到遍历完所有可达的节点。

也就是说对一个点相邻的未被访问过的点进同样的操作，直到遍历完所有点

bfs有一个队列的性质

把每个点存进去然后找这个点的相邻未访问过的点存到队列里然后把队头出队 如此反复

可以看看b站视频演示https://www.bilibili.com/video/BV1uCH1eoEYP?t=119.9

844. 走迷宫 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>  
#include <algorithm>  
#include <cstring>  

using namespace std;  
typedef pair<int, int> PII;   

const int N=110;  

int n, m;  
int g[N][N];// g是给的地图  
int d[N][N];// d表示到初始位置的“距离”  
PII q[N*N];// q存的是点的位置的一个队列  
int bfs(){  
    int hh = 0, tt = 0;  
    q[0]={0, 0};  
    memset(d, -1, sizeof d);  
    d[0][0]=0;// 初始位置（0，0）的距离是0  
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};// 走迷宫走的四个方向的x， y变化的所有可能性  
    while (hh<=tt)   
    {  
        auto t = q[hh++];  
        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] == -1表示当前点未被访问过  
            {  
                d[x][y] = d[t.first][t.second] + 1;  
                q[++tt] = {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]; // 读入  
    }  
    cout << bfs();  
    return 0;  
}

3.拓扑排序

每条边起点在终点的前面的序列就是拓扑序列

此时1 2 3就是拓扑序列

有向无环图（也叫做拓扑图）一定存在拓扑序列

度数的概念：

入度就是一个点有多少条边指向自己，出度就是一个点有几条边出去

本题就是求出其中的拓扑序列

这里主要用BFS实现

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>  
#include <cstring>  
using namespace std;  
const int N = 100010;  
int n, m;  
int h[N], e[N], ne[N], idx;// 这里跟下面的add函数就是邻接表用于存储一个图  
int q[N], d[N];// d表示每个点入度的个数  

void add(int a, int b)  
{  
    e[idx] = b;  
    ne[idx] = h[a];  
    h[a] = idx++;  
 }   
   
bool topsort ()  
{  
    int hh = 0, tt = 0;  
    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];  
            d[j] --;// 删去一个入度因为int t = q[hh++];  
            if (d[j] == 0)q[tt++] = j;// 如果入度为0，相当于q队列的用法，存进来  
        }  
    }  
    return tt == n;  
}  
int main()  
{  
    cin >> n >> m;  
    memset(h, -1, sizeof h);  
    // while循环里先用头插将点存进来点从a指向b，因此存进来的点入度加一  
    while(m --){  
        int a, b;  
        cin >> a >> b;  
        add(a, b);  
        d[b] ++;  
    }  
    if(topsort())  
    {  
        for (int i = 0; i < n; i ++)cout << q[i] << " ";  
    }else puts("-1");  
      

return 0;  

 }

最短路

√4.Dijkstra

题目一定不能存在负权边！！

就是一个一个往下递推

0x3f3f3f3f大约是1x10^9用来定义一个很大的数

850. Dijkstra求最短路 II - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 #include <iostream>  
 #include <cstring>  

 using namespace std;  

 const int N = 510;  

 int n, m;  
 int g[N][N];// g为邻接矩阵   
 int dist[N];// dist为某点到该点的距离   
 bool st[N];// st为该点是否已经被确定最短路   

 int dijkstra()  
 {  
     memset(dist, 0x3f, sizeof(dist));// memset按单字节填充int每个字节被设置为0x3f则每个整数被定为0x3f3f3f3f  
     dist[1] = 0;// 1到自己距离为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]))// 找到未被确定的距离1最小的点(依据贪心，其实也好理解)  
         {  
             t = j;  
         }  
     }  
     st[t] = true;// 这点最短距离确定  
     // 以这点为基准判断其他点的最短路  
     for(int j = 1; j <= n; j ++)  
     {  
         dist[j] = min(dist[j], dist[t] + g[t][j]);  
     }  
 }  
 if(dist[n] == 0x3f3f3f3f)return -1;// dist[n] == 0x3f3f3f3f表示该点未被确定也就是没有路从1到该点  
 return dist[n];// 返回最短路  

 }  
 int main()  
 {  
     scanf("%d%d", &n, &m);  
     memset(g, 0x3f, sizeof(g));  
     while (m --)  
     {  
         int x, y, z;  
         scanf("%d%d%d", &x, &y, &z);  
         g[x][y] = min(g[x][y], z);// 如果遇到重边选择最短的那个(依据题意)  
      }   
     int t = dijkstra();  
       

 printf("%d", t);  

 return 0;  

  } 

而当数据量很大的时候用邻接矩阵N*N会报错

这时候我们可以优化使用邻接表和优先队列的形式

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

 using namespace std;  

 typedef pair<int, int > PII;  
 const int N = 1e5 + 10;  

 int n, m;  
 int h[N], e[N], w[N], ne[N], idx;// h为每个头，e为值，w为每个权重  
 int dist[N];// dist为某点到该点的距离   
 bool st[N];// st为该点是否已经被确定最短路   

 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));// memset按单字节填充int每个字节被设置为0x3f则每个整数被定为0x3f3f3f3f  
     dist[1] = 0;// 1到自己距离为0  
       

 priority_queue<PII, vector<PII>,greater<PII>>heap;// 创建一个升序的优先队列  
 heap.push({0, 1});// 插入第一个元素,fist为距离second为编号  

 while(heap.size()){// 若非空  
     auto t = heap.top();  
     heap.pop();  
       
     int ver = t.second, distance = t.first;// ver是该点，distance是到起始点的距离  
       
     if(st[ver]) continue;// 如果该点已经得出最短路  
     st[ver] = true;  
       
     for(int i = h[ver]; i != -1; i = ne[i])// 以这点为基准判断其他点的最短路  
     {  
         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;// dist[n] == 0x3f3f3f3f表示该点未被确定也就是没有路从1到该点  
 return dist[n];// 返回最短路  

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

 memset(h, -1, sizeof(h));// 邻接表的初始化  

 while (m --)  
 {  
     int x, y, z;  
     scanf("%d%d%d", &x, &y, &z);  
     add(x, y, z);  
  }   
 int t = dijkstra();  

 printf("%d", t);  

 return 0;  

  }

√5.bellman-ford

当存在负权边时可以使用

有边数限制的时候可以用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>  
#include <cstring>  

using namespace std;  

const int N = 510, M = 10010;  

struct Edge{  
    int a, b, w;  
}edges[M];  

int n, m, k;  
int dist[N], backcup[N];  

int bellman_ford()  
{  
    memset(dist, 0x3f, sizeof dist);  
    dist[1] = 0;  
      

for(int i = 0; i < k; i ++)// 处理最多走k条边时的最短路  
{  
    memcpy(backcup, dist, sizeof dist);// 备份，因为这里走的边有限所以mei走一条边要用上一次的距离来计算下面的  
    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], backcup[a] + w);   
    }  
}  

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

int t = bellman_ford();  

if(t == -1)printf("impossible");  
else printf("%d", t);  

return 0;  

 }

6.spfa

  • 判断最短路

    主要是对bellman-ford一个优化

    dist[b] = min(dist[b], dist[a] + w); 当dist[a]不变时dist[b]就不会变小

    spfa就是用队列对这一部分进行优化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    #include <iostream>  
    #include <cstring>  
    #include <queue>  
        
    using namespace std;  
        
    typedef pair<int, int > PII;  
    const int N = 1e5 + 10;  
        
    int n, m;  
    int h[N], e[N], w[N], ne[N], idx;// h为每个头，e为值，w为每个权重  
    int dist[N];// dist为某点到该点的距离   
    bool st[N];// st为该点是否在队列中  
        
    void add(int a, int b, int c)// 邻接表的头插  
    {  
        e[idx] = b;  
        w[idx] = c;  
        ne[idx] = h[a];  
        h[a] = idx++;  
    }  
    int spfa()  
    {  
        memset(dist, 0x3f, sizeof dist);  
        dist[1] = 0;  
          
        
    queue<int> q;// 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])  
                {  
                    q.push(j);  
                    st[j] = true;  
                }  
            }  
        }  
    }  
        
    if(dist[n] == 0x3f3f3f3f)return -1;// -1依据题目  
    return dist[n];  
        
    }  
    int main()  
    {  
        scanf("%d%d", &n, &m);  
          
        
    memset(h, -1, sizeof(h));// 邻接表的初始化  
        
    while (m --)  
    {  
        int x, y, z;  
        scanf("%d%d%d", &x, &y, &z);  
        add(x, y, z);  
     }   
    int t = spfa();  
        
    if(t == -1)printf("impossible");  
    else printf("%d", t);  
        
    return 0;  
        
     }

  • spfa判断负环

    创建一个cnt数组来记录边数

    当cnt数组>=n就代表当前边存在自环且一定是负环（只有负环才会往下更新）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
     #include <iostream>  
     #include <cstring>  
     #include <queue>  

     using namespace std;  

     typedef pair<int, int > PII;  
     const int N = 1e5 + 10;  

     int n, m;  
     int h[N], e[N], w[N], ne[N], idx;// h为每个头，e为值，w为每个权重  
     int dist[N], cnt[N];// dist为某点到该点的距离，cnt记录边数  
     bool st[N];// st为该点是否在队列中  

     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;// q队列存储改变的那个点，因为这个点改变才会导致后面的点变化  
           

     // 将所以点都入队，防止第一个点与后面不相连  
    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])  
                 {  
                     q.push(j);  
                     st[j] = true;  
                 }  
             }  
         }  
     }  

     return false;  

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

     memset(h, -1, sizeof(h));// 邻接表的初始化  

     while (m --)  
     {  
         int x, y, z;  
         scanf("%d%d%d", &x, &y, &z);  
         add(x, y, z);  
      }   

     if(spfa())puts("Yes");  
     else puts("No");  

     return 0;  

      }

√7.Floyd

一个比较简单的算法

可以想象成向量相加的形式

floyd里面三个for循环循序不能变！！！ 否则可能会把没有求出最短路的边拿来用导致出错

854. Floyd求最短路 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>  

 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]);// d[i][k] + d[k][j]“向量相加”  
       
 }  

 int main()  
 {  
     cin >> 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 x, y, z;  
     cin >> x >> y >> z;  
     d[x][y] = min(d[x][y], z);  
 }  

 Floyd();  

 while(Q --)  
 {  
     int x, y;  
     cin >> x >> y;  
       
     if(d[x][y] > INF / 2)puts("impossible");  
     else cout << d[x][y] << endl;  
 }  

 return 0;  

  }

最小生成树

8.Prim

主要解决最小生成树的问题

跟Dijkstra类似但此时求的是到集合的距离

858. Prim算法求最小生成树 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
 #include <iostream>  
 #include <cstring>  

 using namespace std;  

 const int N = 510, INF = 0x3f3f3f3f;  
    
 int n, m;  
 int g[N][N];  
 int dist[N];// dist存到集合的最短距离  
 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;// 如果这个最下的点为INF则表明没有线到集合就是与集合不相连  
​       
​     if(i)res += dist[t];  
​       
​     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;  

 }

√9.Kruskal

这个方法线将权重w排序使得每次循环都用的最短的那条路，这样就可以使得求出来的权值最小

859. Kruskal算法求最小生成树 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>  
#include <algorithm>  

using namespace std;  

const int N = 200010;  

int n, m;  
int p[N];  

struct Edge{  
    int a, b, w;  
    // 自定义排序，按边的权重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()  
{  
    scanf("%d%d", &n, &m);  
      

for (int i = 1; i <= n; i ++ ) p[i] = i;  //并查集初始化  
//读入数据  
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);  

int res = 0, cnt = 0;// res存权重之和，cnt存有多少条边可以来判断是否有生成树  

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",res);  

return 0;  

 }

二分图

10.染色法判定二分图

什么是二分图？

就是可以形成点在左右两个集合里边在中间的图

二分图当且仅当图中不含奇数环

860. 染色法判定二分图 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>  
#include <cstring>  

using namespace std;  

const int N = 100010, M = 200010;  

int n, m;  
int h[N], e[M], ne[M], idx;  
int color[N];// 1和2为不同颜色  

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

// dfs用于给点当前点染色并判断与之相连的点是否符合条件即颜色不同  
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])  
    {  
        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])// 如果为染色  
    {  
        if(!dfs(i, 1))// 如果染色后不满足二分图的条件  
        {  
            flag = false;  
            break;  
        }  
    }  
}  

if(flag)puts("Yes");  
else puts("No");  

return 0;  

}

11.匈牙利算法

怎么说呢

就是左右两个集合匹配问题，如果a想匹配b而b已被匹配但b有别的匹配方案那么b匹配另一个的a匹配b

具体可以看看Acwing上的视频这一课我认为是讲的最好的

AcWing 861. 二分图的最大匹配 - AcWing看他举的例子

861. 二分图的最大匹配 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>  
#include <cstring>  

using namespace std;  

const int N = 510, M = 100010;  

int n1, n2, m;  
int h[N], e[M], ne[M], idx;  
int math[N];// math存储匹配的对象  
bool st[N];// st存储当前点是否被考虑过  

void add(int a, int b)  
{  
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;  
}  
// 匹配算法 成功返回true失败返回false  
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(math[j] == 0 || find(math[j]))// 如过当前点未匹配或者他可以匹配其他的点  
            {  
                math[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", res);  

return 0;  

}


第四章数学知识

1.质数

①试除法判断质数

1
2
3
//只强调写循环条件的时候
 for9int i = 2;i <= n/i;i ++) 
 //其他照旧

②试除法分解质因数

image-20250126153901302

③筛质数

这里介绍线性算法，即用质数筛掉所有以该质数为因子的合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;

int cnt,primes[N];
bool st[N];

void get_primes(int n){
	for(int i = 2;i <= n;i ++){
		if(!st[i]) primes[cnt ++] = i;
		else {
			for(int j = 0;primes[j] <= n/i;j ++) {
			st[i * primes[j]] = true;
			if(i % primes[j] == 0) break; // primes[j]一定是i的最小质因子
			}
		}
	}
}

int main(){
	int n; cin >> n;
	get_primes(n);
	cout << cnt << endl;
	return 0;
}

2.约数

①试除法求约数

image-20250126164736991

②求约数个数

约数个数公式

image-20250126165536547

所以我们需要先分界质因数然后再求指数，用hash表来存就好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;

const int N = 1e7;
const int mod = 1e9 + 7;

int main()
{
    int n; cin >> n;
    unordered_map<int,int>primes; //用来存质因数和它的指数
    while(n --){
        int x; cin >> x;
        for(int i = 2;i <= n;i ++){
            while(x % i == 0){
                x /= i;
                primes[i] ++;
            }
        }
    }
    ll res = 0;
    for(auto prime : primes) res = res * (prime.second + 1) % mod;
    cout << res << endl;

}

③求约数之和

image-20250126174914523

一样的，我们分解质因数然后按照公式计算即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;

const int N = 1e7;
const int mod = 1e9 + 7;

int main()
{
    int n; cin >> n;
    unordered_map<int,int>primes; //用来存质因数和它的指数
    while(n --){
        int x; cin >> x;
        for(int i = 2;i <= n;i ++){
            while(x % i == 0){
                x /= i;
                primes[i] ++;
            }
        }
    }
    ll res = 0;
    for(auto prime : primes) res = res * (prime.second + 1) % mod;
    cout << res << endl;

}

③最大公约数

辗转相除法 欧几里得算法 gcd

1
2
3
4
int gcd(int a,int b)
{
	return b ? gcd(b,a % b) : a;
}

④扩展欧几里得算法

1
2
3
4
5
6
7
8
9
10
11
12
// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}

3.欧拉函数

定义

image-20250218212753454

求法

1、公式求欧拉函数

image-20250218213643606

其中第一行是对N进行分解质因数的结果

第二行是求欧拉函数的公式

代码实现

1
2
3
4
5
6
7
8
9
10
11
int a; cin >> a;
    int res = a;
    for(int i = 2;i <= a / i;i ++){
        if(a % i == 0) {
            res = res / i * (i - 1);
            while(a % i == 0) a /= i;
        }
    }

    if(a > 1) res = res / a * (a - 1);
    cout << res << endl;

2、筛法求欧拉函数

注意，这里是求1~N每一个数的欧拉函数

这里以求1~N的每个数的欧拉函数之和为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;

typedef long long ll;

const int N = 1e6 + 10;
int primes[N],cnt;
int phi[N];
bool st[N];

ll get_eulers(int n)
{
    phi[1] = 1;
    for(int i = 2;i <= n;i ++)
    {
        if(!st[i]) {
            primes[cnt ++] = i;
            phi[i] = i - 1; // 质数的欧拉函数
        }
        for(int j = 0; primes[j] <= n / i; j ++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) {
                phi[primes[j] * i] = primes[j] * phi[i];
                break;
            }
            phi[primes[j] * i] = phi[i] * (primes[j] - 1);
        }
    }
    ll res = 0;
    for(int i = 1;i <= n;i ++) res += phi[i];
    cout << res << endl;
}

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

4.快速幂

用于快速求出a的k次方 % p的结果

image-20250218224555876

1
2
3
4
5
6
7
8
9
10
11
// 返回a ^ k % p
ll qmi(int a,int k,int p)
{
    int res = 1;
    while(k) {
        if(k & 1) res = (ll)res * a % p;
        k >>= 1;
        a = (ll)a * a % p;
    }
    return res;
}

快速幂求逆元

image-20250218224846741

5.高斯消元求线性方程组

image-20250218230839753

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// a[N][N]是增广矩阵
int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )   // 找到绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        if (fabs(a[t][c]) < eps) continue;

        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);      // 将绝对值最大的行换到最顶端
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];      // 将当前行的首位变成1
        for (int i = r + 1; i < n; i ++ )       // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];

    return 0; // 有唯一解
}

第五章动态规划

√背包问题

1.01背包问题

f[i] [j]数组表示前i个物品不超过j体积的价值数

那么我们可以将f[i] [j]分为包含第 i 个物品和不包含 i 两种再求一个max

2. 01背包问题 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>  

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

return 0;  

}

优化:

我们可以将二维优化成一维

将 j 从大到小这样就保证每个 i 只被选一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>  

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 = m; j >= v[i]; j --)  
        f[j] = max(f[j], f[j - v[i]] + w[i]);  

cout << f[m];  

return 0;  

}

2.完全背包问题

跟上面的思路差不多

但是此时我们将f [i] [j]分为包含0个i，1个i， 2个i……

所以max里面应该包含0个i项， 1个i项……

再进行整理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>  

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][j], f[i][j - v[i]] + w[i]);  
    }  

cout << f[n][m];  

return 0;  

 }

优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>  

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

 cout << f[m];  

 return 0;  

  }

3.多重背包问题（数据小的时候）

直接暴力枚举

4. 多重背包问题 I - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>  

using namespace std;  

const int N = 110;  

int n, m;  
int f[N];  

int main()  
{  
    cin >> n >> m;  
    for(int i = 0; i < n; i ++)  
    {  
        int v, w, s;  
        cin >> v >> w >> s;  
        for(int j = m; j >= 0; j -- )  
            for(int k = 1; k <= s && k * v <= j; k ++)  
                f[j] = max(f[j], f[j - k * v] + k * w);  
    }  
      

cout << f[m];  

return 0;  

}

4.多重背包问题（数据大的时候）

我们可以将每个数量拆出来变成01背包问题

怎么拆使得拆出来的数字个数最小呢？

用二进制的方式拆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>  
 #include <vector>  

 using namespace std;  

 const int N = 2010;  

 int n, m;  
 int f[N];  

 struct Good{  
   int v, w;    
 };  
 int main()  
 {  
     vector<Good> goods;  
     cin >> n >> m;  
     for(int i = 0; i < n; i ++)  
     {  
         int v, w, s;  
         cin >> v >> w >> s;  
         for(int k = 1; k <= s; k *= 2)  
         {  
             s -= k;  
             goods.push_back({v * k, w * k}); // 二进制的方式拆  
         }  
         if(s > 0) goods.push_back({v * s, w * s}); // 将剩下的数放进去  
     }  
       

 // 01 背包问题模板  
 for(auto good : goods)  
     for(int j = m; j >= good.v; j --)  
         f[j] = max(f[j], f[j - good.v] + good.w);  
           
 cout << f[m];  

 return 0;  

 }

5.分组背包问题

多重背包问题是这个的特殊情况

代码思路差不多

9. 分组背包问题 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>  

using namespace std;  

const int N = 110;  

int n, m;  
int f[N], v[N], w[N];  


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

for(int i = 0; i < n; i ++)  
{  
    int s;  
    cin >> s;  
    for(int j = 0; j < s; j ++)cin >> v[j] >> w[j];  
    for(int j = m; j >= 0; j --)  
        for(int k = 0; k < s; k ++)  
            if(j >= v[k])  
                f[j] = max(f[j], f[j - v[k]] + w[k]);  
}  

cout << f[m];  

return 0;  

}

线性DP

√6.数字三角形

状态表示+计算

f[i] [j]表示到i行j列最大值

898. 数字三角形 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>  

 using namespace std;  

 const int N = 510, INF= 1e9;  

 int n;  
 int a[N][N];  
 int f[N][N];  

 int main()  
 {  
     cin >> n;  
     for(int i = 1; i <= n; i ++)  
         for(int j = 1;j <= i; j ++)  
             cin >> 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] + a[i][j], f[i - 1][j] + a[i][j]);  

 int res = -INF;          
 for(int i = 1; i <= n; i ++)res = max(res, f[n][i]);  

 cout << res;  

 return 0;  

 }

√7.最长上升子序列（数据小时）

f[i] 为以i为结尾的最长的长度

那么就可以得到他的最长长度等于0 …i - 1中比a[i]小的数的 f 值加1再跟i取max

895. 最长上升子序列 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>  

using namespace std;  

const int N = 1010;  

int n;  
int a[N], f[N];  

int main()  
{  
    cin >> n;  
      

for(int i = 1; i <= n; i ++) cin >> a[i];  

for(int i = 1; i <= n; i ++)  
{  
    f[i] = 1;  
    for(int j = 1; j < i; j ++)  
        if(a[j] < a[i])  
            f[i] = max(f[i], f[j] + 1);  
}  

int res = 0;  

for(int i = 1; i <= n ; i ++) res = max(res, f[i]);  

cout << res;  

return 0;  

}

√8.最长上升子序列（数据大时）

先弄出每个长度子序列的最小值

枚举每个数把他接到小于他的最长的子序列这样就使得出来的子序列最长

用二分的方法找到小于他的最长的子序列

896. 最长上升子序列 II - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>  

using namespace std;  

const int N = 100010;  

int n;  
int a[N];  
int q[N]; // q存储每个上升子序列长度结尾的数的最小值  

int main()  
{  
    cin >> n;  
      

for(int i = 0; i < n; i ++) cin >> 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];  
}  

cout << len;  

return 0;  

}

9.最长公共子序列

f[i] [j]表示所有a[1….i]和b[1….i]中公共子序列的集合的最大值

那么可以分为包含a[i]不包含b[j]包含a[i]包含b[j]等等四个

四个发现可以整合成三个

897. 最长公共子序列 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>  

using namespace std;  

const int N = 1010;  

int n, m;  
char a[N], b[N];  
int f[N][N];  

int main()  
{  
    cin >> n >> m >> 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);  
    }  

cout << f[n][m];  

return 0;  

}

10.最短编辑距离

f[i] [j]表示将a[i…i]变成b[1…j]的所有方式的最小值

根据题意分三步

902. 最短编辑距离 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>  

using namespace std;  

const int N = 1010;  

int n, m;  
char a[N], b[N];  
int f[N][N];  

int main()  
{  
    cin >> n >> a + 1;  
    cin >> m >> b + 1;  
      

for(int i = 0; i <= m; i ++) f[0][i] = i;  
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 ++)  
    {  
        f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);  
        if(a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);  
        else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);  
    }  

cout << f[n][m];  

return 0;  

}

区间DP

11.石子合并

f[i] [j]表示合并第i到j堆石子的代价最小值

282. 石子合并 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>  

using namespace std;  

const int N = 310;  

int n;  
int s[N];  
int f[N][N];  

int main()  
{  
       

cin >> n;  
for(int i  = 1; i <= n; i ++) cin >> s[i], s[i] += s[i - 1];  

for(int len = 2; len <= n; len ++)  
    for(int i = 1; i + len - 1 <= n; i ++)  
    {  
        int j = i + len - 1;  
        f[i][j] = 1e8;  
        for(int k = i; k < j; k ++)  
            f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);  
    }  

cout << f[1][n];  
   
return 0;  

}

计数类DP

12.整数划分

可以发现他就是一个完全背包问题

f[i] [j]表示1…i中选总数恰好是j

而f[i] [j]恰好可以优化成跟f[i] [j - 1]有关

再进行优化

900. 整数划分 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 #include <iostream>  

 using namespace std;  

 const int N = 1010, mod = 1e9 + 7;  

 int n;  
 int f[N];  

 int main()  
 {  
     cin >> n;  
       

 f[0] = 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];  
​       

 return 0;  

 }

数位统计DP

13.计数问题

分类讨论

338. 计数问题 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>  
 #include <vector>  

 using namespace std;  

 int get(vector<int> num, int l, int r) // num数组中r到l的数  
 {  
     int res = 0;  
     for(int i = l; i >= r; i --)  
         res = res * 10 + num[i];  
     return res;  
 }  

 int power10(int x) // 求10的x次方  
 {  
     int res = 1;  
     while(x --) res *= 10;  
     return res;  
 }  

 int count(int n, int x) // 表示前n个数中x在每一位出现的次数  
 {  
     if(!n) return 0;  
       

 vector<int> num;  
 while(n)  
 {  
     num.push_back(n % 10);  
     n /= 10;  
 }  

 n = num.size();  

 int res = 0;  
 for(int i = n - 1 - !x; i >= 0; i --)  
 {  
     if(i < n - 1)  
     {  
         res += get(num, n - 1, i + 1) * power10(i);  
         if(!x) res -= power10(i);  
     }  
       
      if(num[i] == x) res += get(num, i - 1, 0) + 1;  
      else if(num[i] > x) res += power10(i);  
 }  

 return res;  

 }  

 int main()  
 {  
     int a, b;  
     while(cin >> a >> b, a || b)  
     {  
         if(a > b) swap(a, b);  
           

​     for(int i = 0; i < 10; i ++)  
​         cout << count(b, i) - count (a - 1, i) << ' ';  
​     cout << endl;  
 }  

 return 0;  

 }

状态压缩DP

14.蒙德里安的梦想

15.最短Hamilton路径

f[i] [j]表示经过了i里面的点现在在j点（i表示一个数组用二进制表示1为经过0表示不经过）

91. 最短Hamilton路径 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>  
#include <cstring>  

using namespace std;  

const int N = 20, M = 1 << 20;  

int n;  
int f[M][N], weight[N][N];  

int main()  
{  
    // 读入数据  
    cin >> n;  
    for(int i = 0; i < n; i ++)  
        for(int j = 0; j < n; j ++)  
            cin >> weight[i][j];  
      

memset(f, 0x3f, sizeof f);  
f[1][0] = 0;  

for(int i = 0; i < 1 << n; i ++)  
    for(int j = 0; j < n; j ++)  
        if(i >> j & 1) // 判断j这个点是否经过  
            for(int k = 0; k < n; k ++) // DP  
                if(i - (1 << j) >> k & 1) // 这里（1 << j）没有也行主要是一个内在原理见上图  
                    f[i][j] = min(f[i][j], f[i - (1 << j)][k] + weight[k][j]);  

cout << f[(1 << n) - 1][n - 1] << endl;  
return 0;  

}

树形DP

16.没有上司的舞会

两个状态f[u] [0]表示从u为根的子树中选，不选u这个方案的值 f[u] [1]表示从u为根的子树中选，选择u这个点的方案

将两个取max则为答案

285. 没有上司的舞会 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>  
 #include <cstring>  

 using namespace std;  

 const int N = 6010;  

 int n;  
 int happy[N];  
 int h[N], e[N], ne[N], idx;  
 int f[N][2];  
 bool has_father[N];  

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

 void dfs(int u)  
 {  
     f[u][1] = happy[u];  
       

 for(int i = h[u]; i != -1; i = ne[i])  
 {  
     int j = e[i];  
     dfs(j);  
       
     f[u][0] += max(f[j][0], f[j][1]);  
     f[u][1] += f[j][0];  
 }  

 }  

 int main()  
 {  
     cin >> n;  
     for(int i = 1; i <= n; i ++) cin >> happy[i];  
       

 memset(h, -1, sizeof h);  
 for(int i = 0; i < n - 1; i ++)  
 {  
     int a, b;  
     cin >> a >> b;  
     has_father[a] = true;  
     add(b, a);  
 }  

 int root = 1;  
 while(has_father[root]) root ++;  

 dfs(root);  


​       
​     cout <<  max(f[root][0], f[root][1]);  
​       

 return 0;  

 }

记忆化搜索

17.滑雪

f[i] [j] 表示从当前位置滑经过路径的最大值

显然f[i] [j] 等于下一个路径的f值加一

901. 滑雪 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>  
#include <cstring>  

using namespace std;  

const int N = 310;  

int n, m;  
int h[N][N];  
int f[N][N];  

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};  

int dp(int x, int y)  
{  
    int &v = f[x][y];  
    if(v != -1) return v;  
      

v = 1;  
for(int i = 0; i < 4; i ++)  
{  
    int a = x + dx[i], b = y + dy[i];  
    if(a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])  
        v = max(v, dp(a, b) + 1);  
}  

return v;  

}  

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

for(int i = 1; i <= n; i ++)  
    for(int j = 1; j <= m; j ++)  
        cin >> h[i][j];  

memset(f, -1, sizeof f);  

int res = 0;  
for(int i = 1; i <= n; i ++)  
    for(int j = 1; j <= m; j ++)  
        res = max(res, dp(i, j));  
          
cout << res;  

return 0;  

}

第六章贪心

区间问题

1.区间选点

主要思路：

1.是将每个区间按右端点排序

2.枚举每个区间若当前区间已包含点则下一个 若没有则右端点为一个点

905. 区间选点 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>  
#include <algorithm>  

using namespace std;  

const int N = 100010;  

int n;  
struct Range  
{  
    int l, r;  
    bool operator< (const Range &W)const  
    {  
        return r < W.r;  
    }  
}range[N];  

int main()  
{  
      

cin >> n;  
for(int i = 0; i < n; i ++)  
{  
    int l, r;  
    cin >> l >> r;  
    range[i] = {l, r};  
}  

sort(range, range + n);  

int res = 0, ed = -2e9;  
for(int i = 0; i < n; i ++)  
    if(range[i].l > ed)  
    {  
        res ++;  
        ed = range[i].r;  
    }  
      
cout << res;  

return 0;  

}

2.区间分组

将区间按左端点排序

如果当前区间的左端点大于已有组区间的右端点则放在组里

否则开个新组

因此当前区间的左端点拿去跟组里面的最小右端点比就行了

所以就可以用小根堆

906. 区间分组 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>  
#include <algorithm>  
#include <queue>  

using namespace std;  

const int N = 100010;  

int n;  
struct Range  
{  
    int l, r;  
    bool operator< (const Range &W)const  
    {  
        return l < W.l;  
    }  
}range[N];  

int main()  
{  
    cin >> n;  
    for(int i = 0; i < n; i ++)  
    {  
        int l, r;  
        cin >> l >> r;  
        range[i] = {l, r};  
    }  
      

sort(range, range + n);  

priority_queue<int, vector<int>, greater<int>> heap;  
for(int i = 0; i < n; i ++)  
{  
    auto r = range[i];  
    if(heap.empty() || heap.top() >= r.l) heap.push(r. r);  
    else  
    {  
        int t = heap.top();  
        heap.pop();  
        heap.push(r.r);  
    }  
}  

cout << heap.size();  

return 0;  

}

3.区间覆盖

1.将左端点进行排序

2.找到覆盖线段左端点最长的区间

3.将区间右端点变成一个新的线段左端点重复上面第二步

907. 区间覆盖 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>  
#include <algorithm>  

using namespace std;  

const int N = 100010;  

int n;  
struct Range  
{  
    int l, r;  
    bool operator< (const Range &W)const  
    {  
        return l < W.l;  
    }  
}range[N];  

int main()  
{  
    int st, ed;  
    cin >> st >> ed;  

cin >> n;  
for(int i = 0; i < n; i ++)  
{  
    int l, r;  
    cin >> l >> r;  
    range[i] = {l, r};  
}  

sort(range, range + n);  

int res = 0;  
bool success = false;  
for(int i = 0; i < n; i ++)  
{  
    int j = i, r = -2e9;  
    while(j < n && range[j].l <= st)  
    {  
        r = max(r, range[j].r);  
        j ++;  
    }  
      
    if(r < st)  
    {  
        res = -1;  
        break;  
    }  
      
    res ++;  
    if(r >= ed)  
    {  
        success = true;  
        break;  
    }  
      
    st = r;  
    i = j - 1;  
}  

if(!success)res = -1;  
cout << res;  

return 0;  

}

Huffman树

4.合并果子

每次合并最小的果子

148. 合并果子 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>  
#include <queue>  

using namespace std;  

int main()  
{  
    int n;  
      



cin >> n;  
priority_queue<int, vector<int>, greater<int> > heap;  

for(int i = 0; i < n; i ++)  
{  
    int x;  
    cin >> x;  
    heap.push(x);  
}  

int res = 0;  
while(heap.size() > 1)  
{  
    int a = heap.top(); heap.pop();  
    int b = heap.top(); heap.pop();  
    res += a + b;  
    heap.push(a + b);  
}  
cout << res;  

}

排序不等式

5.打水问题

从小到大排序

让花费时间最少的先打

代码就不写了

913. 排队打水 - AcWing题库

绝对值不等式

6.货仓选址

就选中间就行了

104. 货仓选址 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 #include <iostream>  
 #include <algorithm>  

 using namespace std;  

 const int N = 100010;  

 int n;  
 int a[N];  

 int main()  
 {  
     cin >> n;  
     for(int i = 0; i < n; i ++) cin >> a[i];  

​       

 sort(a, a + n);  
 int res = 0;  
 for(int i = 0; i < n; i ++) res += abs(a[i] - a[n / 2]);  
 cout << res;  

 return 0;  

 }

推公式

7.耍杂技的牛

我们先随便排序

发现将第i个和第i + 1 个交换后 如果Wi + Si > Wi+1 + Si+1那么就会使这两个交换后风险值变小

由局部推导全局

则这个顺序是升序的

125. 耍杂技的牛 - AcWing题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <limits.h>  
#include <iostream>  
#include <algorithm>  

using namespace std;  

typedef pair<int, int> PII;  

const int N = 50010;  

int n;  
PII cows[N];  

int main()  
{  
    cin >> n;  
    for(int i = 0; i < n; i ++)  
    {  
        int w, s;  
        cin >> w >> s;  
        cows[i] = {w + s, w};  
    }  
      

sort(cows, cows + n);  

int sum = 0, res = INT_MIN;  
for(int i = 0; i < n; i ++)  
{  
    int w = cows[i].second, s = cows[i].first - w;  
    res = max(res, sum - s);  
    sum += w;  
}  

cout << res;  

return 0;  

}