第4部分 数据结构与算法提高班.docx
《第4部分 数据结构与算法提高班.docx》由会员分享，可在线阅读，更多相关《第4部分 数据结构与算法提高班.docx（78页珍藏版）》请在冰点文库上搜索。
第4部分数据结构与算法提高班
第4部分数据结构与算法提高班2
4.1栈、队列、单调队列、单调栈（高天宇）2
4.2堆、并查集、加权并查集（高天宇）5
4.3倍增算法（高天宇）8
4.4基础数论（高天宇）10
4.5前缀和与差分，STL选讲（高天宇）13
4.6NOIP历年题目分析与讲解（高天宇）17
4.7NOIP模拟赛（李佳蔚）25
4.8比赛策略和骗分技巧（李佳蔚）25
4.9搜索及优化（张晨）32
4.10最短路、最小生成树（张晨）37
4.11线段树与树状数组（谢兴宇）44
4.12背包dp、简单树型dp（马龙）47
4.13动态规划及常见优化（马龙）56
第4部分数据结构与算法提高班
4.1栈、队列、单调队列、单调栈（高天宇）
4.1.1栈
4.1.1.1栈的定义
栈（stack）是一种运算受限的线性表。
其限制是仅允许在表的一端进行插入和删除运算。
这一端被称为栈顶，相对地，把另一端称为栈底。
4.1.1.2计算机中的栈
计算机中调用函数时，函数信息便保存在堆栈当中。
4.1.1.3栈的实现
4.1.1.3.1栈的存储
DataTypestack_data[STACK_SIZE];//通常DataType都是intinttop=0;//栈顶指针，初始时栈为空
4.1.1.3.2判断栈是否为空
boolisStackEmpty（）
{
returntop==0;
}
4.1.1.3.3判断栈是否为满
boolisStackFull（）
{
returntop==STACK_SIZE–1;
}
4.1.1.3.4进栈操作
boolpush（DataTypex）
{
if（isStackFull（））returnfalse;stack_data[++top]=x;
returntrue;
}
4.1.1.3.5出栈操作
查询+删除：
boolpop（DataType&x）
{
if（isStackEmpty（））returnfalse;x=stack_data[top--];
returntrue;
}
只查询：
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入队（插入）
boolpush（DataTypex）
{
if（isQueueFull（））returnfalse;queue_data[tail++]=x;
}
4.1.2.2.5出队（查询，删除）
查询（无空队列检查）：
DataTypeget_front（）{returnqueue_data[front];}
删除：
boolpop（）
{
if（isQueueEmpty（））returnfalse;front++;
returntrue;
}
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路径压缩
intfind（intx）
{
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]）;
}
for（inti=1;i<=n;i++）f[i][0]=a[i];
for（intj=1;j<=20;j++）
for（inti=1;i<=n;i++）if（i+（1<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<}
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）
{
if（!
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;i<=m;i++）
if（!
vis[i]）
for（intj=i*i;j<=n;j+=i）vis[j]=true;
4.4.2.4欧拉筛法
复杂度O（n）
#include
#includeconstintMAXN=1e7;intprime[MAXN/3];
boolflag[MAXN+10]={0};inlinevoidget_prime（）
{
intcntprime=0;
for（inti=2;i<=MAXN;i++）
{
if（!
flag[i]）prime[++cntprime]=i;
for（intj=1;j<=cntprime&&prime[j]*i<=MAXN;j++）
{
flag[i*prime[j]]=true;if（i%prime[j]==0）
break;
}
}
}
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
2
3
1
4
5
2
6
sum
2
5
6
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中的算法主要包含在头文件中
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最为常用
std:
:
lower_bound用于在一个升序区间中查找某个元素，并返回第一个不小于（大于等于）该元素的元素的迭代器，如果找不到，则返回指向区间结束位置的迭代器。
std:
:
upper_bound用于在一个升序区间中查找某个元素，并返回第一个大于该元素的元素的迭代器，如果找不到，则返回指向区间结束位置的迭代器。
std:
:
binary_search用于确定某个元素有没有在一个升序区间中出现过，返回true或false。
三个函数的时间复杂度均为O（logn）。
10.使用std:
:
swap交换两个变量的值。
11.使用std:
:
next_permutation和std:
:
prev_permutation函数生成当前排列的（按照字典序）下一个（上一个）排列。
12.栈std:
:
stack：
使用头文件中的std:
:
stack定义一个储存T类型数据的栈。
13.队列std:
:
queue
使用std:
:
queue定义一个储存T类型数据的队列。
14.优先队列（堆）std:
:
priority_queue
使用头文件中的std:
:
priority_queue定义一个储存T类型数据的优先队列
（堆）。
15.数组std:
:
vector
使用头文件中的std:
:
vector定义一个储存T类型数据的动态数组。
std:
:
vector支持在某个位置插入、删除元素，注意，在非尾部插入、删除元素的时间复杂度为O（n）
16.对组std:
:
pair
使用头文件中的std:
:
pair定义一个由一个T1类型和一个T2类型的值组成的值对。
使用std:
:
make_pair（a,b）构造一个由a、b组成的值对，可以省去模板参数。
std:
:
pair类型在比较大小时，T1为第一关键字，T2为第二关键字。
17.集合std:
:
set
使用
升级会员 