笔记-X03与主线课
2024-08-22 12:00:25
发布于：上海
差分数组：
对有 个数据的数组 ，其差分数组 使得 的前缀和可以获得 ,即:
由此移项，可得：
则易得若将 增加 ，则在数组 中，数据 都会增加 。
因此，若要将序列 中 之间的数都增加 ，则我们需要有且，时间复杂度为
例题：
区间修改(集训营入口)
区间修改(非集训营入口)
表:
解决在线问题的工具。
步骤：
设表示区间 区间的最值，区间长度为，填表的时间复杂度为 ，递推式为：
分治法：
指定对于一个规模为 的问题，将其分解为 个规模较小的子问题。这些子问题互相独立(即子问题之间不包含公共的子子问题)且与原问题形式相同，递归解这些子问题，合并其解可得原问题的解。分治的核心代码主要集中在分解和合并阶段，治理极端的核心点事递归参数和递归边界。
快速排序：
问题：对一个长度为 的序列 ，将其升序排列。
方法：从序列中任取一个元素 ，将所有小于等于 的元素放到 的左边，所有大于等于 的元素放到 的右边，此时 的位置必定正确，下面是使用双指针的方式解决快速排升序问题的代码：
#include<bits/stdc++.h>
using namespace std;
int n = 0;
int numList[100005];
void Quick_sort(int arr[], int low, int high){
if (high <= low) return;
int i = low;
int j = high;//定义左右指针
int key = arr[low];//设置基准数key
while (i<j){
//从左向右找比key大的值
while(arr[i] <= key){
i++;
if(i == high) break;
}
//从右向左找比key小的值
while(arr[j] >= key){
j--;
if(j == low) break;
}
if(i >= j) break;
//交换i,j对应的值
swap(arr[i],arr[j]);
}
arr[low] = arr[j];
arr[j] = key;
Quick_sort(arr,low,j - 1);
Quick_sort(arr,j + 1,high);
}
int main(){
cin>>n;
for(int i = 0;i < n;i++){
cin >> numList[i];
}Quick_sort(numList,0,n-1);
for(int i = 0;i < n;i++){
cout << numList[i] << " ";
}
}
快速排序的一次划分算法从两头交替搜索，直到指针 和指针 重合，因此其时间复杂度是 。而整个快速排序算法的时间复杂度与划分的趟数有关。理想的情况是每次划分所选择的中间数恰好将当前序列几乎等分，经过 趟划分，便可得到长度为 的子数组。这样，整个算法的时间复杂度为 。而最坏的情况是每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子数组中一个为空，另一子表的长度为原数组的长度 。这样，长度为 的数据表的快速排序需要经过 趟划分后的时间复杂度为 。
归并排序：
步骤如下：
将给定的包含 个元素的局部数组"分割"成两个局部数组，每个数组各包含 个元素。(划分)
对两个局部数组分别执行 排序。(处理)
通过 将两个已排序完毕的局部数组"整合"成一个数组。(合并)
代码：
#include<bits/stdc++.h>
using namespace std;
int n,a[100010],b[100010];
void Merge_sort(int l,int r){
if(l>=r) return ;
int s = (l+r)/2;
Merge_sort(l,s);
Mek-1rge_sort(s+1,r);
int x=l,y=s+1,lc=l;
while(x<=s&&y<=r){
b[lc++]=a[x]<a[y]?a[x++]:a[y++];
}
while(x<=s)b[lc++]=a[x++];
while(y<=r)b[lc++]=a[y++];
for(int i=l;i<=r;i++){
a[i] = b[i];
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}Merge_sort(0,n-1);
for(int i=0;i<n;i++){
cout<<a[i]<<" ";
}
}
树与图：
边的数量： 对于有 个节点的树，有且只有 条边。
路径： 在一棵树中，一个结点和根结点的通路称为路径。在第 层的结点的路径长度为 (如果称根结点处在第 层)。一个结点的路径长度乘以该结点的权值，为结点的带权路径长度，其中权是给一个结点赋予的有意义的值。树的带权路径长度规定为所有叶子结点的带权路径长度之和。
哈夫曼树： 使得的带权路径长度最短的树称为哈夫曼树，又称为最优二叉树。哈夫曼树通常为二叉树。
哈夫曼树的构造：
对于给定带有各自权值的 个结点，构造哈夫曼树：
在 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树的一个结点的左右孩子。
删除使用过的两个权值，将新的权值加入到权值集合中。
重复 和 ，直到无法再选出两个权值，此时这个二叉树就是哈夫曼树。
通俗点：最底下一层俩叶子，往上每层加一个叶子，叶子的权值下面小上面大。
详见百度百科-哈夫曼树
哈夫曼编码： 按照字符出现的概率分配哈夫曼树的叶子结点的权值，以实现平均码长最短的编码。每个字符的哈夫曼编码表示为：从根结点出发到目标结点，每走一个右子树加一个 ,否则加一个 。
度： 节点的子节点数，特别的，称度为 的节点为叶子结点；树的度是其所有节点的度的最大值。
树的表示与储存： tree[i].child 存储着节点i的孩子的位置信息。tree[i].child.push_back(idx) 表示给节点i增加一个编号为 idx 的孩子.
完全二叉树: 若某二叉树深 层，且除第 层外其他所有的层的结点总数达到最大值，同时第 层节点数小于等于 并靠左侧连续，则称其为完全二叉树。即在完全二叉树中，编号为 的结点与满二叉树中编号为 的结点的位置相同。有 个结点的完全二叉树的深度为 。
二叉搜索树： 也称为二叉查找树、二分搜索树、有序二叉树或排序二叉树，其满足以下几个条件：
若任意结点的左子树不空，则其左子树上所有结点的值均不大于它的根结点的值。
若任意结点的右子树不空，则其右子树上所有结点的值均不小于它的根结点的值。
对二叉搜索树进行删除、查找、插入的操作的平均时间复杂度为 ，最坏为 。二叉搜索树的中序排列是一个有序序列。
网：顶点表示活动，有向边表示活动之间的优先制约关系， 表示活动 必须先于活动 进行，称这种有向图为顶点表示活动的网为 网。
拓扑排序-入度： 在有向图中，一个顶点 的入度指与该条边向关联的入边的条数。
拓扑排序-出度： 在有向图中，一个顶点 的入度指与该条边向关联的出边的条数。
拓扑排序： 拓扑排序解决的问题是给一个有向无环图的所有结点排序：每次去掉一个入度为 的顶点并更新所有与其有关系的顶点的入度。一个有向无环图的拓扑排序可能不唯一。
运算符重载
即在结构体内写sort函数的比较规则，下面是一个优先按照x降序排列的例子。
struct Node{
int x, y;
friend bool operator<(Node a, Node b)>{
if(a.x == b.x)
return a.y > b.y;
return a.x > b.x;
}
}a[15];
sort(a + 1, a + n + 1);
//等价写法
struct Node{
int x, y;
}a[15];
bool operator<(Node a, Node b)>{
if(a.x == b.x)
return a.y > b.y;
return a.x > b.x;
}
sort(a + 1, a + n + 1);
有帮助，赞一个