当前位置：首页 > news >正文

高一讲课

news 2026/5/12 21:29:03

栈

又叫后进先出表

给出一个栈常用功能的实现

struct sta{int tp,a[(int)1e7];void push(int x){a[++t]=x;}int top(int x){if(t==0)return -1;return a[t];}int size(){return t;}void pop(){if(t==0)return ;else t--;}
}s;

push(x) 向栈内压入一个元素

top() 查询栈顶

pop() 弹出栈顶

size() 栈中元素个数

单调栈

问题引入

P5788

维护一个栈,使得栈中元素单调

考虑如何维护一个栈内元素递增的栈:

1.若栈为空或栈顶大于当前元素,直接压入当前元素

2.弹出栈顶

我们发现使某个位置弹出栈的元素编号就是这个位置的答案

于是得到以下代码

#include<bits/stdc++.h>
using namespace std;
int a[1000000*4];
int f[1000000*4];
stack<int> s;
void expush(int x){while(!s.empty()&&a[x]>a[s.top()]){f[s.top()]=x;s.pop();}s.push(x);
}
int main(){cin.tie(0);ios::sync_with_stdio(false);int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){expush(i);}for(int i=1;i<=n;i++)cout<<f[i]<<" ";
}

例题

P10334

考虑无解,由于一个时刻只能做一杯饮料,所以当饮料数大于当前时刻,直接输出无解.

倒序计算出相邻两个顾客顾客之间的间隔,尽量在最晚的时间做好.

P10798

取反操作对绝对值限制无意义,只可能通过改变端点值改变威胁区间个数

P9461

P10174

P7167

""水会流入半径大于这个圆盘的圆盘中"",容易想到单调栈.

把圆盘向其后第一个半径大于他的连边,构建出一棵树(根节点为水池),倍增维护.

队列

先进先出表

队列常用功能

struct ccc{int a[1000000],t=0,h=1;void push(int x){a[++t]=x;}void pop(){h++;}int front(){return a[h];}int size(){return t-h+1;}bool empty(){return (t-h+1)==0;}
}q;

单调队列

问题引入

......

考虑维护一个由队首到队尾单调的队列,队首即为该区间的答案

以区间最大值为例:

如果队首元素不在当前区间内,则弹出队首
若队尾小于当前元素,弹出队尾
当前元素入队

代码如下

 h=1,t=0;for(int i=1;i<=n;i++){while(h<=t&&q2[h]+m<=i) h++;while(h<=t&&a[i]>a[q2[t]]) t--;q2[++t]=i;if(i>=m) printf("%d ",a[q2[h]]);}
}

例题

P2827

经典老题

暴力: 堆模拟,注意其余蚯蚓的长度会增加.

正解: 排序,发现切之前,前半段,后半段分别单调,开三个队列维护

P6033

同上

P4944

deque的应用,应该都做了.

堆

小根堆

priority_queue<int,vector<int>,greater<int> >q;

大根堆

priority_queue<int>q;

DAG

~~谁把这玩意放这儿的?~~

性质

能拓扑排序的图一定是有向无环图,有向无环图一定能拓扑排序.
从一个点出发,一定不会回到这个点

拓扑排序

拓扑排序要解决的问题是如何给一个有向无环图的所有节点排序。

因此我们可以说在一个 DAG（有向无环图）中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 $u$ 到 $v$ 的有向边 $(u,v)$ , 都可以有 $u$ 在 $v$ 的前面。

还有给定一个 DAG，如果从 $i$ 到 $j$ 有边，则认为 $j$ 依赖于 $i$ 。如果 $i$ 到 $j$ 有路径（ $i$ 可达 $j$ ），则称 $j$ 间接依赖于 $i$ 。

拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。

构造拓扑序列

从图中选择一个入度为零的点。
输出该顶点，从图中删除此顶点及其所有的出边。

重复上面两步，直到所有顶点都输出，拓扑排序完成，或者图中不存在入度为零的点，此时说明图是有环图，拓扑排序无法完成。

Kahn 算法

算法流程

初始状态下，集合 $S$ 装着所有入度为 $0$ 的点， $L$ 是一个空列表。

每次从 $S$ 中取出一个点 $u$ （可以随便取）放入 $L$ , 然后将 $u$ 的所有边 $( u , v_1) , (u, v_2), (u, v_3)$ 删除。对于边 $(u, v)$ ，若将该边删除后点 $v$ 的入度变为 $0$ ，则将 $v$ 放入 $S$ 中。

不断重复以上过程，直到集合 $S$ 为空。检查图中是否存在任何边，如果有，那么这个图一定有环路，否则返回 $L$ ， $L$ 中顶点的顺序就是构造拓扑序列的结果。

int n, m;
vector<int> G[MAXN];
int in[MAXN];  // 存储每个结点的入度bool toposort() {vector<int> L;queue<int> S;for (int i = 1; i <= n; i++)if (in[i] == 0) S.push(i);while (!S.empty()) {int u = S.front();S.pop();L.push_back(u);for (auto v : G[u]) {if (--in[v] == 0) {S.push(v);}}}if (L.size() == n) {for (auto i : L) cout << i << ' ';return true;}return false;
}

关于例题,你们会在晴空幻梦的tarjan例题里见到的,这里先放两道简单的.

最小生成树

定义

在图的边集中选择 $n - 1$ 条，将所有顶点连通。

Kruskal

为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入生成树，如果某次加边产生了环，就扔掉这条边，直到加入了 $n-1$ 条边，即形成了一棵树.

查询两点是否连通和连接两点可以使用并查集维护。

#include<bits/stdc++.h>
using namespace std;
int fa[10000000];
struct edge{int u,v,w;
}e[10000000];
bool xx(edge a,edge b){return a.w<b.w;
}
int get(int x){if(fa[x]==x)return x;return fa[x]=get(fa[x]);
}
int main(){int n,m;cin>>n>>m;for(int i=1;i<=m;i++)cin>>e[i].u>>e[i].v>>e[i].w;for(int i=1;i<=n;i++)fa[i]=i;sort(e+1,e+m+1,xx);int cnt=0,ans=0;for(int i=1;i<=m;i++){int fx=get(e[i].u),fy=get(e[i].v);if(fx==fy)continue;fa[fx]=fy;cnt++;ans+=e[i].w;if(cnt==n-1){cout<<ans;return 0;}}puts("orz");return 0;
}

prim

基本思想是从一个结点开始，不断加点.

具体来说，每次要选择距离最小的一个结点，以及用新的边更新其他结点的距离。

其实跟 Dijkstra 算法一样，每次找到距离最小的一个点，可以暴力找也可以用堆维护。

#include<bits/stdc++.h>
#define mr make_pair
using namespace std;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >  q;
struct ccc{int to,nxt,w;
}e[(int)1e6];
int head[(int)1e6];
int cnt,tot,ans;
void add(int u,int v,int w){e[++cnt].to=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;
}
int n,m;
int dis[(int)1e6],vis[(int)1e6];
void prim(){for(int i=1;i<=n;i++)dis[i]=1e9,vis[i]=0;dis[1]=0;q.push(mr(0,1));while(!q.empty()){if(tot>=n)return ;int nw=q.top().second,d=q.top().first;q.pop();if(vis[nw])continue;tot++;ans+=d;vis[nw]=1;for(int i=head[nw];i;i=e[i].nxt){int v=e[i].to,w=e[i].w;if(dis[v]>w){dis[v]=w;q.push(mr(w,v));}}}
}