第4部分 数据结构与算法提高班Word格式.docx
- 文档编号:7282875
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:78
- 大小:435.43KB
第4部分 数据结构与算法提高班Word格式.docx
《第4部分 数据结构与算法提高班Word格式.docx》由会员分享,可在线阅读,更多相关《第4部分 数据结构与算法提高班Word格式.docx(78页珍藏版)》请在冰点文库上搜索。
只查询:
DataTypeget_top(){returnstack_data[top];
}
4.1.1.4栈的应用
4.1.2队列
4.1.2.1队列的定义
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端进行删除(查询)操作,而在表的后端进行插入操作。
进行插入操作的端称为队尾,进行删除(查询)操作的端称为队头。
4.1.2.2队列的实现
4.1.2.2.1队列的存储
DataTypequeue_data[QUEUE_SIZE];
//DataType通常为int
intfront=0,tail=0;
//队首和队尾指针。
队首指针指向第一个元素,队尾指针指向最后一个元素后面的位置。
4.1.2.2.2判断队列是否为空
boolisQueueEmpty()
returnfront==tail;
4.1.2.2.3判断队列是否为满
boolisQueueFull()
returntail>
=QUEUE_SIZE;
4.1.2.2.4入队(插入)
if(isQueueFull())returnfalse;
queue_data[tail++]=x;
4.1.2.2.5出队(查询,删除)
查询(无空队列检查):
DataTypeget_front(){returnqueue_data[front];
删除:
boolpop()
if(isQueueEmpty())returnfalse;
front++;
4.1.2.2.6循环队列
我们注意到,进行pop(弹出)操作后,队列数组前端有许多空闲下来的存储空间,如果能将其利用则队列存储效率更高。
我们可以用『循环队列』的方式来节省空间。
当我们的队首或者队尾指针变成QUEUE_SIZE的时候,将其对QUEUE_SIZE取模变为
0。
这样就实现了让队列『首尾相接』,循环起来了。
这样判断队满的条件不再是tail>
=QUEUE_SIZE,而是tail==front。
不过这样和判断队空的条件冲突了。
我们可以通过牺牲一个存储单元的方式,将判断队满的条件改成
tail==front-1。
只需要将原先程序里面front++和tail++的部分改成front=(front+1)%QUEUE_SIZE
和tail=(tail+1)%QUEUE_SIZE即可。
4.1.2.2.7双端队列
即可以在两端进行删除/查询/插入操作的队列,在普通队列的基础上稍加升级即可。
4.1.2.3队列的应用4.1.3单调队列,单调栈
4.1.3.1何为单调队列和单调栈
单调队列/单调栈,顾名思义,即保证内部元素单调(从大到下或者从小到大)的队列或者栈。
我们只要在插入新元素的时候,将队尾/栈顶所有在插入新元素后不满足单调的元素依次弹出,再插入新元素即可。
4.1.3.2应用
通常被用来进行动态规划的优化。
4.2堆、并查集、加权并查集(高天宇)
4.2.1并查集
4.2.1.1并查集简介
并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。
常常在使用中以森林来表示。
举个简单的例子,若A和B互相认识,B和C也互相认识,则A与C互相认识。
现在给出若干对这样的关系,询问某两个人是否互相认识。
诸如此类的问题可以用并查集解决
4.2.1.2并查集操作
4.2.1.2.1存储
并查集首先要记录一组分离的动态集合,每个集合都有一个代表元素。
我们开一个数组father[i]记录第i个元素所在集合的代表元素是谁。
本质上father[i]是i在并查集这个森林中的父亲。
4.2.1.2.2初始化
for(inti=1;
i<
=n;
i++)father[i]=i;
4.2.1.2.3查找代表元素
intfind(intx)
if(father[x]==x)returnx;
elsereturnfind(father[x]);
4.2.1.2.4合并
voidmerge(intx,inty)
intf1=find(x);
intf2=find(y);
father[f1]=f2;
4.2.1.2.5路径压缩
if(father[x]==x)returnfather[x];
father[x]=find(father[x]);
returnfather[x];
4.2.1.2.6加权并查集
并查集节点维护一些附加信息。
在进行路径压缩的同时对信息进行更新。
4.2.1.2.7在最小生成树中的应用
Kruskal算法
4.2.1.3并查集习题
4.2.2堆
4.2.2.1简介
堆(heap)是一棵特殊的二叉树,它总满足以下两点性质:
1.堆中某个节点的值总是不大于或不小于其父节点的值
2.堆总是一棵完全二叉树。
4.2.2.2堆的存储
只需要一个数组就可以搞定。
令heap[1]存储根节点。
对于每个点i来说,heap[i*2]存储左儿子,heap[i*2+1]存储右儿子
4.2.2.3堆的操作
4.2.2.3.1筛选
假设有一个堆heap[1..n],我现在要删除第一个元素(最大的元素),如何维护堆的性质不变?
将根节点删除,把最后一个点移动到根节点上来。
如果当前点比某一个儿子小,就与儿子交换(如果比两个儿子都小,与最大的儿子交换),以此类推,直到没有儿子或者比儿子大。
voidheap_adjust(intx)
while(x*2<
=tot)
intj=x*2;
if(x*2+1<
=tot&
&
heap[x*2+1]>
heap[x*2])j++;
if(heap[j]>
heap[i])
swap(heap[i],heap[j]);
i=j;
else
break;
4.2.2.3.2初始化
现在我们有一个数组a[1..n],如何把它初始化成一个堆?
从编号大的点,到编号小的点,依次进行“筛选”操作即可。
for(inti=tot/2;
i>
=1;
i--)heap_adjust(i);
4.2.2.3.3加入新的点
如果现在堆中共有tot个节点,我们把新的节点放在位置tot+1上。
运用和“筛选”类似的方法,我们不停地比较当前点和父亲,如果当前点比父亲大,则
交换,直到交换到根或者不再比父亲大为止。
4.2.2.3.4堆排序
–将整个序列调整为堆
–提取出根节点,输出,并删除。
将最后一个点放到根节点的位置,进行“调整”。
“调整”后,仍然满足堆的性质。
–重复第二步,直到所有的元素都被删除。
4.2.2.4应用例题
4.3倍增算法(高天宇)
4.3.1倍增思想简介倍增是根据已经得到的信息,将考虑的范围扩大一倍,从而加速操作的一种思想使用了倍增思想的算法:
⏹归并排序,快速幂
⏹基于ST表的RMQ算法和树上倍增找LCA
⏹FFT、后缀数组等高级算法
4.3.2倍增的两种情况
4.3.2.1在变化规则相同的情况下加速状态转移
4.3.2.1.1归并排序
归并排序是一个递归过程merge_sort(l,r),表示要将位置l到位置r之间的数字排列成有序。
令mid=(l+r)/2,过程大致如下:
●merge_sort(l,mid)
●merge_sort(mid+1,r)
●merge(l,mid,mid+1,r)
其中merge(l,mid,mid+1,r)负责将l到mid的有序区间和mid+1到r的有序区间合并成一个新的有序区间。
执行完merge函数后,从l到r将变为有序。
merge函数执行前必须保证l到mid有序,mid+1到r有序总体复杂度O(nlogn)
4.3.2.1.2快速幂
intfast_pow(inta,intp)
intans=1;
for(;
p;
p>
>
=1,a=a*a)if(p&
1)
ans=ans*a;
returnans;
4.3.2.1.3矩阵乘法快速幂
与快速幂相同,只不过将整数乘法变为矩阵乘法。
4.3.2.1.3例题
4.3.2.2加速区间操作
4.3.2.2.1RMQ算法
RMQ(RangeMinimum/MaximumQuery),即区间最值查询,是指这样一个问题:
对于长度为n的数列A,回答若干询问RMQ(A,i,j),返回数列A中下标在i,j之间的最小/大值。
令A[i]存储我们要求最值的数列,F[i][j]表示从第i个位置开始,往后的2^𝑗
个数字中,最大的数字是什么。
我们对j从小到大枚举。
每次处理𝐹
[𝑖
][𝑗
]的时候,𝐹
][0~𝑗
−1]都已经处理好了
𝐹
]=max(𝐹
−1],𝐹
+2^(𝑗
−1)][𝑗
−1])
查询:
要查询的区间是(i,j),令𝑘
=⌊log(𝑖
+𝑗
−1)⌋,那么要查询的结果是:
Ans=max(𝐹
][𝑘
],𝐹
[𝑗
−2^𝑘
+1][𝑘
])
代码:
voidinit_rmq(intn)
–1]);
i++)f[i][0]=a[i];
for(intj=1;
j<
=20;
j++)
i++)if(i+(1<
<
j)–1<
=n)
f[i][j]=max(f[i][j–1],f[i+(1<
(j–1))][j
intquery_rmq(inti,intj)
intk=log(i+j–1)/log
(2);
returnmax(f[i][k],f[j–(1<
k)+1][k]);
4.3.2.2.2倍增查找LCA
令father[i][j]表示编号为i的点,往上蹦2^𝑗
次的父亲是谁。
预处理与RMQ的预处理类似。
先从小到大枚举j,然后令
𝑓
𝑎
𝑡
ℎ𝑒
𝑟
]=𝑓
[𝑓
−1]][𝑗
−1]
查询时我们分两步走:
⏹将u和v移动到同样的深度
⏹u和v同时向上移动,直到重合。
第一个重合的点即为LCA
4.3.2.2.3例题
4.4基础数论(高天宇)
4.4.1约数与质数
4.4.2.1欧几里得算法
intgcd(inta,intb)
if(!
b)returna;
returngcd(b,a%b);
4.4.2.2扩展欧几里得算法
voidexgcd(inta,intb,int&
d,int&
x,int&
y)
b){d=a;
x=1;
y=0;
else{exgcd(b,a%b,d,y,x);
y-=(a/b)*x;
4.4.2.2唯一分解定理
即分解质因数。
4.4.2.3Eratosthenes筛法
复杂度O(nlogn)
intm=sqrt(n+0.5);
memset(vis,0,sizeof(vis));
for(inti=2;
=m;
i++)
vis[i])
for(intj=i*i;
j+=i)vis[j]=true;
4.4.2.4欧拉筛法
复杂度O(n)
#include<
cstdio>
cstring>
constintMAXN=1e7;
intprime[MAXN/3];
boolflag[MAXN+10]={0};
inlinevoidget_prime()
intcntprime=0;
for(inti=2;
=MAXN;
flag[i])prime[++cntprime]=i;
=cntprime&
prime[j]*i<
flag[i*prime[j]]=true;
if(i%prime[j]==0)
4.4.2同余问题
4.4.2.1符号与基本性质
表示a与b关于模n余数相同(同余)
(a+b)%n=((a%n)+(b%n))%n
(a–b)%n=((a%n)–(b%n)+n)%nab%n=(a%n)(b%n)%n
4.4.2.2逆元
方程称为a关于模n的逆元。
当gcd(a,n)=1时方程有唯一解,否则误解。
逆元可以理解为在模n剩余系当中的a的倒数。
4.4.2.3模线性方程组
输入正整数a,b,n,解方程,其中a,b,n
可理解成ax-b为n的整数倍。
得到方程ax-b=ny,化简得ax-ny=b。
用扩展欧几里得算法即可。
注意,得出x以后,任意满足的数y都可以被当做该方程的解。
4.4.3前两节应用举例
4.4.4计数问题
4.4.4.1排列组合,加法乘法原理
做一件事情有n个办法,每个办法p[i]个方案,则一共有p[1]+p[2]+…+p[n]种方案。
做一件事情有n个步骤,每个步骤有p[i]个方案,则一共有p[1]*p[2]*…*p[n]种方案。
排列:
A(n,m)表示n个东西里面选出m进行排列。
组合:
C(n,m)表示n个东西里面选出m个进行组合。
C(n,m)=C(n–1,m)+C(n–1,m–1)
C(n,m)=n!
/(m!
(n–m)!
)
4.4.4.2二项式定理,杨辉三角
二项式定理:
对于二项式,展开式第r+1项为杨辉三角:
4.4.4.3容斥原理
4.4.5概率初步
4.4.5.1期望
期望指试验中每次可能结果的概率乘以其结果的总和。
它反映随机变量平均取值的大小,记作E(X)。
若C为常数,则E(CX)=CE(X)E(X+Y)=E(X)+E(Y)
当X,Y互相独立(不影响)时,E(XY)=E(X)E(Y)
4.4.5.2条件概率
P(A|B)=P(AB)/P(B)
4.4.6后两节应用举例
4.5前缀和与差分,STL选讲(高天宇)
4.5.1前缀和与差分
4.5.1.1前缀和、差分简介
用a表示原数组,用sum表示其前缀和
下标
1
2
3
4
5
6
7
a
sum
10
15
17
23
差分:
a[i]~a[j]的和,即为sum[j]-sum[i–1]
4.5.1.2例题4.5.2STL选讲
【知识点】
掌握基本的c++stl模板库的应用其中常用函数包括:
1.排序函数sort,stable_sort
2.最大最小值函数min,max,min_element,max_element
3.二分查找函数lower_bound,upper_bound
4.交换函数swap
5.去重函数unique
6.生成排列函数next_permutation,prev_permutation
常用容器与配接器包括
1.栈stack
2.队列queue
3.双端队列deque
4.优先队列priority_queue
5.向量vector
6.对组pair
7.集合set,multiset
8.映射map,multimap
9.字符串string
【知识讲解】
1.STL是什么:
在OI竞赛中,可以使用的语言有C++、C、Pascal,其中C++最大的优势是,它本身提供了一个模板库——StandardTemplateLibrary(标准模板库),简称STL。
STL包含一系列算法和容器等,合理地使用STL,可以在提高编写代码的效率。
NOI系列比赛自2011年起允许C++选手使用STL,所以我们应该利用好STL,发挥C++语言的优势。
2.STL分类
STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器
(adapters)、算法(algorithms)、仿函数(functors)六个部分
3.STL中的算法主要包含在<
algorithm>
头文件中
4.迭代器是用于访问STL容器中元素的一种数据类型
5.STL中提供一些与排序相关的算法,最常用的是不稳定排序std:
:
sort。
它由类似快速排序的算法实现,时间复杂度为(期望)O(nlogn)
6.使用std:
unique函数来去除有序区间内重复的元素,其调用格式与std:
sort类似,返回去重后的区间结束位置
7.使用std:
max和std:
min取得两个数中较大、较小值。
8.使用std:
max_element和std:
min_element取得一个区间内的最大、最小值。
函数返回对应值的迭代器。
9.STL中常用的用于二分查找的函数有三个:
std:
lower_bound、std:
upper_bound、std:
binary_search,一般std:
lower_bound最为常用
lower_bound用于在一个升序区间中查找某个元素,并返回第一个不小于(大于等于)该元素的元素的迭代器,如果找不到,则返回指向区间结束位置的迭代器。
std:
upper_bound用于在一个升序区间中查找某个元素,并返回第一个大于该元素的元素的迭代器,如果找不到,则返回指向区间结束位置的迭代器。
binary_search用于确定某个元素有没有在一个升序区间中出现过,返回true或false。
三个函数的时间复杂度均为O(logn)。
10.使用std:
swap交换两个变量的值。
11.使用std:
next_permutation和std:
prev_permutation函数生成当前排列的(按照字典序)下一个(上一个)排列。
12.栈std:
stack:
使用<
stack>
头文件中的std:
stack<
T>
定义一个储存T类型数据的栈。
13.队列std:
queue
使用std:
queue<
定义一个储存T类型数据的队列。
14.优先队列(堆)std:
priority_queue
queue>
priority_queue<
定义一个储存T类型数据的优先队列
(堆)。
15.数组std:
vector
vector>
vector<
定义一个储存T类型数据的动态数组。
vector支持在某个位置插入、删除元素,注意,在非尾部插入、删除元素的时间复杂度为O(n)
16.对组std:
pair
utility>
pair<
T1,T2>
定义一个由一个T1类型和一个T2类型的值组成的值对。
make_pair(a,b)构造一个由a、b组成的值对,可以省去模板参数。
类型在比较大小时,T1为第一关键字,T2为第二关键字。
17.集合std:
set
se
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第4部分 数据结构与算法提高班 部分 数据结构 算法 提高班