【栈】第十二届蓝桥杯省赛第一场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…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
Visual Studio Code 扩展
Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后,命令 changeCase.commands 可预览转换效果 EmmyLua…...
6.9-QT模拟计算器
源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...
解析“道作为序位生成器”的核心原理
解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制,重点解析"道作为序位生成器"的核心原理与实现框架: 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...
