本文主要是介绍5069. 一端进,两端出 浙江大学考研上机题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
给定一个输入受限的双端队列(即一个端点允许插入和删除,另一个端点只允许删除的双端队列)和一个长度为 N 的插入序列。
插入序列中的元素两两不同。
你需要将插入序列中的元素按顺序依次插入到给定队列中。
在插入过程中和插入完成后的任意时刻,你可以随时删除队列中的现有元素(如果有的话)。
将所有元素按删除顺序进行排列可以得到删除序列。
现在,给定 K个删除序列,对于每个删除序列,请你判断其能否通过给定插入序列得到。
输入格式
第一行包含两个整数 N,K。
第二行包含 N个不同的整数,表示插入序列。
接下来 K 行,每行包含一个删除序列,保证每个删除序列都是给定插入序列的一个排列。
输出格式
每个删除序列,输出一行答案,如果该删除序列可以通过给定插入序列得到,则输出 yes
,否则输出 no
。
数据范围
1≤N≤10e5
1≤K≤10
序列中元素的取值范围 [1,109]。
输入样例:
解释
5 4 10 2 3 4 5 10 3 2 5 4 5 10 3 2 4 2 3 10 4 5 3 5 10 4 2
输出样例:
解释
yes no yes yes
/*算法思想:可以删 《a--------------b》 可以删可以插要删除的x(1)x !=a && x!=b 不能删 返回no(2)x==a || x == b 可以删
*/
#include<bits/stdc++.h>
using namespace std;
const int N =10e5+100;
int n,m;
int a[N],b[N],q[N];bool cheak()
{int hh = 1,tt=0;for(int i =1,j=1; i<=n;i++){q[++tt]=a[i];while(tt>=hh){if(b[j]==q[hh]){j++;hh++;}else if(b[j]==q[tt]){tt--;j++;}else{break;}}}if(tt<hh) return true;else return false;
}int main(){cin >>n>>m;for(int i = 1; i<=n;i++)//插入数列{cin>>a[i]; }while(m--){for(int i = 1; i <=n;i++)//删除数列{cin >> b[i];}if(cheak()){puts("yes");}else{puts("no");}}return 0;
}
这篇关于5069. 一端进,两端出 浙江大学考研上机题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!