本地测试无误,WA12345
查看原帖
本地测试无误,WA12345
444195
caramel_qwq楼主2022/3/31 19:22

主要是模拟弹出时是否与输入弹出序列有矛盾,有矛盾就是no,否则yes

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
const int MAXN=1e5+8;
int q,n,ru[MAXN];
int chus[MAXN],chu[MAXN],len;
int main(){
	scanf("%d",&q);
	while(q--){
		memset(chus,0,sizeof(chus));
		len=1;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&ru[i]);
		}
		for(int i=1;i<=n;i++){
			scanf("%d",&chu[i]);
		}
		int j=1;
		stack<int> s;
		for(int i=1;i<=n;i++){
			if(s.size()>=1&&s.top()==chu[j]){
				chus[len++]=s.top();
				s.pop();
				j++;
			}
			s.push(ru[i]);
		}
		bool flag=true;
		len--;
		for(int i=1;i<=len;i++){
			if(chus[i]==chu[i]){
				flag=false;
				break;
			}
		}
		if(flag==true){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}
	return 0;
}
2022/3/31 19:22
加载中...