F - 度度熊学队列 HDU - 6375

2024-03-12 22:58
文章标签 队列 hdu 度度 熊学 6375

本文主要是介绍F - 度度熊学队列 HDU - 6375,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

度度熊正在学习双端队列,他对其翻转和合并产生了很大的兴趣。 

初始时有 NN 个空的双端队列(编号为 11 到 NN ),你要支持度度熊的 QQ 次操作。 

①11 uu ww valval 在编号为 uu 的队列里加入一个权值为 valval 的元素。(w=0w=0 表示加在最前面,w=1w=1 表示加在最后面)。 

②22 uu ww 询问编号为 uu 的队列里的某个元素并删除它。( w=0w=0 表示询问并操作最前面的元素,w=1w=1 表示最后面) 

③33 uu vv ww 把编号为 vv 的队列“接在”编号为 uu 的队列的最后面。w=0w=0 表示顺序接(队列 vv 的开头和队列 uu 的结尾连在一起,队列vv 的结尾作为新队列的结尾), w=1w=1 表示逆序接(先将队列 vv 翻转,再顺序接在队列 uu 后面)。且该操作完成后,队列 vv 被清空。

Input

有多组数据。 

对于每一组数据,第一行读入两个数 NN 和 QQ。 

接下来有 QQ 行,每行 33~44 个数,意义如上。 

N≤150000,Q≤400000N≤150000,Q≤400000 

1≤u,v≤N,0≤w≤1,1≤val≤1000001≤u,v≤N,0≤w≤1,1≤val≤100000 

所有数据里 QQ 的和不超过500000500000 

Output

对于每组数据的每一个操作②,输出一行表示答案。 

注意,如果操作②的队列是空的,就输出−1−1且不执行删除操作。

Sample Input

2 10
1 1 1 23
1 1 0 233
2 1 1 
1 2 1 2333
1 2 1 23333
3 1 2 1
2 2 0
2 1 1
2 1 0
2 1 1

Sample Output

23
-1
2333
233
23333提示由于读入过大,C/C++ 选手建议使用读入优化。一个简单的例子:void read(int &x){char ch = getchar();x = 0;for (; ch < '0' || ch > '9'; ch = getchar());for (; ch >='0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';}

题目意思不用说了,思路就是双端队列queue 照着上面的一步一步的走就可以了。

代码:

#include<stdio.h>
#include<algorithm>
#include<deque>
using namespace std;
int main()
{int nan,mam;while(~scanf("%d%d",&nan,&mam)){deque<int>q[nan+1]; //定义双端队列int a,b,c,d;for(int i=0; i<mam; i++){scanf("%d %d %d",&a,&b,&c);if(a==1||a==3) scanf("%d",&d);if(a==1){if(c==1) q[b].push_back(d);         //进队列尾else if(c==0) q[b].push_front(d);   //进对列头}if(a==2){int t;if(q[b].empty())        //如果队列为空就输出-1;printf("-1\n");else{if(c==0){printf("%d\n",q[b].front());  //输出头q[b].pop_front();         //头出去}else{printf("%d\n",q[b].back());  //输出队列尾q[b].pop_back();          //队列尾出队列}}}else if(a==3){   int tt;if(d==0){deque<int>::iterator it;for(it=q[c].begin(); it!=q[c].end(); it++) //从开始到到结束{   tt=*it;q[b].push_back(tt);               //复制到b 前一个队列中}}if(d==1){deque<int>::reverse_iterator it;for(it=q[c].rbegin(); it!=q[c].rend(); it++)  //从尾到头逆序复制{   tt=*it;q[b].push_back(tt);}}q[c].clear();     //清空队列 c}}}return 0;
}

 

这篇关于F - 度度熊学队列 HDU - 6375的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/802854

相关文章

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :