『C++普及组X02の提高组所有知识点』
2023-11-20 11:07:38
发布于：河南
7588阅读
0回复
0点赞
#最近更新:7月30日晚上19.05(别看了不会更了)
提高班笔记:「提高班笔记补充」
7月12日上午：
通俗地讲，算法是解决一系列问题的清晰步骤和方法，是准确解决问题方案的完整描述，
是对有一点规范的输入，在有限的时间内获得所要求的输出的这种能力的表达。
一个合格的算法，具备五个特性：
1.有穷性：一个合格的算法必须在执行完有穷（有限）步骤后再结束
且有时间限制
2.确定性：算法的步骤规定，含义和执行方法都是非常明确的；
3.可行性：所有操作都可实现；
4.输入：算法有多个或者零个输入；
5.输出：与输入一样，算法有多个或零个输出
没有输出（结果）的算法没有意义；
7月12日下午
STL：Standard Template Library 标准模板库，一般将这些模板称之为“容器”
常用容器包括string vector set map queue等。
vector：容器内元素访问：
1.通过下标访问，类似普通数组，下标从0开始
2.通过迭代器访问：vector<DataType>::iterator it;
常用成员函数(设 vector 容器名 val)：
函数名 功能 时间复杂度
val.push_back(data) 对val向后插入data数据 O(1)
val.pop_back() 删除val尾数据 O(1)
val.size() 当前val内元素个数 O(1)
val.clean() 清空当前val容器 O(N)
val.begin() 起始迭代器 -
val.end() 末尾迭代器 -
val.empty() 判空 -
set：容器内元素访问：
只能通过迭代器访问：set<DataType>::iterator it;
常用成员函数(设 set 容器名 val)：
函数名 功能 时间复杂度
val.insert(data) 对val插入data数据 O(1)
val.erase(it) 1.删除一个迭代器it所指的位置 O(1)
2.删除一个值为it的数据 O(log(n))
val.erase(first,last) 3.删除迭代器于[first,last)的数据 O(last-first)
val.size() 当前val内元素个数 O(1)
val.clean() 清空当前val容器 O(N)
val.begin() 起始迭代器 -
val.end() 末尾迭代器 -
val.find(data) 在val中查找data O(log(n))
map：容器内元素访问：
1.通过“下标”访问，即键值对访问，例如map['name']。
2.通过迭代器iterator访问元素：
map<DataType1,DataType2>::iterator it;
迭代器指代的是一个键值对对象:
用it->first访问键(DataType1)，it->second访问值(DataType2)。
常用成员函数(设 map 容器名 mp)：
函数名 功能 时间复杂度
mp.erase(it) 1.删除一个迭代器it所指的位置 O(1)
2.删除一个键为it的数据 O(log(n))
mp.erase(first,last) 3.删除迭代器于[first,last)的数据 O(last-first)
mp.size() 当前mp内,键的个数 O(1)
mp.clean() 清空当前mp容器 O(N)
mp.begin() 起始迭代器 -
mp.end() 末尾迭代器 -
mp.find(data) 在mp中查找键data O(log(n))
7月13日上午：
前缀和：
前缀和是指一段序列的前n项之和，可以理解为数学中，数列的前n项之和。
下标位置 0 1 2 3 4 5 6
数据数组a 0 4 3 2 5 9 6
数据数组b 0 4 7 9 14 23 29
b[1] = a[1] 令b[i] = a[1]+a[2]+…+a[i-1]+a[i]
b[2] = a[1] + a[2] 则b[i-1]=a[1]+a[2]+…+a[i-1]
b[3] = a[1] + a[2] + a[3]…… 有b[i] = b[i-1]+a[i]
区间和：
区间和往往是值一段序列连续某段连续区间之和。
下标位置 0 1 2 3 4 5 6
数据数组a 0 4 3 2 5 9 6
前缀和数组b 0 4 7 9 14 23 29
推广到[L,R]区间和：ans = a[L]+a[L+1]+a[L+2]+…a[R]
可知前缀和h[R]=a[1]+a[2]+…+a[L-1]+a[L]+a[L+1]+…+a[R]
整理算式得b[R]=b[L-1]+ans 因此 [L,R]区间和：ans=b[R]-b[L-1]
差分区间修改:
问题表述：对序列区间[L,R]中的每个数都加上c。
思路分析：
对d[L]增加c将使得a[L]及之后的数据都增加c。
对d[L]减少c将使得a[R+1]及之后的的数据减少c。
两种操作同时操作 则易知从a[R+1]开始之后的数据
因+c-c而无变化。
时刻牢记：差分是前缀和的逆运算。
7月13日下午
递归：
根据递归调用自身的位置不同，数量不同，可以将递归执行大致分为：
前置递归，后置递归，前后混合递归。
7月14日上午
贪心：
贪心算法，又称贪婪算法，是指在对问题求解时，模拟一个“贪心”的人做
出决策的过程。在每次做出决策的时候都采用当前看来最好的选择，不从整
体最优上去考虑，
他所做出的仅是在某种意义上的局部最优解，所以贪心算法不是对
于所有问题都能够得到最优解，关键是选择贪心的策略
贪心算法需要具备的特征：
1.贪心的选择：一个问题的整体最优解，能够通过一系列局部的最优解的选择
达到。每次的选择可以依赖以前做出的选择，但不依赖于后面要做出的选择，
这就是贪心
选择性质
2.最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题
具有最优子结构。问题的最优子结构性质是该问题可用贪心法求解的关键所在。
7月14日下午
二分搜索：
二分搜索，又名二分查找，折半查找。从算法大类来讲，属于分治的策略。
经典的二分搜索例子，猜数字。
顾名思义，每次将搜索规模缩小一半，因此搜索的时间复杂度为：O(logN)
二分模版：
int binSearch(int a[],int x,int left,int right){
while(left<=right){
int mid=(left+right)/2;
if(x==a[mid]){
return mid;
}else if(x>a[mid])
left=mid+1;
}else{
right=mid-1;
}
}return -1;
}
函数：所需头文件：#include<algorithm>
使用前提：递增序列，如递增数组
作用：
lower_bound (a, a + n, x)
在[a, a + n)区域内二分搜索第一个大于等于目标值 x 的地址。
upper_bound (a, a + n, x)
在[a, a + n)区域内二分搜索第一个大于目标值 x 的地址。
若该值存在，返回该值的地址，若该值不存在，返回a+n这个地址。
地址换算为数组中的下标
int v = lower_bound (a, a + n, x) - a
int v = upper_bound (a, a + n, x) - a
7月15日上午：
7月15日下午：
归并排序：
归并排序，又名二路归并排序。顾名思义，该排序算法涉及了二分的思想
即将原数列不断的平均拆分成两个子部分，再分别对子部分分别进行处理。
而“并”字,则意味着，将处理好地子部分再有序地合并起来。
归并排序步骤：
(1)令 mid=(R+L)/2 将[L,R]拆为[L,mid]于[mid+1,R]
(2)若L < mid,则将[L,mid]作为新[L,R]跳转(1),否则跳转(3)
(3)若mid + 1 < R,则将[mid+1,R]作为新[L,R]跳转(1),否则跳转(4)
(4)有序合并[L,mid]于[mid+1,R]
快速排序：
快速排序，简称快排，排序的核心逻辑是拆。但这个拆法于归并排序不同，
归并是单纯的拆开,快排是寻找一个基准值val,将数列拆分不小于val的部分
和不大于val的部分。然后对两个拆出来的部分重复这个拆分行为，直到
不可再拆为止
1.选择枢纽(一般是序列第一个数)
2.比枢纽小(大)，移到枢纽的前面
3.比枢纽大(小)，移到枢纽的后面
4.对新的两个子序列，再次重复上述步骤。
7月16日下午:
队列：
入队操作，是指向一个队列插入新元素。
（当head于tail相等时 队列为空）
出队操作，是指向一个队列删除队头元素
（根据队列的性质，从队头开始删数据，遵循先进先出原则）
7月18日下午：
图是一种由顶点和边组成的数据结构，其中顶点表示图中的对象
边表示这些对象的距离。
顶点：即节点，是图中的基本单元，表示一个实体或一个抽象概念。
边：顶点之间的连线表示顶点之间的距离。
无向图：由没有方向的边组成的图，也称为无向网络或无向图形。
无向边表示两个顶点之间的双边关系。
有向图：由有方向的边组成的图，也称为有向网络或有向图形。有向边从一个顶点指向
另一个顶点，表示一个方向的关系。在有向图中，顶点也称为起点或终点。
带权图：边上带有权值的图。
权值：可以形象地理解为通过这条边的花费的时间、距离、金额等等；
自环：一条边的两端连接的是同一个端点。 重边：顶点之间存在多条边连接。
简单图：一种无向图或有向图，其中不存在自环和重边。
多重图：一种有向图或无向图，其中存在自环或重边。
无向完全图：图中任意两个顶点之间都存在边。
拥有n个顶点的完全无向图含有n*(n-1)/2条边。
有向完全图：图中任意两个顶点之间都存在方向相反的两条边。
拥有n个顶点的完全有向图含有n*(n-1)条边。
稀疏图：图中的边相对较少，边之间的连接相对稀疏。
稠密图：图中的边相对较多，边之间的连接相对密集。
度：指于一个顶点相连的边的数量。在无向图中，一个顶点的度就是它的边的连接数。
在有向图中，一个顶点的入度是指指向该顶点的边的数量，
出度是指从该顶点出发的边的数量
路径：指从一个顶点到另一个顶点的连续边构成的序列。
路径长度：指一路经中，经过的边的数量。
简单路径：指从一个顶点到另一个顶点的连续边构成的路径，不存在重复边。
（即同一条边最多经过一次）
有向图的路径可被称为有向路径。
环路：指一路径的起点和终点是同一个顶点，且路径上的每个顶点可重复
（即同一条边可经过多次）。
简单环路：指一路径除了起点和终点是同一个顶点外，其路径上的其他顶点均不重复
（即同一条边不可经过多次）。若某图不包含任何简单环路，可称该图为无环图。
连通性：若某图中任意两个顶点之间都存在路径，则称该图是连通图。
若某图不是联通图，则该图可分为多个联通分量。
对于有向图，有强连通图和弱连通图之分
1.强连通图：指任意两个顶点u和v之间存在一条从u到v的有向路径，同时存在一条
从v到u的有向路径。
2.弱连通图：指将有向图中的所有边都看作无向边后得到的连通图。
7月19号上午：
Floyd-Warshall算法，简称Floyd算法，求解多源最短路径
多源指起点可以是任意顶点，例如在下图中求i号顶点到j号顶点的最短距离。
核心思想是用以中间点进行松弛，时间复杂度为O(n³)，且可以解决负边权情况。
1-----3
| \/ |
| /\ |
2-----4
参考代码 memset(mp,0x3f,sizeof(d));//初始化为一个较大的值
for(int i=1;i<=n;i++){
d[i][i]=0;
for(int j=1;j<=n;j++){
cin>>d[i][j];
}
}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][j]在计算过程中表示的是仅经过前k个点的情况下任意i,j的最短距离
其中k是阶段，一定要放到外层循环。
时间复杂度O(n³)
7月20日上午：
01背包：
当j<w[i],背包容量放不下第i件物品: dp[i][j]=dp[i-1][j]
当j≥w[i],背包容量能放下第i件物品，考虑放与不放两种情况，且要最大价值，取max:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v]+w)
01背包优化：dp[i]=max(dp[i],dp[i-v]+w) tip:v==空间,w==价值
完全背包公式==01背包 但01背包为for(int j=m;j>=v;i--) 而完全背包为for(int j=v;j<=m;j++);
多重背包:
for(k=1;k<=n;k++){
cin>>v>>w>>x;
for(int i=1;i<=x;i++){
for(j=v*i;j<=m;j++){
f[j]=max(f[j],f[j-v*i]+i*w);
}
}
}
或将多重中大于一个的拆分开来，化简为01背包问题，但对应的复杂度会增加。
提高班补充：
草、acgo为啥会有限制字数这个东西啊
提高班笔记记不下了
提高班点这个→→→「提高班笔记补充」
有帮助，赞一个