10月1号D1数据结构讲解(PPT1)
10月1号D1数据结构讲解(PPT1)
注意:这个东西是留给自己看的，不是特地给别人看的，所以很多我知道的东西就没加注释，请谅解。
单调栈
单调栈在联赛中一般处理在第一个严格比他大的数，或者比他小的数。
在联赛难度下, 单调栈几乎全部用来简单地求每个数向左/右比它小/大的第一个数的位置。
单调栈还是一个应用性非常广泛的数据结构，一定要熟练掌握。
单调栈可以让我们在线性时间求出答案。
//那就套一下单调栈的板子，顺顺手。
//模拟实现单调递增栈
/*
现在有一组数10，3，7，4，12。从左到右依次入栈，则如果栈为空或入栈元素值小于栈顶元素值，则入栈；否则，如果入栈则会破坏栈的单调性，则需要把比入栈元素小的元素全部出栈。单调递减的栈反之。
*/
int sta[MAXN];
int top=0;
int a[10]={0,10,3,7,4,12};
int n=5;
for(int i=1;i<=n;i++){
if(top==0||sta[top]>=a[i])//栈为空或者栈中元素大于我们现在查询的元素
sta[++top]=a[i];//入栈
else{
while(sta[top]<a[i]){//如果比我们的值要小
top--;//出栈
}
sta[++top]=a[i];
}
}
例1：柱形统计图中最大面积
这是一道典型的单调栈的题目，我们枚举所有的柱子，往左往右做单调栈，分别找到第一个比它小的数的位置。这是一个单调栈比较简单的应用。
code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,p;
int s[100010],a[100010],w[100010];
int ans;
signed main(){
while(cin>>n&&n){
ans=0;p=0;
for(int i=1;i<=n;i++)cin>>a[i];
a[n+1]=0;
for(int i=1;i<=n+1;i++){
if(a[i]>s[p])s[++p]=a[i],w[p]=1;//单调递增的单调栈
else{
int wid=0;
while(s[p]>a[i]){
wid+=w[p];
ans=max(ans,wid*s[p]);//查找最大值
p--;
}//访问完毕
s[++p]=a[i],w[p]=wid+1;//栈顶的宽度+1，更新新的矩形（如有删除就整合）
}
}
cout<<ans<<endl;
}
return 0;
}
例二：
给定一个数组\(A[1...n]\)，求\(\sum_{i<j}\min(A[i],A[i+1],..,A[j])\)，要求线性。
这也是一道单调栈的经典题，让我们开心地AK它。
code:
#include <bits/stdc++.h>
using namespace std;
int n;
int a[190900];
int sta[190900];
int top;
int ans;
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
if(!top||sta[top]>a[i]){
sta[++top]=a[i];
}
ans+=sta[top];
}
cout<<ans<<endl;
return 0;
}
如此简短的代码我也不做解释了，太基础，如果不会，请重学单调栈。
队列
因为我的队列不是很好，所以我就多弄点队列。
先进先出的数据结构，从队尾插，从队头删。
操作:入队列，出队列，求队首元素，判断是否为空。
BFS的板子:
//没编译，可以自行编译
bool bfs(int x,int y){
queue<pair<int,int>> q;
q.push(make_pair(x,y));
vis[x][y]=1;
while(q.size()){
int xx=q.front().first;
int yy=q.front().second;
q.pop();
for(int i=1;i<=4;i++){
int nx=xx+dx[i];//四大方向
int ny=yy+dy[i];//四大方向
if(nx<1||nx>n||ny<1||ny>m||vis[nx][ny])//防止出边界
continue;
vis[nx][ny]=1;//表示已经遍历过
if(nx==n)return 1;
else q.push(make_pair(nx,ny));
}
}
return 0;
}
例一：
给定一棵树，按层数遍历整棵树
一道BFS的经典题，上code。
code:
#include <bits/stdc++.h>
const int maxn=1000;
using namespace std;
int n,m;
inline int read(){
int x=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1,ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*w;
}
struct edge{
int to,nxt;
}e[maxn];
int head[maxn],cnt;
void addg(int u,int v){
//cout<<cnt<<endl;
cnt++;
e[cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int a[10000];
bool vis[10000];
queue<int> q;
void bfs(){
vis[1]=1;
a[1]=1;
q.push(1);
while(!q.empty()){
int u=q.front();
//cout<<u<<endl;
q.pop();
//cout<<head[u]<<endl;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!vis[v]){q.push(v);a[v]=a[u]+1;vis[v]=1;}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
addg(x,y);
addg(y,x);
}
bfs();
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
例二：
给定一个无向图，求一个点s到每个点的距离
一道典型的BFS，上代码吧。
code:
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1,ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*w;
}
struct edge{
int to,nxt;
}e[10000];
int head[10000],cnt;
bool vis[10000];
int dis[10000];
void addg(int u,int v){
cnt++;
e[cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void bfs(int s){
queue<int> q;
q.push(s);
vis[s]=1;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(!vis[v]){q.push(v);dis[v]=dis[u]+1;vis[v]=1;}
}
}
}
int n,m;
int main(){
n=read(),m=read();
int s=read();
for(int i=1;i<=m;i++){
int x=read(),y=read();
addg(x,y);
addg(y,x);
}
bfs(s);
for(int i=1;i<=n;i++)
cout<<dis[i]<<" ";
return 0;
}
单调队列：
-
维持队列内元素的单调性，如果新入队的元素破坏了单调性我们就要弹出队尾元素直到满足单调性。
-
一旦队首元素变得不合法。就需要弹掉队首元素。
-
一般用于以下问题：
源源不断地来一堆元素，元素之间有一个好差的全序
就像如果一个人比你小还比你巨，你就可以退役了...
当一个元素A比元素B差并且还要来得早的话A就会被B完爆
(单调队列也是NOIP的一大考点，一定要非常熟练！！！)
算法步骤：
一. 把第一个元素进队，队头队尾指针指向第一个元素
二. 对于其他的\(N-1\)个未入队的元素执行如下操作：
1.如果队头元素超过指定的区间范围，队头元素出队
2.当队尾指向的元素的值小于当前要入队的元素值，队尾元素出队
3.当前要入队的新元素入队
4.当前最优值为队头元素的值
接下来几道例题，理解一下
例一：
有一个长为 n 的序列 a，以及一个大小为 k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
经典题就不会再给讲解了，直接上代码。
code：
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; const int N=1e6+500; int n,k,a[N],q[N],head=1,tail;//head要+1 q[]存储的是编号 int main() { scanf("%d %d",&n,&k); //求解最小值 for(int i=1;i<=n;i++) { scanf("%d",&a[i]); while(head<=tail&&q[head]<=i-k) head++;//队头显然是最早进入的,如果队头的下标大于i-k,该数便不在区间内了,从队头删除 while(head<=tail&&a[q[tail]]>=a[i]) tail--;//当前数破坏了单调性,从队尾删除,直至队中数小于当前数 q[++tail]=i;//当前元素进队 if(i>=k) printf("%d ",a[q[head]]);//输出每个区间最小值 } printf("\n"); //求解最大值 head=1,tail=0; for(int i=1;i<=n;i++) { while(head<=tail&&q[head]<=i-k) head++;//队头显然是最早进入的,如果队头的下标大于i-k,该数便不在区间内了,从队头删除 while(head<=tail&&a[q[tail]]<=a[i]) tail--;//当前数破坏了单调性,从队尾删除,直至队中数大于当前数 q[++tail]=i;//当前元素进队 if(i>=k) printf("%d ",a[q[head]]);//输出每个区间最大值 } return 0; }例二：
• 在某两座城市之间有n个烽火台,每个烽火台发出信号都有一定 代价
• 每连续m个烽火台中至少要有一个发出信号
• 求最少花费多少代价
不知道为什么我的脑子里一直想着烽火戏诸侯，这就是找区间最小值的一道题，但他是一个\(DP\)难度系数就上来了。
根据我们所知很容易得到这样一个式子:
本题是dp加单调队列优化。
f[i]表示当第i个烽火台发出信号，前i个烽火台最少付出的代价。
f[i]=min{f[k]}(i-m<=k<=i-1)+w[i]
单调队列维护一单调递增区间，每次队首取出最小值。
然后我们的code就上场了
code:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int f[N];
int que[N];
int main()
{
scanf("%d%d",&n,&m);
int head=1,tail=0;
for(int i=1;i<=n;i++)
{
int w;
scanf("%d",&w);
while(head<=tail&&f[que[tail]]>=f[i-1])
tail--;
que[++tail]=i-1;
while(que[head]<i-m)
head++;
f[i]=w+f[que[head]];
}
int ans=inf;
for(int i=n;i>n-m;i--)
ans=min(ans,f[i]);
printf("%d\n",ans);
return 0;
}
例三：书架
自己点题目就能打开....
一眼就能出来是一道DP，和上一题的转移方程很像。
\[f[i]=\min(f[i],f[j]+\max(h[k]))
\]
具体的看这篇博客，讲的很详细。
书架题解