【栈】第十二届蓝桥杯省赛第一场C++ B组/研究生组《双向排序》(c++)
【题目描述】
给定序列 (a1,a2,⋅⋅⋅,an)=(1,2,⋅⋅⋅,n),即 ai=i。
小蓝将对这个序列进行 m 次操作,每次可能是将 a1,a2,⋅⋅⋅,aqi 降序排列,或者将 aqi,aqi+1,⋅⋅⋅,an 升序排列。
请求出操作完成后的序列。
【输入格式】
输入的第一行包含两个整数 n,m,分别表示序列的长度和操作次数。
接下来 m 行描述对序列的操作,其中第 i 行包含两个整数 pi,qi 表示操作类型和参数。当 pi=0 时,表示将 a1,a2,⋅⋅⋅,aqi 降序排列;当 pi=1 时,表示将 aqi,aqi+1,⋅⋅⋅,an 升序排列。
【输出格式】
输出一行,包含 n 个整数,相邻的整数之间使用一个空格分隔,表示操作完成后的序列。
【数据范围】
对于 30% 的评测用例,n,m≤1000;
对于 60% 的评测用例,n,m≤5000;
对于所有评测用例,1≤n,m≤10的5次方,0≤pi≤1,1≤qi≤n。
【输入样例】
3 3
0 3
1 2
0 2
【输出样例】
3 1 2
【样例解释】
原数列为 (1,2,3)。
第 1 步后为 (3,2,1)。
第 2 步后为 (3,1,2)。
第 3 步后为 (3,1,2)。与第 2 步操作后相同,因为前两个数已经是降序了。
【代码】
#include <iostream>
#include <cstring>
#include <algorithm>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 100010;int n, m;
PII stk[N];
int ans[N];int main()
{scanf("%d%d", &n, &m);int top = 0;while (m -- ){int p, q;scanf("%d%d", &p, &q);if (!p){while (top && stk[top].x == 0) q = max(q, stk[top -- ].y);while (top >= 2 && stk[top - 1].y <= q) top -= 2;stk[ ++ top] = {0, q};}else if (top){while (top && stk[top].x == 1) q = min(q, stk[top -- ].y);while (top >= 2 && stk[top - 1].y >= q) top -= 2;stk[ ++ top] = {1, q};}}int k = n, l = 1, r = n;for (int i = 1; i <= top; i ++ ){if (stk[i].x == 0)while (r > stk[i].y && l <= r) ans[r -- ] = k -- ;elsewhile (l < stk[i].y && l <= r) ans[l ++ ] = k -- ;if (l > r) break;}if (top % 2)while (l <= r) ans[l ++ ] = k -- ;elsewhile (l <= r) ans[r -- ] = k -- ;for (int i = 1; i <= n; i ++ )printf("%d ", ans[i]);return 0;
}相关文章:
【栈】第十二届蓝桥杯省赛第一场C++ B组/研究生组《双向排序》(c++)
【题目描述】 给定序列 (a1,a2,⋅⋅⋅,an)(1,2,⋅⋅⋅,n),即 aii。 小蓝将对这个序列进行 m 次操作,每次可能是将 a1,a2,⋅⋅⋅,aqi 降序排列,或者将 aqi,aqi1,⋅⋅⋅,an 升序排列。 请求出操作完成后的序列。 【输入格式】 输入的第一行…...
Gitea 安装和配置
Gitea 安装和配置: http://coffeelatte.vip.cpolar.top/post/software/applications/gitea/gitea_安装和配置/ 文章目录 Gitea 安装和配置: <http://coffeelatte.vip.cpolar.top/post/software/applications/gitea/gitea_%E5%AE%89%E8%A3%85%E5%92%8C%E9%85%8D%E7%BD%AE/>…...
CEF JS与c++能够交互的原理 以及 JS 调用C++的流程分析
相关章节:CEF 之 Render进程 与 Browser进程通信 目录 一、JS与c++能够交互的原理 二、JS调用C++ 流程梳理...
关于比特币的AI对话
【ChatGPT】 比特币源码开源吗? 是的,比特币的源码是开源的。比特币项目是在MIT许可证下发布的,这意味着任何人都可以查看、修改、贡献和分发代码。比特币的源码托管在GitHub上,可以通过下面的链接进行访问: https://g…...
Linux查看磁盘命令df-h详解
df -h 是一个常用的 Linux 命令,用于查看文件系统的磁盘使用情况并以易于阅读的方式显示。以下是 df -h 命令的详细解释: -h:以人类可读的格式显示磁盘空间大小。例如,使用 GB、MB、KB 等单位代替字节。 执行 df -h 命令后&…...
nginx-排查一次大文件无法正常下载问题
目录 问题现象&报错信息 问题现象以及分析 nginx报错信息 问题解决 方法1:配置proxy_max_temp_file_size 方法2:关闭proxy_buffering 参考文档 问题现象&报错信息 问题现象以及分析 文件正常从后端服务器直接下载时,一切正常…...
基于yolov5的草莓成熟度检测系统,可进行图像目标检测,也可进行视屏和摄像检测(pytorch框架)【python源码+UI界面+功能源码详解】
功能演示: 基于yolov5的草莓成熟度检测系统,系统既能够实现图像检测,也可以进行视屏和摄像实时检测_哔哩哔哩_bilibili (一)简介 基于yolov5的草莓成熟度系统是在pytorch框架下实现的,这是一个完整的项目…...
Kubesphere 保姆级分析
应用场景 KubeSphere 适用于多种场景,为企业提供容器化的环境,借助完善的管理和运维功能,让企业在数字化转型过程中从容应对各种挑战和各类业务场景,如多云多集群管理、敏捷软件开发、自动化运维、微服务治理、流量管理以及 DevO…...
力扣hot100:240.搜索二维矩阵II(脑子)
吉大21级算法分析与设计的一道大题,由于每一行都是排好序的直接逐行二分 可以达到:O(mlogn)。但是这里追求更广的思路可以使用其他方法。 矩阵四分: 在矩阵中用中心点比较,如果target大于中心点的值,则由于升序排列&am…...
Apache Hive(三)
一、Apache Hive 1、ETL数据清洗 数据问题 问题1:当前数据中,有一些数据的字段为空,不是合法数据 解决:where 过滤 问题2:需求中,需要统计每天、每个小时的消息量,但是数据中没有天和小时字段…...
ORM(对象关系映射)的概念,并说明在Python中如何使用
ORM(对象关系映射)的概念,并说明在Python中如何使用 ORM(对象关系映射)是一种编程技术,它实现了将关系型数据库中的数据映射到程序中的对象模型,使得开发者能够使用面向对象的方式来操作数据…...
Br 算法
基于google的brotli开源,实现Br算法。 #include <brotli/encode.h> #include <brotli/decode.h>namespace br {/*compress unsigned char* content,if ok return non empty unsigned char * */std::string compress_string(const std::string& c…...
GPT实战系列-一种构建LangChain自定义Tool工具的简单方法
GPT实战系列-一种构建LangChain自定义Tool工具的简单方法 LLM大模型: GPT实战系列-探究GPT等大模型的文本生成 GPT实战系列-Baichuan2等大模型的计算精度与量化 GPT实战系列-GPT训练的Pretraining,SFT,Reward Modeling,RLHF …...
【Docker】Memcached 容器化部署
Memcached环境标准软件基于Bitnami Memcached 构建。当前版本为1.6.24 你可以通过轻云UC部署工具直接安装部署,也可以手动按如下文档操作,该项目已经全面开源,可以从如下环境获取 配置文件地址: https://gitee.com/qingplus/qingcloud-platf…...
Langchain-Chatchat本地搭建ChatGLM3模型和提取PDF内容
文章目录 1、软件要求2、安装CUDA2.1、安装gcc2.2、安装CUDA 3、安装Anaconda33.1、下载Anaconda33.2、创建python虚拟环境 4、部署系统4.1、下载源码4.2、安装依赖4.3、下载模型4.4、初始化配置和知识库4.4.1、初始化配置4.4.2、初始化知识库 4.5、运行4.6、运行4.6.1、启动4.…...
案例分析篇03:一篇文章搞定软考设计模式考点(2024年软考高级系统架构设计师冲刺知识点总结系列文章)
专栏系列文章推荐: 2024高级系统架构设计师备考资料(高频考点&真题&经验)https://blog.csdn.net/seeker1994/category_12593400.html 【历年案例分析真题考点汇总】与【专栏文章案例分析高频考点目录】(2024年软考高级系统架构设计师冲刺知识点总结-案例分析篇-…...
套接字的地址结构,IP地址转换函数,网络编程的接口
目录 一、套接字的地址结构 1.1 通用socket地址结构 1.2 专用socket地址结构 1.2.1 tcp协议族 1.2.3 IP协议族 二、IP地址转换函数 三、网络编程接口 3.1 socket() 3.2 bind() 3.3 listen() 3.4 accept() 3.5 connect() 3.6 close() 3.7 recv()、send() 3.8 recv…...
Java回顾总结--RandomAccessFile和NIO
目录 一、RandomAccessFile1.1 为什么要有RandomAccessFile?1.2 常用方法简介1.3 RandomAccessFile 特点和优势1.3.1 既可以读也可以写1.3.2 可以指定位置读写 1.4 示例 二、NIONIO使用示例 一、RandomAccessFile 1.1 为什么要有RandomAccessFile? Ran…...
2024年3月第15届蓝桥杯青少组STEMA考试C++中高级真题试卷
第15届蓝桥杯青少组STEMA考试C中高级真题试卷(2024年3月) 题目总数:11 总分数:400 选择题 第 1 题 单选题 (110010)2(c3)16的结果是( )。 A. (240)10 B. (11110101)2 C. (366)8 D. (f6)16 第 2 题 单选题 …...
Hyperf AOP 和 注解
注解 (hyperf.wiki) AOP 面向切面编程 (hyperf.wiki) 切面 定义切面(Aspect) 根据官方教程定义一个切面。可以指定类、方法、参数和注解上生效。 <?php namespace App\Aspect;use App\Service\SomeClass; use App\Annotation\SomeAnnotation; use Hyperf\Di\Annotatio…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
