長沙網(wǎng)站制作工作室知名公司關(guān)鍵詞有哪幾種
今天學(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)造方法如下:
- �T?的根結(jié)點為?�R,其類型與串?�S?的類型相同;
- 若串?�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;
}