「提高组笔记补充」
2023-11-20 09:57:06
发布于：浙江
177阅读
0回复
0点赞
因某些不可抗力原因(字数破两万了)
提高组笔记转移
提高班补充：
搜索强化的重点：
1、深度优先搜索
* 分析清楚算法时间复杂度
算法时间复杂度过高不宜使用深搜
估算“超时”的关键点是实际运行次数是否超过一亿/秒
* 确定深搜传递的参数
传递的参数是要寻找/计算的关键值
例如今天题目里的取每位数、二维矩阵的数对以及总收益
* 写好递归的边界条件
递归必须有结束的情况，若无陷入死循环
递归结束时记录相关的计算结果
* 合适的剪枝策略
去掉冗余计算部分，当前计算不会产生最优结果时，及时结束
2、广（宽）度优先搜索
* 初始化
需要初始的内容所有变量，例如vis数组、f数组等
未初始化可能会出问题
* 队列的STL模板
建议使用STL模板<queue>进行队列操作
常见的操作：
q.push() q.pop() q.empty() q.size() q.front()
int n = q.size();
* 确定初始时入队的元素
寻找起点或者一部分符合直接入队的元素
* 寻找转移的点
四个方向转移（定义常量）
八个方向转移（定义常量）
转移的点是否合法？判断范围内部
* 标记点被访问，不要重复入队
在点入队的时候标记被访问，避免重复访问
* 根据广搜的特性，在等步长的情况下，第一次寻找的点就是最优值
按层便利
差分:
一维差分可以利用 差分数组 将 一个区间内的所有元素 快速的加上或减去d
二维差分可以利用 差分矩阵 将 一个区块内的所有元素 快速的加上或减去d
for(int i=1;i<=m;i++){
int a1,b1,a2,b2;
cin>>a1>>b1>>a2>>b2;
for(int j=a1;j<=a2;j++){
c[j][b1]++;
c[j][b2+1]--;
}
|
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
c[i][j]+=c[i][j-1];
二分:
二分查找是用来在一个有序数组中查找某一元素的算法。
二分查找的平均时间复杂度均为O(log n).
若满足单调性，则满足使用二分法的条件。
把这里的枚举换成二分，就变成了「二分答案」。
int ans;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
ans=mid;
r=mid-1;
}else
l=mid+1;
}cout<<ans;
二叉堆:
结构:
从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。
堆性质：父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆，本文以大根堆为例。
由堆性质，树根存的是最大值。
插入操作
插入操作是指向二叉堆中插入一个元素，要保证插入后也是一棵完全二叉树。
最简单的方法就是，最下一层最右边的叶子之后插入。
如果最下一层已满，就新增一层。
插入之后可能会不满足堆性质？
向上调整：如果这个结点的权值大于它父亲的权值，就交换，重复此过程直到不满足或者到根。
可以证明，插入之后向上调整后，没有其他结点会不满足堆性质。
向上调整的时间复杂度是O(log n)的
删除操作
删除操作指删除堆中最大的元素，即删除根结点。
但是如果直接删除，则变成了两个堆，难以处理。
所以不妨考虑插入操作的逆过程，设法将根结点移到最后一个结点，然后直接删掉。
然而实际上不好做，我们通常采用的方法是，把根结点和最后一个结点直接交换。
是直接删掉（在最后一个结点处的）根结点，但是新的根结点可能不满足堆性质……
向下调整：在该结点的儿子中，找一个最大的，与该结点交换，重复此过程直到底层。
可以证明，删除并向下调整后，没有其他结点不满足堆性质。
时间复杂度 O(log n)。
增加某个点的权值：
很显然，直接修改后，向上调整一次即可，时间复杂度为 O(logn )
priority_queue priority_queue 的中文翻译为“优先队列”也就是常说的“堆” 它分为大根堆和小根堆。
priority_queue<int>que;//大根堆(大的在堆顶)
priority_queue<int,vector<int>,greater<int> >que;//小根堆(与大根堆相反)
↑这个空格一定要保留!!!
常见的操作：
que.push(x) //将x加入堆
que.pop() //丢掉堆顶
que.empty() //访问是否堆为空，空为0，非空为1
que.top() //访问堆顶
que.size() //优先队列的大小
并查集，在一些有N个元素的集合应用问题中，在开始时让每个元素构成一个单元素的集合，
然后按一定顺序将属于同一组的元素所在的集合合并，期间要反复查找一个元素在哪个集合中。
合并(Union):合并两个元素所属集合
查询(Find):查询某个元素所属集合
初始化
for(int i=1;i<=n;i++)
f[i]=i;
查询:
int Find(int x){//查询x的根节点
if(f[x]==x)return f[x];
else return f[x]=Find(f[x]);
}
合并：
void merge(int a,int b){
//先找到两个元素对应的根节点
int fa=Find(a);
int fb=Find(b);
if(fa==fb) return;
else f[fa]=fb;//令元素a的根指向b
树状数组：总能将一段前缀[1,n]拆成不多于logn段区间，使得这logn段区间的信息是已知的。
区间范围计算函数
int lowbit(int x){
return x & -x;
}
区间查询函数
int getsum(int x){
int ans=0;
while(x>0){
ans=ans+c[x];
}
return ans;
}
单点修改函数
void add(int x,int k){
while(x<=n){
c[x]=c[x]+k;
x=x+lowbit(x);
}
}
Dijkstra算法是一种单源最短路径算法，
时间复杂度上限为O(N^2)(朴素)
加上堆优化后时间复杂度为((N+M)log(2,N))
Dijkstra的流程如下：
1.初始化d[s]=0,其余节点的d值为无穷大。
2.找一个d值最小的白点 u,把节点u变成绿点。
3.便利u的所有出边(u,v,m),若d[v]>d[u]+w,
则令d[v]=d[u]+w.
4.重复2,3两步，知道所有点都变成绿点。
单调栈:
在栈的FILO规则基础上，要求从栈顶到栈底的元素具有单调性
准则
1.若当前入栈数比栈顶元素小，则入栈
2.若当前入栈数比栈顶元素大，则不断出栈，直到空栈或者比栈顶元素小
单调队列：
顾名思义，单调队列的重点分为「单调」
「单调」指的是元素的规律--递增（或递减）
求每连续的k个数中的最大值，
当一个数进入所要“寻找”最大值的范围中时，
若这个数比其前面(先进队)的数要大，
前面的数会比这个数先出队且不再可能是最大值。
即当满足以上条件时，可将前面的数“弹出”，再将该数真正push进队尾
相当于维护了一个递减的队列，符合单调队列的定义，减少了重复的比较次数，
由于维护出的队伍是查询范围内的且是递减的，队头必定是该查询区域内的 最大值。
由于每个数只进队或出队各一次，时间复杂度为O(N)
有帮助，赞一个