无容量限制的出栈序列验证——模拟

---

title: 无容量限制的出栈序列验证——模拟
categories:
- ICPC
tags:
- null
abbrlink: ea3c3b0a
date: 2024-03-20 00:00:00

#include<iostream>
#include<stack>
using namespace std;
//stack<int>q;//栈q 
int n,m,t;
const int N=1100;
int a[N],sum=1;//入栈队列a，待检验队列b，计数器sum 
int main()
{
	cin>>m>>n>>t;
for(int i=1;i<=n;i++)
		cin>>a[i];
	while(t--){
		stack<int>q;//栈q 
		int b[N];sum=1;
	bool hve=false;
	for(int i=1;i<=n;i++)
		cin>>b[i];//平平无奇的输入 
	for(int i=1;i<=n;i++)
		{
			//cerr<<i<<" "<<q.size()<<endl;
			if(q.size()>=m){
				cout<<"NO"<<endl;
				hve=true;
				break;
			}
			q.push(a[i]);//入栈 
			while((q.top())==b[sum])//当栈顶元素与b中当前元素相同时出栈 
			{
				q.pop(),sum++;//sum++到b下一个元素 
				if(q.empty())break;//注意这里，第一次RE就因为当栈空时还用了出栈操作，所以要手动结束循环 
			}
		}
		if(hve)continue;
		if(q.empty()) cout<<"YES"<<endl;//如果栈为空说明出栈序列b正确 
		else cout<<"NO"<<endl;
		//while(!q.empty())q.pop();//清空栈 
	}
	return 0;//谢幕 
}