題目描述

給出兩個序列 pushed 和 poped 兩個序列，其取值從 1 到?n(n≤100000)。已知入棧序列是 pushed，如果出棧序列有可能是 poped，則輸出?Yes，否則輸出?No。為了防止騙分，每個測試點有多組數據，不超過?5?組。

輸入格式

第一行一個整數?q，詢問次數。

接下來?q?個詢問，對于每個詢問：

第一行一個整數?n?表示序列長度；

第二行?n?個整數表示入棧序列；

第三行?n?個整數表示出棧序列；

輸出格式

對于每個詢問輸出答案。

輸入輸出樣例

輸入 #1復制

2
5
1 2 3 4 5
5 4 3 2 1
4
1 2 3 4
2 4 1 3

輸出 #1復制

Yes
No

代碼實現：

#include <iostream>
#include <stack>
#include <vector>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int main(int argc, char** argv)
?{
??? ?int m,n,i,j,c[100001];
? ? ?cin>>m;
?? ? stack<int> sta;
?? ? for(j=0;j<m;j++)
?? ?{
?? ? ?? ?cin>>n;
?? ? ?? ?int a[n],b[n];
?? ? ?? ?for(i=0;i<n;i++)
?? ? ?? ?{
?? ? ?? ??? ?cin>>a[i];
?? ??? ?}
?? ??? ?for(i=0;i<n;i++)
?? ? ?? ?{
?? ? ?? ??? ?cin>>b[i];
?? ??? ?}
?? ??? ?int head=0;
?? ??? ?for(i=0;i<n;i++)
?? ??? ?{
?? ??? ??? ?sta.push(a[i]);
?? ??? ??? ?while(sta.top()==b[head])
?? ??? ??? ?{
?? ??? ??? ??? ?sta.pop();
?? ??? ??? ??? ?head++;
?? ??? ??? ??? ?if(sta.empty())
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?}
?? ??? ?if(sta.empty())
?? ??? ?{
?? ??? ??? ?c[j]=1;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?c[j]=0;
?? ??? ?}
?? ??? ?while (!sta.empty()) {
? ? ? ? ? ? sta.pop();
? ? ? ? }
?? ?}?
?? ?for(i=0;i<m;i++)
?? ?{
?? ??? ?if(c[i]==0)
?? ??? ?{
?? ??? ??? ?cout<<"No"<<endl;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?cout<<"Yes"<<endl;
?? ??? ?}
?? ?}
?? ?return 0;
}