今天學(xué)習(xí)了二叉樹，了解了二叉樹的創(chuàng)建和遍歷的過程

今天所了解的遍歷過程主要分為三種，前序中序和后序，都是DFS的想法

前序遍歷：先輸出在遍歷左節(jié)點和右節(jié)點（輸出->左->右）

中序遍歷：先遍歷左節(jié)點，再輸出和遍歷右節(jié)點（左->輸出->右）

后序遍歷：先遍歷左節(jié)點和右節(jié)點，最后再輸出（左->右->輸出）? ? ??

#define TElemType char 
typedef struct BiNode{TElmeType data;//數(shù)據(jù)struct BiNode *left,*right;//節(jié)點的左右指針  
}BiNode,*BiTree;
void preOrderTraverse(BiTree T)
{if (T==NULL)return ;printf("%c",T->data);preOrderTraverse(T->left);preOrderTraverse(T->right);//前序遍歷中-左-右，先輸出，再遍歷左和右 
}
void InOrderTraverse(BiTree T)
{if (T==NULL)return ;//中序遍歷左-中-右InOrderTraverse(T->left);//先遍歷左節(jié)點cout<<T->data<<endl;InOrderTraverse(T->right);	
} 
void PostOrderTraverse(BiTree T)
{if (T==NULL)return ;//后序遍歷左右中 PostOrderTraverse(T->left);PostOrderTraverse(T->right);cout<<T->data<<endl;
}
void CreatTree(BiTree *T)
{TElmeType x;cin>>x;if (x=='*'){T=NULL;return;}*T=new BiNode;//T=(BiNode*)malloc(sizeof (BiNode));*T->data=x;CreatTree(&(*T)->left);CreatTree(&(*T)->right); 
}
bool isempty(BiTree T)
{return T==NULL;
}

然后嘗試了一道關(guān)于樹的題目

https://www.luogu.com.cn/problem/P1087

題目描述

我們可以把由 0 和 1 組成的字符串分為三類：全 0 串稱為 B 串，全 1 串稱為 I 串，既含 0 又含 1 的串則稱為 F 串。

FBI 樹是一種二叉樹，它的結(jié)點類型也包括 F 結(jié)點，B 結(jié)點和 I 結(jié)點三種。由一個長度為?2�2N?的 01 串?�S?可以構(gòu)造出一棵 FBI 樹?�T，遞歸的構(gòu)造方法如下：

1. �T?的根結(jié)點為?�R，其類型與串?�S?的類型相同；
2. 若串?�S?的長度大于?11，將串?�S?從中間分開，分為等長的左右子串?�1S1??和?�2S2?；由左子串?�1S1??構(gòu)造?�R?的左子樹?�1T1?，由右子串?�2S2??構(gòu)造?�R?的右子樹?�2T2?。

現(xiàn)在給定一個長度為?2�2N?的 01 串，請用上述構(gòu)造方法構(gòu)造出一棵 FBI 樹，并輸出它的后序遍歷序列。

輸入格式

第一行是一個整數(shù)?�(0≤�≤10)N(0≤N≤10)，

第二行是一個長度為?2�2N?的 01 串。

輸出格式

一個字符串，即 FBI 樹的后序遍歷序列。

輸入輸出樣例

輸入 #1復(fù)制

3
10001011

輸出 #1復(fù)制

IBFBBBFIBFIIIFF

說明/提示

對于?40%40%?的數(shù)據(jù)，�≤2N≤2；

對于全部的數(shù)據(jù)，�≤10N≤10。

這道題就是先按照題目中給出的方法，不斷分治找到當(dāng)串的長度只有1的時候，創(chuàng)建節(jié)點，然后再分散開建立新的節(jié)點，為了便于得到左右節(jié)點的位置，可以設(shè)置新的函數(shù)

int ls(int p){return p*2;
}
int rs(int p){return p*2+1;
}

等完成樹的創(chuàng)建后，最后再一個后序遍歷結(jié)束

#include<bits/stdc++.h>
using namespace std;
char s[1024],tree[4096];
int ls(int p){return p*2;
}
int rs(int p){return p*2+1;
}
void build_FBItree(int p,int l,int r)
{if (l==r){if (s[r]=='1')tree[p]='I';else tree[p]='B';return;}int mid=(l+r)/2;build_FBItree(ls(p),l,mid);build_FBItree(rs(p),mid+1,r);if (tree[ls(p)]=='B' && tree[rs(p)]=='B')tree[p]='B';else if (tree[ls(p)]=='I' && tree[rs(p)]=='I')tree[p]='I';else tree[p]='F';
}
void PostOrderTraverse(int p)
{if (tree[ls(p)])PostOrderTraverse(ls(p));if (tree[rs(p)])PostOrderTraverse(rs(p));printf("%c",tree[p]);
}
int main()
{int n;cin>>n;//cin>>s;scanf("%s",s+1);build_FBItree(1,1,strlen(s+1));PostOrderTraverse(1);return 0;
}

第二題是有關(guān)于搜索的

https://www.lanqiao.cn/problems/644/learning/?page=1&first_category_id=1&problem_id=644

這道題是需要找到所有的對稱分割方法，可以輕松的知道，分割線一定是經(jīng)過對稱中心的，因此可以把起始點設(shè)置在中心對稱處，然后開始向四個方向搜索，當(dāng)碰到邊界的時候就是一種結(jié)果

#include<bits/stdc++.h>
using namespace std;
int ans;
bool vis[10][10];
void dfs(int x,int y)
{if (x==0 || y==0 || x==6 ||y==6)//到達(dá)邊界的時候算一種方案{ans++;return;}int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};for (int i=0;i<4;++i){int tx=x+dir[i][0],ty=y+dir[i][1];if (!vis[tx][ty]){vis[tx][ty]=true;vis[6-tx][6-ty]=true;//由于對稱的關(guān)系，所以只需要訪問一半的對稱圖形就可以了dfs(tx,ty);vis[tx][ty]=false;//因為需要找到所有的情況，所以需要取消標(biāo)記vis[6-tx][6-ty]=false;}}return;
}
int main()
{vis[3][3]=true;//由于對稱的關(guān)系，所以一定經(jīng)過中心對稱點，所以就從這個點開始搜索dfs(3,3);cout<<ans/4;//由于是中心對稱的，所以得到的方案需要除以4return 0;
} 

題2https://www.lanqiao.cn/problems/106/learning/?page=1&first_category_id=1&problem_id=106

題目描述

考慮一種簡單的正則表達(dá)式：

只由 x ( ) | 組成的正則表達(dá)式。

小明想求出這個正則表達(dá)式能接受的最長字符串的長度。

例如 ((xx|xxx)x|(x|xx))xx 能接受的最長字符串是： xxxxxx，長度是 6。

輸入描述

一個由 x()| 組成的正則表達(dá)式。輸入長度不超過 100，保證合法。

輸出描述

這個正則表達(dá)式能接受的最長字符串的長度。

輸入輸出樣例

示例

輸入

((xx|xxx)x|(x|xx))xx

輸出

6

運行限制

• 最大運行時間：1s
• 最大運行內(nèi)存: 256M

這道題，主要用的是遞歸的方法，由于括號內(nèi)的需要重新算，所以遇到括號就調(diào)用函數(shù)，計算括號內(nèi)的值，遇到有括號就相當(dāng)于出棧。

#include<bits/stdc++.h>
using namespace std;
string s;
int pos;
int dfs()
{int len=s.size();int tmp=0,ans=0;while (pos<len){if (s[pos]=='('){//相當(dāng)于入棧，在棧內(nèi)計算括號的數(shù)值pos++;tmp+=dfs(); }else if (s[pos]==')'){//相當(dāng)于出棧pos++;break; }else if (s[pos]=='|'){//相當(dāng)于已經(jīng)找到了需要比較的一邊ans=max(ans,tmp);pos++;//需要找下一個比較的對象所以需要重置tmptmp=0; }else if (s[pos]=='x'){tmp++;pos++;}}//由于缺少最后的|所以需要在循壞退出之后再比較一次ans=max(ans,tmp);return ans; 
}
int main()
{cin>>s;int ans=dfs();cout<<ans;return 0;
}

后面是每周作業(yè)

題3：高手去散步https://www.luogu.com.cn/problem/P1294

題目背景

高手最近談戀愛了。不過是單相思。“即使是單相思，也是完整的愛情”，高手從未放棄對它的追求。今天，這個陽光明媚的早晨，太陽從西邊緩緩升起。于是它找到高手，希望在晨讀開始之前和高手一起在鰲頭山上一起散步。高手當(dāng)然不會放棄這次夢寐以求的機(jī)會，他已經(jīng)準(zhǔn)備好了一切。

題目描述

鰲頭山上有?�n?個觀景點，觀景點兩兩之間有游步道共?�m?條。高手的那個它，不喜歡太刺激的過程，因此那些沒有路的觀景點高手是不會選擇去的。另外，她也不喜歡去同一個觀景點一次以上。而高手想讓他們在一起的路程最長（觀景時它不會理高手），已知高手的穿梭機(jī)可以讓他們在任意一個觀景點出發(fā)，也在任意一個觀景點結(jié)束。

輸入格式

第一行，兩個用空格隔開的整數(shù)?�n?、?�.m.?之后?�m?行，為每條游步道的信息：兩端觀景點編號、長度。

輸出格式

一個整數(shù)，表示他們最長相伴的路程。

輸入輸出樣例

輸入 #1復(fù)制

4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60

輸出 #1復(fù)制

150

說明/提示

對于?100%100%?的數(shù)據(jù)：�≤20n≤20，�≤50m≤50，保證觀景點兩兩之間不會有多條游步道連接。

思路：這道題可以用圖的想法，一個地點可以通向不同的地方，并且是沒有方向限制的，因為題目需要我們求最大的距離，所以我們可以建立一個二維數(shù)組，那么兩個不同的橋就相當(dāng)于它的坐標(biāo)，所包含的值就是他們之間的距離，最后再搜索一下

#include <bits/stdc++.h>
using namespace std;
int vis[25],a[60][60];
int ans,maxn,m,n;
void dfs(int k,int sum)
{ans=max(ans,sum);for (int i=1;i<=n;++i){if (!vis[i] && a[k][i]>0)//判斷能不能走 {vis[i]=1;//目的地打上標(biāo)記 dfs(i,sum+a[k][i]);vis[i]=0;}}return ;
}
int main()
{cin>>n>>m;for (int i=0;i<m;++i){int x,y,s;cin>>x>>y>>s;a[x][y]=s;a[y][x]=s;}for (int i=1;i<=n;++i){vis[i]=1;dfs(i,0);maxn=max(ans,maxn);memset(vis,0,sizeof(vis));//清空標(biāo)記數(shù)組 }cout<<maxn;return 0;
}

接水問題https://www.luogu.com.cn/problem/P1190

題目描述

學(xué)校里有一個水房，水房里一共裝有?�m?個龍頭可供同學(xué)們打開水，每個龍頭每秒鐘的供水量相等，均為?11。

現(xiàn)在有?�n?名同學(xué)準(zhǔn)備接水，他們的初始接水順序已經(jīng)確定。將這些同學(xué)按接水順序從?11?到?�n?編號，�i?號同學(xué)的接水量為?��wi?。接水開始時，11?到?�m?號同學(xué)各占一個水龍頭，并同時打開水龍頭接水。當(dāng)其中某名同學(xué)?�j?完成其接水量要求?��wj??后，下一名排隊等候接水的同學(xué)?�k?馬上接替?�j?同學(xué)的位置開始接水。這個換人的過程是瞬間完成的，且沒有任何水的浪費。即?�j?同學(xué)第?�x?秒結(jié)束時完成接水，則?�k?同學(xué)第?�+1x+1?秒立刻開始接水。若當(dāng)前接水人數(shù)?�′n′?不足?�m，則只有?�′n′?個龍頭供水，其它?�?�′m?n′?個龍頭關(guān)閉。

現(xiàn)在給出?�n?名同學(xué)的接水量，按照上述接水規(guī)則，問所有同學(xué)都接完水需要多少秒。

輸入格式

第一行兩個整數(shù)?�n?和?�m，用一個空格隔開，分別表示接水人數(shù)和龍頭個數(shù)。

第二行?�n?個整數(shù)?�1,�2,…,��w1?,w2?,…,wn?，每兩個整數(shù)之間用一個空格隔開，��wi??表示?�i?號同學(xué)的接水量。

輸出格式

一個整數(shù)，表示接水所需的總時間。

輸入輸出樣例

輸入 #1復(fù)制

5 3
4 4 1 2 1

輸出 #1復(fù)制

4

輸入 #2復(fù)制

8 4
23 71 87 32 70 93 80 76

輸出 #2復(fù)制

163

說明/提示

【輸入輸出樣例 #1 說明】

第?11?秒，33?人接水。第?11?秒結(jié)束時，1,2,31,2,3?號同學(xué)每人的已接水量為?1,31,3?號同學(xué)接完水，44?號同學(xué)接替?33?號同學(xué)開始接水。

第?22?秒，33?人接水。第?22?秒結(jié)束時，1,21,2?號同學(xué)每人的已接水量為?2,42,4?號同學(xué)的已接水量為?11。

第?33?秒，33?人接水。第?33?秒結(jié)束時，1,21,2?號同學(xué)每人的已接水量為?3,43,4?號同學(xué)的已接水量為?22。44?號同學(xué)接完水，55?號同學(xué)接替?44?號同學(xué)開始接水。

第?44?秒，33?人接水。第?44?秒結(jié)束時，1,21,2?號同學(xué)每人的已接水量為?4,54,5?號同學(xué)的已接水量為?11。1,2,51,2,5?號同學(xué)接完水，即所有人完成接水的總接水時間為?44?秒。

【數(shù)據(jù)范圍】

1≤�≤1041≤n≤104，1≤�≤1001≤m≤100，�≤�m≤n；

1≤��≤1001≤wi?≤100。

思路：由于一開始沒有人接水，所以前面幾個人可以立刻去接水，那么就會產(chǎn)生時間，接下來就需要知道剩下的孩子中，去接水所需要的最大時間，由于這題的數(shù)據(jù)量很小，所以我可以每安排一個孩子就排一次序，那么第一個一定是最先走的，所以一定是它的時間加上下一個接水的，等到所有孩子完成接水后，當(dāng)前數(shù)組的最后一個時間就是所需要的最長時間

#include <bits/stdc++.h>
using namespace std;
int main()
{int n,m;cin>>n>>m;int a[10005];int ss[10005];for (int i=0;i<n;++i)cin>>a[i];//初始化水龍頭,把最前面的m個人去接水 for (int i=0;i<m;++i){ss[i]=a[i];}int max=-1;for (int i=m;i<n;++i){sort(ss,ss+m);ss[0]+=a[i];}sort(ss,ss+m);cout<<ss[m-1];return 0;
}

題4：日志分析https://www.luogu.com.cn/problem/P1165

這道題主要就是再建立一個最大值棧，在只有第一個元素的時候，那個元素入棧，在接下來入棧的元素都要與這個最大值元素比較，如果更大就入棧，若遇到出棧指令，那么判斷出棧元素和最大值棧的元素是否相等，如果相等那就都出棧

#include <bits/stdc++.h>
using namespace std;
int main()
{stack<long long>st;stack<long long >maxst;//建立最大值棧找最大值 int n;cin>>n;for (int i=0;i<n;++i){int x;cin>>x;if (x==0){long long  y;cin>>y;if (st.empty()){maxst.push(y);//沒有元素的情況下，剩余的元素就是最大值 }else if (maxst.top()<y){maxst.push(y);}st.push(y);}else if (x==1){if (st.top()==maxst.top())//如果出棧的元素正好等于最大值的話最大值元素就出棧 {maxst.pop();}st.pop();}else if (x==2){if (st.empty())//沒有元素的情況 {cout<<0<<endl;continue;}cout<<maxst.top()<<endl;}}return 0;
}

題5：表達(dá)式括號匹配https://www.luogu.com.cn/problem/P1739

遇到左括號入棧，遇到右括號出棧，有一點特例就是，會出現(xiàn)開頭就是右括號的情況，那么就直接輸出失敗

#include <bits/stdc++.h>
using namespace std;
int main()
{string s;cin>>s;int top=-1;for (int i=0;s[i]!='@';++i){if (s[i]=='(')top++;else if (s[i]==')')top--;if (top<-1){cout<<"NO";return 0;}}if (top==-1)cout<<"YES";else cout<<"NO";return 0;
}

題6：約瑟夫問題https://www.luogu.com.cn/problem/P1996

循環(huán)隊列，假定數(shù)到m的人要走，那么用while循壞直到隊列中沒有元素停止，那么如果當(dāng)前報的數(shù)不是m的話，這個人出去在進(jìn)去，進(jìn)到隊尾，反之則出隊

#include <bits/stdc++.h>
using namespace std;
int main()
{int m,n;cin>>m>>n;queue<int>que;for (int i=1;i<=m;++i){que.push(i);}int cnt=1;while (!que.empty()){if (cnt!=n){que.push(que.front());que.pop();cnt++;}else{cout<<que.front()<<" ";que.pop();cnt=1;}}
}

題6：路障https://www.luogu.com.cn/problem/P3395

BFS和之前掉隕石很像，這個會在不同時間內(nèi)放置路障，那么我們就建立一個二維數(shù)組，并且存放的是路障放置的時間（在這里，如果人走到那個位置恰好有路障，但是時間與人到那個地方時間相同的話，人是不會有事的），初始化路障好了之后，BFS一邊就結(jié)束了，但這里要注意的是路障的個數(shù)是2n-2

#include <bits/stdc++.h>
using namespace std;
int a[1005][1005];
int vis[1005][1005];
struct Queue{int x;int y;int time;
}QQQ[1000000];
int main()
{int t;int flag=0;cin>>t;while (t--){int n;cin>>n;memset(QQQ,0,sizeof(QQQ));memset(a,0,sizeof(a));memset(vis,0,sizeof(vis));if (n==1){cout<<"Yes"<<endl;continue;}for (int i=1;i<=2*n-2;++i)//注意審題2n-2個路障，一直當(dāng)做是n個導(dǎo)致一直報錯 {int x,y;cin>>x>>y;a[x][y]=i;//每個路障位置都帶著時間 }int head=0,tail=0;QQQ[tail].x=1,QQQ[tail].y=1,QQQ[tail].time=0;vis[1][1]=1;tail++;int dic[4][2]={{0,1},{1,0},{0,-1},{-1,0}};while (head!=tail){for (int i=0;i<4;++i){int tx=QQQ[head].x+dic[i][0],ty=QQQ[head].y+dic[i][1],tt=QQQ[head].time+1;if (tx==n && ty==n && (a[tx][ty]==0||tt<=a[tx][ty]) ){flag=1;break;}if (tx>=1 && ty>=1 &&tx<=n && ty<=n && (a[tx][ty]==0||tt<=a[tx][ty]) && !vis[tx][ty]){QQQ[tail].x=tx,QQQ[tail].y=ty,QQQ[tail].time=tt;vis[tx][ty]=1;tail++;}}if (flag)break;head++;}if (flag){cout<<"Yes"<<endl;flag=0;}else cout<<"No"<<endl;}
}

題7：【模板】單調(diào)棧https://www.luogu.com.cn/problem/P5788

單調(diào)棧就是單調(diào)的棧，它需要知道第一個大于當(dāng)前元素的元素的位置，這就符合單調(diào)遞增棧的想法，具體的想法主要是從最后一個元素開始找，如果遇到比他大的元素，那么當(dāng)前棧頂元素就出棧，這就相當(dāng)于當(dāng)你需要一個身高遞增的隊伍的時候，那么卡在中間的比前人矮的人就變成無效的人了，就可以刪除

如果需要找后面第一個比自己小的元素的索引就是，單調(diào)減同理

#include <bits/stdc++.h>
using namespace std;
int a[3000005];
int res[3000005];
int main()
{int m;stack<int>st;scanf("%d",&m);for (int i=1;i<=m;++i)cin>>a[i];
//單調(diào)棧，從后面開始排，用案例來說，會先判斷棧是否為空和是否棧內(nèi)的元素要小于要進(jìn)去的元素
//如果小了，那么棧內(nèi)的元素就失去了價值，需要出棧
//在壓入新元素之前，需要判斷棧是否為空，如果是的，代表沒有元素大于它或者他是最后一個元素，因此輸出0for (int i=m;i>0;--i){while (!st.empty() &&  a[st.top()]<=a[i])st.pop();res[i]=st.empty()?0:st.top();st.push(i);		}for (int i=1;i<=m;++i)cout<<res[i]<<" ";	
} 

題8：滑動窗口 /【模板】單調(diào)隊列滑動窗口 /【模板】單調(diào)隊列 - 洛谷

可以用雙端隊列做，想法和單調(diào)棧類似

這是找最小值的核心代碼

是否需要輸出是看i-k的情況，只有當(dāng)i大于等于k的時候，才會出現(xiàn)窗口才能輸出

由于需要找的是最小值，所以當(dāng)當(dāng)前的元素大于即將進(jìn)去的元素時，需要出隊，這就相當(dāng)于如果有更小的元素，那么隊列里面的比他小的元素都要出隊，然后這個小的進(jìn)去，如果這個元素比他大，那就直接進(jìn)去，因為當(dāng)前的最小的元素很快就會被滑動窗口淘汰

for (int i=1;i<=n;++i){while (!q.empty() && q.back()>a[i])q.pop_back();q.push_back(a[i]);if (i-k>=1 && a[i-k]==q.front())q.pop_front();if (i-k>=0) printf("%d ",q.front());}

最大值同理

#include <bits/stdc++.h>
using namespace std;
int a[1000009];
int main()
{int n,k;scanf("%d %d",&n,&k);deque<int>q;deque<int>p;for (int i=1;i<=n;++i)cin>>a[i];for (int i=1;i<=n;++i){while (!q.empty() && q.back()>a[i])q.pop_back();q.push_back(a[i]);if (i-k>=1 && a[i-k]==q.front())q.pop_front();if (i-k>=0) printf("%d ",q.front());}cout<<endl;q.clear();for (int i=1;i<=n;++i){while (!q.empty() && q.back()<a[i])q.pop_back();q.push_back(a[i]);if (i-k>=1 && a[i-k]==q.front())q.pop_front();if (i-k>=0) printf("%d ",q.front());}
}

題9：小小的埴輪兵團(tuán)https://www.luogu.com.cn/problem/P7505

同理運用雙端隊列完成

#include <bits/stdc++.h>
using namespace std;
deque<long long>q;
long long tot=0;
int main()
{int n,m,k;cin>>n>>m>>k;for (long long  i=0;i<n;++i){long long  a;cin>>a;q.push_back(a);}sort(q.begin(),q.end());for (long long  i=0;i<m;++i){int op;cin>>op;if (op==3){if (q.empty())cout<<0<<endl;	else cout<<q.size()<<endl;	}else if (op==1){long long x;cin>>x;tot+=x;while (!q.empty()){long long  v=q.back();if (v+tot>k)q.pop_back();else break;}}else if (op==2){long long  x;cin>>x;tot-=x;while (!q.empty()){long long  v=q.front();if (v+tot<-k)q.pop_front();else break;}}}	
}

題10：表達(dá)式求值https://www.luogu.com.cn/problem/P1981

運用棧的思想，如果是先把第一個數(shù)放到棧里面，然后判斷字符和數(shù)字，如果字符是乘號的話優(yōu)先級比較高，那么就直接從棧里面取數(shù)字出來和這個讀入的數(shù)字計算，結(jié)果放到棧里面，如果是加號的話，那么就把數(shù)字存到棧里面，最后再統(tǒng)一加起來

#include <bits/stdc++.h>
using namespace std;
#define MOD 10000
int main()
{stack<long long >st;long long a,b;char c;cin>>a;a%=MOD;st.push(a);while (cin>>c>>b){if (c=='*'){long long p=(st.top()*b)%MOD;st.pop();st.push(p);}else if (c=='+'){st.push(b);}else {break;}}long long sum=0;while (!st.empty()){sum=(sum+st.top())%MOD;st.pop();}cout<<sum%MOD;
}

題11：GITARAhttps://www.luogu.com.cn/problem/P6704

建立七個棧，讀入要彈奏的，如果當(dāng)前的數(shù)小于棧頂元素的數(shù)字，那么出棧，出棧也要記錄個數(shù)，結(jié)束出棧后，棧內(nèi)的元素都是小于等于當(dāng)前元素的，所以要判斷，如果棧頂元素與彈奏的元素相同的話，那么不需要再談了，如果是小于的話，那么還需要再談一次。

#include <bits/stdc++.h>
using namespace std;
#define MOD 10000
int main()
{int n,p;cin>>n>>p;stack<int>st[7];int cnt=0;for (int i=0;i<n;++i){int a,b;cin>>a>>b;while (!st[a].empty()>0&&st[a].top()>b){st[a].pop();cnt++;}if (!st[a].empty()){if (st[a].top()==b){continue;}else {st[a].push(b);cnt++;}}else {st[a].push(b);++cnt;}}cout<<cnt;
}

題12：驗證棧序列https://www.luogu.com.cn/problem/P4387

把序列1和序列2的元素都放到兩個數(shù)組里面，對于序列2需要特別的設(shè)置一個了計數(shù)器，然后就是開始遍歷，把序列1中的元素壓入棧中，并且同時判斷，當(dāng)前元素是否和序列2中相同，如果相同的話，就出棧，直到棧內(nèi)沒有元素為止，在繼續(xù)從序列1中壓入元素。元素壓完后，再判斷棧內(nèi)是否有元素，如果沒有就可以完成。

#include <bits/stdc++.h>
using namespace std;
#define MOD 10000
int main()
{int q;cin>>q;stack<int>st1;int a1[100005];int a2[100005];while (q--){int n;cin>>n;for (int i=1;i<=n;++i){cin>>a1[i];}for (int i=1;i<=n;++i){cin>>a2[i];}int cnt=1;for (int i=1;i<=n;++i){st1.push(a1[i]);while(st1.top()==a2[cnt]){st1.pop();cnt++;if (st1.empty())break;} }if (st1.empty()){cout<<"Yes"<<endl;}else {cout<<"No"<<endl;}while (!st1.empty())st1.pop();}return 0;
}