堆疊
演算法思路
堆疊（\(stack\)）又名堆疊，它是一種運算受限的線性表，限定僅在表尾進行插入和洗掉操作的線性表，這一端被稱為堆疊頂，相對地，把另一端稱為堆疊底，向一個堆疊插入新元素又稱作進堆疊、入堆疊或壓堆疊，它是把新元素放到堆疊頂元素的上面，使之成為新的堆疊頂元素；從一個堆疊洗掉元素又稱作出堆疊或退堆疊，它是把堆疊頂元素洗掉掉，使其相鄰的元素成為新的堆疊頂元素， ----摘自 百度百科
由上述資料可知，堆疊是一個“先進后出”的資料結構，是只能在堆疊頂插入和洗掉的資料結構，如圖，支持進堆疊（\(push\)）和出堆疊（\(pop\)）兩種操作，由于只能從一端進堆疊，一端出堆疊，所以任一元素，如上圖中的\(s_2\)，必須得在比它后進堆疊的\(s_3\sim s_n\)（\(s_n\)即\(s_{top}\)）都出堆疊以后才能出堆疊，換句話說，先進來的元素必須等后進來的元素都出堆疊后才能出堆疊，故堆疊被稱為“先進后出（\(FILO\)）表”，
代碼片段
進堆疊
進堆疊很簡單，只需要將堆疊頂上移一格，然后在新的一格中放入元素即可，
void push(int x){
s[++top]=x;
}
出堆疊
出堆疊也很簡單，只需要將堆疊頂下移一格即可，且不需要替換，因為如果有元素進堆疊需占用此格時會將它替換，
void pop(){
top--;
}
例題
P1739 運算式括號匹配
大意
給定一個以\(@\)結尾的運算式，判斷其括號（只有“(”和“)”）是否匹配，
“(()())”，“((()))”匹配，但是“())”，“)()(”不匹配，
思路
如果只判斷左右括號的數量的話顯然是不行的，因為有很多資料顯然過不去，如“)()(”，“())(()”等，
所以，這時候，我們就要使用堆疊了，逐個讀入運算式，若為“(”則入堆疊（顯然此時堆疊應該為\(char\)型別），若為“)”則判斷，若堆疊頂為慷訓為“)”，即不為“(”，說明此時這個右半圓括號沒有匹配到左半圓括號，說明不匹配，另外，若最后堆疊頂不為\(0\)，說明還有剩下的括號沒被匹配，也是不合法的，
代碼
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char a[260],s[260];
int top=0;
int main(){
cin>>a;
for(int i=0;i<strlen(a);i++){
if(a[i]=='('){
s[++top]=a[i];
}else if(a[i]==')'){
if(a[i]==')'&&s[top]=='('){
top--;
}else{
cout<<"NO";
return 0;
}
}
}
if(top==0){
cout<<"YES";
}else{
cout<<"NO";
}
return 0;
}
P1449 后綴運算式求值
科普
逆波蘭式（\(Reverse Polish notation\)，\(RPN\)，或逆波蘭記法），也叫后綴運算式（將運算子寫在運算元之后），
一個運算式\(E\)的后綴形式可以如下定義：
（1）如果\(E\)是一個變數或常量，則E的后綴式是\(E\)本身，
（2）如果\(E\)是\(E1 op E2\)形式的運算式，這里\(op\)是任何二元運算子，則E的后綴式為\(E1'E2' op\)，這里\(E1'\)和\(E2'\)分別為\(E1\)和\(E2\)的后綴式，
（3)如果\(E\)是\((E1)\)形式的運算式，則\(E1\)的后綴式就是\(E\)的后綴式，
如：我們平時寫\(a+b\)，這是中綴運算式，寫成后綴運算式就是：\(ab+\)，
\((a+b)*c-(a+b)/e\)的后綴運算式為：
\((a+b)*c-(a+b)/e\)
→\(((a+b)*c)((a+b)/e)-\)
→\(((a+b)c*)((a+b)e/)-\)
→\((ab+c*)(ab+e/)-\)
→\(ab+c*ab+e/-\)
這里用樹解釋上述樣例：
首先我們構建上述運算式的樹，使得樹的中序遍歷為運算式（因為我們寫的是中綴運算式，若想將前綴運算式，即波蘭式 變為樹，則需構建樹讓其前序遍歷為運算式即可），那么，這棵樹的后序遍歷就是逆波蘭式，
大意
給出后綴運算式，輸出其值，
思路
一個個讀入后綴運算式，遇到數字進堆疊，遇到符號計算堆疊頂和堆疊頂后一位的元素，最后輸出堆疊頂即可，
代碼
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int s[260],top=1;
char x;
int main(){
while(x!='@'){
x=getchar();
if(x=='.'){
top++;
}else{
if(x>='0'&&x<='9'){
s[top]=s[top]*10+(x-'0');
}
if(x=='+'){
top--;
s[top-1]+=s[top];
s[top]=0;
}else if(x=='-'){
top--;
s[top-1]-=s[top];
s[top]=0;
}else if(x=='*'){
top--;
s[top-1]*=s[top];
s[top]=0;
}else if(x=='/'){
top--;
s[top-1]/=s[top];
s[top]=0;
}else if(x=='@'){
break;
}
}
}
cout<<s[--top];
return 0;
}
佇列
演算法思路
堆疊是一端進和出的資料結構，對應地，佇列是一端進、另一端出的資料結構，
佇列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行洗掉操作，而在表的后端（rear）進行插入操作，和堆疊一樣，佇列是一種操作受限制的線性表，進行插入操作的端稱為隊尾，進行洗掉操作的端稱為隊頭， ——摘自 百度百科
與堆疊類似，不多贅述，
單調堆疊
演算法思路
顧名思義，單調堆疊是一種堆疊內元素具有單調性的堆疊，也就是說，我們將數列內的元素入堆疊，且要讓堆疊內元素單調遞增或單調遞減，維護這樣一個堆疊也很簡單（以下假設維護單調遞增的單調堆疊），我們將堆疊內的元素\(s_i\)表示為數列\(a\)中的元素的下標，也就是說，當你在看到堆疊內有一個元素\(x\)時，它表示的不是數字\(x\)，而是表示\(a\)陣列中的元素\(a_x\)，這一點需要特別注意，入堆疊時，如果堆疊頂元素表示的值大于加入的值（即\(a_{s_{top}}>a_x\)，\(x\)表示加入的元素，顯然為\(a\)陣列中的元素下標），那么將\(top--\)，即把堆疊頂踢出去，因為加進來的\(x\)，即代表的\(a_x\)，已經小于堆疊頂了，而我們要維護單調遞增的堆疊，所以若\(x\)直接加入會破壞單調性，故要讓堆疊頂出堆疊，等到所有的要踢出堆疊頂\(top\)都被踢出后（即現在的堆疊頂\(top\)符合\(a_{s_{top}}<a_x\)），就可以將\(x\)入堆疊了，
那么，單調堆疊有什么作用呢？顯然，你可以維護一個單調遞增的堆疊，通過按順序一個個入堆疊序列中的元素，可以求出長度為\(n\)的序列\(a\)中的前\(k\)個元素的最小值（\(0<k\le n\)），因為堆疊是單調遞增的，所以按順序加入前\(k\)個元素后，堆疊頂一定是前\(k\)個數中的最小值，但是，你顯然可以不用單調堆疊來解決這一個非常基礎的問題，單調堆疊的主要作用之一就是求出序列中每個數右（或左）邊第一個比它大（或者小）的數（詳情請見例題1），
例題
P5788 【模板】單調堆疊 & P2947 [USACO09MAR]Look Up S
大意
求出序列中每個數右邊第一個比它大的數，
思路
維護一個單調遞減的堆疊，那么，對于每一個元素，讓它被踢出去的那個元素一定是第一個比它大的元素，（建議自己畫圖好好分析一下），
代碼
#include<iostream>
#include<cstdio>
#define maxn 100005
using namespace std;
int n,a[maxn];
int s[maxn],top=0;
int ans[maxn];
void push(int x){
while(a[s[top]]<a[x]&&top>0){
ans[s[top]]=x;
top--;
}
s[++top]=x;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
s[++top]=1;
for(int i=2;i<=n;i++){
push(i);
}
for(int i=1;i<=n;i++){
printf("%d ",ans[i]);
}
return 0;
}
P1901 發射站
大意
有\(n\)個發射站，每一個發射站有一個高度\(h_i\)和能量值\(v_i\)，對于每個發射站\(i\)，它左邊和右邊第一個比它高的發射站都可以接收到它發出的信號（即累計值加上\(v_i\)），求每個信號塔累計的能量值總和的最大值，
思路
同上兩題，只不過要加兩次，
代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1000005
using namespace std;
int n,a[maxn],v[maxn];
int s[maxn],top=0;
int ans[maxn];
void push(int x){
while(a[s[top]]<a[x]&&top>0){
ans[x]+=v[s[top]];
top--;
}
s[++top]=x;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i],&v[i]);
}
s[++top]=1;
for(int i=2;i<=n;i++){
push(i);
}
memset(s,0,sizeof(s));
top=0;
s[++top]=n;
for(int i=n-1;i>=1;i--){
push(i);
}
int mmax=-1;
for(int i=1;i<=n;i++){
mmax=max(mmax,ans[i]);
}
printf("%d ",mmax);
return 0;
}
P2422 良好的感覺
大意
有一長為\(n\)的序列\(a\)，定義某區間\([l,r]\)的值\(comfort_{l,r} = \min\limits_{i=l}^{r}{a_i} \times \sum\limits_{i=l}^{r}{a_i}\)，求\(max(comfort_{i,j})(0 < i\le j\le n)\)，
思路
可以想象，列舉每個區間需要耗費大量的時間，這很可能會使我們\(TLE\)，我們不妨列舉\(min(i,j)\)，顯然我們只需要列舉\(n\)次，因為我們可以從\(1\)到\(n\)列舉\(i\)，計算以\(a_i\)為最小值的區間中的最大\(comfort_{l,r}\)，因為\(a_i \ge 1\)，所以我們只要讓區間越大越好，所以我們需要列舉的區間即為從\(a_i\)開始，左右兩邊各延伸到離它最近的比它小的兩個位置（不包括這兩個比它小的值）（因為這樣就可以保證區間內沒有小于\(a_i\)的數，即\(a_i\)為區間內最小值，且區間最大），計算所有的\(a_i\)計算的區間的和乘\(a_i\)（即以\(a_i\)為最小值的最大\(comfort\)值）的最大值即為所求最大值，
代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 100005
using namespace std;
int n,a[maxn];
long long pre[maxn];
int le[maxn],ri[maxn];
int s[maxn],top=0;
void pushr(int x){
while(a[s[top]]>a[x]&&top>=0){
ri[s[top]]=x;
top--;
}
s[++top]=x;
}
void pushl(int x){
while(a[s[top]]>a[x]&&top>=0){
le[s[top]]=x;
top--;
}
s[++top]=x;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
pre[i]=pre[i-1]+a[i];
}
s[++top]=1;
for(int i=2;i<=n;i++){
pushr(i);
}
memset(s,0,sizeof(s));
top=0;
s[++top]=n;
for(int i=n-1;i>=1;i--){
pushl(i);
}
for(int i=1;i<=n;i++){
ri[i]=ri[i]==0?n+1:ri[i];
}
long long ans=-1;
for(int i=1;i<=n;i++){
ans=max(ans,(long long)(a[i]*(pre[ri[i]-1]-pre[le[i]])));
}
printf("%lld",ans);
return 0;
}
單調佇列
演算法思路
我們剛才講到，單調堆疊可以算出一組資料中前\(k\)個資料中的最值（雖然不用單調堆疊更簡單易懂），那么，如何計算一組資料中任意連續\(k\)個資料的最值呢（\(0<k\le n\)）？這時，我們就要用到單調佇列了（注：用線段樹也可以），
單調佇列相當于單調堆疊，但是它在隊頭也可以進行洗掉操作（即\(head++\)），以上述題目（即例題\(1\)）為例，我們只要控制這個單調佇列的隊頭始終滿足在所求范圍內即可，更詳細的思路見例題\(1\)，
例題
P1886 滑動視窗 /【模板】單調佇列
大意
有一串長\(n\)的序列，有一個長\(m\)的視窗從\(1\)到\(n-m+1\)滑動（\(0<m<=n\)），求每滑動一次視窗的最值，
思路
模板題，
維護佇列\(q\)（當然能用\(STL\)），（這里講最大值的做法，最小值同理）每次加入一個元素，從隊尾把小于此元素的從隊尾出隊（因為當前的元素已經比它大了，且視窗向右滑動，所以它必定不可能再一次成為最大值），從隊首將不在范圍內的元素從隊首出隊，這時隊首即為最大值，
代碼中，先將前\(k-1\)個元素入隊，然后回圈\(i\)（\(k\le i\le n\)），列舉隊尾，用\(push\)函式從隊尾插入，同時從隊頭刪去\(i-k+1\)之前的元素，即已經不在滑動視窗內的元素，輸出隊頭，
代碼
#include<iostream>
#include<cstdio>
#define maxn 1000005
using namespace std;
int n,k;
int a[maxn];
int q1[maxn],q2[maxn],h1=1,t1=0,h2=1,t2=0;//q1維護最大值,q2維護最小值
int ans1[maxn],ans2[maxn];
void push1(int x,int l){
while(t1>=h1&&a[x]>a[q1[t1]]){
t1--;
}
q1[++t1]=x;
while(t1>=h1&&q1[h1]<l){
h1++;
}
}
void push2(int x,int l){
while(t2>=h2&&a[x]<a[q2[t2]]){
t2--;
}
q2[++t2]=x;
while(t2>=h2&&q2[h2]<l){
h2++;
}
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
q1[++t1]=1;
q2[++t2]=1;
for(int i=2;i<=k;i++){
push1(i,-1);
push2(i,-1);
}
ans1[1]=q1[h1];
ans2[1]=q2[h2];
for(int i=k+1;i<=n;i++){
push1(i,i-k+1);
push2(i,i-k+1);
ans1[i-k+1]=q1[h1];
ans2[i-k+1]=q2[h2];
}
for(int i=1;i<=n-k+1;i++){
printf("%d ",a[ans2[i]]);
}
printf("\n");
for(int i=1;i<=n-k+1;i++){
printf("%d ",a[ans1[i]]);
}
return 0;
}
注
雙倍經驗（只需求最大值）：P2032 掃描
P2629 好訊息，壞訊息
大意
給定一個環，問從任意元素開始累加，有多少種情況使得累加時總和\(tot\)恒大于等于\(0\)，
思路
斷環成鏈，維護單調佇列和前綴和\(pre_i\)，若某一長度為\(n\)的序列\(i\sim i+n-1\)的最小值減\(pre_{i-1}\)大于零的話即可行，
代碼
#include<iostream>
#include<cstdio>
#define maxn 1000005
using namespace std;
int n,k;
int a[maxn*2],pre[maxn*2];
int q[maxn],h=1,t=0;
int ans[maxn];
void push(int x,int l){
while(t>=h&&pre[x]<pre[q[t]]){
t--;
}
q[++t]=x;
while(t>=h&&q[h]<l){
h++;
}
}
int main(){
scanf("%d",&n);
k=n;
n*=2;
for(int i=1;i<=k;i++){
scanf("%d",&a[i]);
a[i+k]=a[i];
}
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+a[i];
}
q[++t]=1;
for(int i=2;i<=k;i++){
push(i,-1);
}
ans[1]=q[h];
for(int i=k+1;i<n;i++){
push(i,i-k+1);
ans[i-k+1]=q[h];
}
int tot=0;
for(int i=1;i<=n-k;i++){
if(pre[ans[i]]-pre[i-1]>=0){
tot++;
}
}
printf("%d",tot);
return 0;
}
單調佇列優化DP
例題
P1725 琪露諾
大意
有一串長度為\(n+1\)的序列\(a\)，從\(0\)出發，在某個節點\(i\)能走到\(i+l\sim i+r\)的任意位置，\(tot\)累加當前位置的\(a_i\)，求離開時的最大\(tot\)值（\(i+r>n\)代表從\(i\)節點能離開），
思路
顯然此題暴力代碼復雜度為\(O(N^2)\)，\(f_i=\max\limits_{j=max(0,i-r)}^{i-l}{f_j}(l<=i<=n)\)，那么，我們只要開一個單調佇列求前文的\(max(f_j)\)即可，
代碼
（細節很多）
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1000005
#define INF 0x3f
using namespace std;
int n,l,r;
int a[maxn];
int q[maxn],h=1,t=0,maxx[maxn];
int f[maxn];
void push(int x,int l){
while(f[x]>f[q[t]]&&h<=t){
t--;
}
while(q[h]<l&&h<=t){
h++;
}
q[++t]=x;
}
void clear(int l){
while(q[h]<l&&h<=t){
h++;
}
}
int main(){
scanf("%d%d%d",&n,&l,&r);
memset(f,0x80,sizeof(f));
memset(q,-1,sizeof(q));
for(int i=0;i<=n;i++){
scanf("%d",&a[i]);
}
f[0]=0;
push(0,-1);
for(int i=l;i<=n;i++){
if(i-l>=l){
push(i-l,max(0,i-r));
}else{
clear(max(0,i-r));
}
if(q[h]==-1){
f[i]=f[maxn-1]+a[i];
}else{
f[i]=f[q[h]]+a[i];
}
// for(int j=i-l;j>=max(0,i-r);j--){
// f[i]=max(f[i],f[j]+a[i]);
// }
}
int ans=-INF;
for(int i=n;i>=n-r+1;i--){
ans=max(ans,f[i]);
}
printf("%d",ans);
return 0;
}
P2627 Mowing the Lawn G
大意
有一個長度為\(n\)的序列，選出若干個元素，使得選出的元素沒有連續超過\(k\)個的（\(0<k<=n\)），求選出元素的和的最大值，
思路
選出的數的和的最大值可以轉換成刪去的數的和的最小值，
代碼
#include<iostream>
#include<cstdio>
#define maxn 100005
using namespace std;
long long n,k,a[maxn],f[maxn];
long long q[maxn],h=0,t=0;
long long tot=0;
void push(long long x,long long l){
while(f[x]<f[q[t]]&&h<=t){
t--;
}
while(q[h]<l&&h<=t){
h++;
}
q[++t]=x;
}
int main(){
scanf("%lld%lld",&n,&k);
for(long long i=1;i<=n;i++){
scanf("%lld",&a[i]);
tot+=a[i];
}
for(int i=1;i<=n;i++){
f[i]=f[q[h]]+a[i];
push(i,i-k);
}
long long mmin=f[n-k];
for(long long i=n-k+1;i<=n;i++){
mmin=min(f[i],mmin);
}
printf("%lld",tot-mmin);
return 0;
}
/*
5 4
1 2 3 4 5
*/
注
雙倍經驗：P2034 掃描
qzez1926 玉米實驗
大意
給定一個\(n*n\)的矩陣\(a\)，有\(t\)次詢問，每次詢問以\((x_i,y_i)\)為左上角、長寬均為\(k\)的矩陣中，最大值與最小值的差值是多少，
思路
首先，我們還是顯然能得出暴力的代碼：
\(ans_i = \max\limits_{x=x_i , y=y_i}^{x_i+k-1 , y_i+k-1}{a_{{x},{y}}} - \min\limits_{x=x_i , y=y_i}^{x_i+k-1 , y_i+k-1}{a_{{x},{y}}}\)，
然后，由于\(k\)是給定的，這讓我們想到可以用單調佇列優化\(max(a_{{x},{y}})\)和\(min(a_{{x},{y}})\)，即預處理矩陣\(a\)，算出矩陣每一行的長\(k\)的滑動視窗中的最值，詢問時直接查詢子矩陣第一列的最值即可，
代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1005
#define INF 99999999
using namespace std;
int n,k,t,x,y;
int a1[maxn][maxn],a2[maxn][maxn];
int q1[maxn],q2[maxn],h1=1,t1=0,h2=1,t2=0;
int ans1[maxn][maxn],ans2[maxn][maxn];
void push1(int i,int x,int l){//找最小值
while(a1[i][x]<a1[i][q1[t1]]&&h1<=t1){
t1--;
}
q1[++t1]=x;
while(q1[h1]<l&&h1<=t1){
h1++;
}
}
void push2(int i,int x,int l){//找最大值
while(a2[i][x]>a2[i][q2[t2]]&&h2<=t2){
t2--;
}
q2[++t2]=x;
while(q2[h2]<l&&h2<=t2){
h2++;
}
}
void doit(int i){
memset(q1,0,sizeof(q1));
memset(q2,0,sizeof(q2));
h1=1;t1=0;h2=1;t2=0;
q1[++t1]=1;q2[++t2]=1;
for(int j=2;j<k;j++){
push1(i,j,-1);
push2(i,j,-1);
}
for(int j=k;j<=n+k;j++){
push1(i,j,j-k+1);
push2(i,j,j-k+1);
ans1[i][j-k+1]=q1[h1];
ans2[i][j-k+1]=q2[h2];
}
}
int main(){
memset(a1,0x3f,sizeof(a1));
scanf("%d%d%d",&n,&k,&t);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a1[i][j]);
a2[i][j]=a1[i][j];
}
}
for(int i=1;i<=n;i++){
doit(i);
}
// printf("\n");
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// printf("%d ",a2[i][ans2[i][j]]);
// }
// printf("\n");
// }
// printf("\n");
while(t--){
scanf("%d%d",&x,&y);
int mmax=-1,mmin=INF;
for(int i=0;i<k;i++){
mmax=max(mmax,a2[x+i][ans2[x+i][y]]);
mmin=min(mmin,a1[x+i][ans1[x+i][y]]);
}
printf("%d\n",mmax-mmin);
}
return 0;
}
/*
5 3 2
5 1 2 6 3
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9
2 1
1 2
*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/288133.html
標籤：其他