一道好题——分治
一道好题应该有一个简洁的题面。
有一个长度为 n,初始全为 0 的序列 a,另有一个长度为 n 的序列 b,你希望将 a 变成 b,你可以执行如下两种操作:
1 x:将 a 中所有值为 x 的数 +1+1。
2 x:将 a 中下标为 x 的数 +1+1。
你不需要最小化操作次数,但只能使用最多 2000020000 次操作。
Input
第一行 一个正整数 n(1≤n≤1000)。
第二行 n 个非负整数 b1 ,⋯,bn (0≤ bi ≤n)描述序列 b。
Output
第一行一个整数 k 表示操作次数,你需要保证 0≤k≤20000。
之后 k 行每行两个整数 ,1 x 或 2 x,表示一次操作。对于 1 x 类型的操作,你需要保证 0≤x≤n,对于 2 x 类型的操作,你需要保证 1≤x≤n。
Input
4
2 4 3 1
Output
7
1 0
2 1
2 2
2 3
2 2
1 3
2 3
解析:
考虑分治,将所有相等的数压在一起先,然后每次让后半截先 +1 然后就可以提出后半截变成子问题了。做完后半截再做前半截。
这样大概是 nlogn 次。
要先进行 后半截的操作,避免 1类型操作。
这样造成的效果就是
1 1 1 1 1 1 1 1
1 1 2 1 1 1 2 1
1 1 2 2 1 2 2 1
1 1 3 3 1 3 3 1
1 1 3 4 1 4 3 1
1 2 3 4 2 4 3 1
(排序后) (原序列)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const int N=2e6+10;
vector <PII> a;
vector <PII> ans;
int n;
void dfs(int l,int r,int now)
{if (l>r) return ;if (l==r){while (now<a[l].first){ans.push_back({2,a[l].second});now++;}return ;}else{while (now<a[l].first){ans.push_back({1,now});now++;}int mid=l+r>>1;mid++;while (mid<=r&&a[mid].first<=now) mid++;if (mid<=r){for (int i=mid;i<=r;i++) ans.push_back({2,a[i].second});dfs(mid,r,now+1);dfs(l,mid-1,now);}}
}
signed main()
{ios;cin>>n;for (int i=1;i<=n;i++){int x;cin>>x;a.push_back({x,i});}sort(a.begin(),a.end());dfs(0,a.size()-1,0);cout<<ans.size()<<endl;for (auto x:ans) cout<<x.first<<" "<<x.second<<endl;return 0;
}
相关文章:
一道好题——分治
一道好题应该有一个简洁的题面。 有一个长度为 n,初始全为 0 的序列 a,另有一个长度为 n 的序列 b,你希望将 a 变成 b,你可以执行如下两种操作: 1 x:将 a 中所有值为 x 的数 11。 2 x:将 a 中下…...
庖丁解牛:NIO核心概念与机制详解 02 _ 缓冲区的细节实现
文章目录 PreOverview状态变量概述PositionLimitCapacity演示: 观察变量 访问方法get() 方法put()方法类型化的 get() 和 put() 方法 缓冲区的使用:一个内部循环 Pre 庖丁解牛:NIO核心概念与机制详解 01 接下来我们来看下缓冲区内部细节 Ov…...
Python itertools模块中的combinations() 函数用法
Python itertools模块中的combinations 函数用法 调用方法示例1示例2 调用方法 itertools.combinations(iterable, r)各个参数意义: iterable:输入数据,数据应该是可迭代的。 r:子序列的长度 返回值:从输入的可迭代数…...
在线预览excel,luckysheet在vue项目中的使用
一. 需求 需要在内网项目中在线预览excel文档,并可以下载 二.在项目中下载并引入luckysheet 1.打开项目根目录,npm i luckyexcel 安装 npm i luckyexcel2.在项目的index.html文件中引入依赖 外网项目中的引入(CDN引入)&#…...
【python】OpenCV—Image Pyramid(8)
文章目录 1 图像金字塔2 拉普拉斯金字塔 1 图像金字塔 高斯金字塔 在 OpenCV 中使用函数 cv2.pyrDown(),实现图像高斯金字塔操作中的向下采样,使用函数 cv2.pyrUp() 实现图像金字塔操作中的向上采样 import cv2img cv2.imread(C://Users/Administrat…...
vue3父组件提交校验多个子组件
实现功能:在父组件提交事件中校验多个子组件中的form 父组件: <script setup lang"ts">import {ref, reactive} from vueimport childForm from ./childForm.vueimport childForm2 from ./childForm2.vuelet approvalRef ref()let ap…...
系统移植-uboot
uboot概述: 操作系统运行之前运行的一小段代码,用于将软硬件环境初始化到 一个合适的状态,为操作系统的加载和运行做准备(其本身不是操作系统) Bootloader基本功能 1.初始化软硬件环境 2.引导加载linux内核 3. 给lin…...
使用FFmpeg合并多个ts视频文件转为mp4格式
前言 爬取完视频发现都是ts文件,而且都是几百KB的视频片段,.ts 全名叫:MPEG Transport Stream,它是一个万能的多媒体容器,可以装下音频、视频、字幕。有时我们需要将.ts文件转换为其他更加广泛被支持的格式࿰…...
大模型之十二十-中英双语开源大语言模型选型
从ChatGPT火爆出圈到现在纷纷开源的大语言模型,众多出入门的学习者以及跃跃欲试的公司不得不面临的是开源大语言模型的选型问题。 基于开源商业许可的开源大语言模型可以极大的节省成本和加速业务迭代。 当前(2023年11月17日)开源的大语言模型如下&#…...
.Net6 部署到IIS示例
基于FastEndpoints.Net6 框架部署到IIS 环境下载与安装IIS启用与配置访问网站 环境下载与安装 首先下载环境安装程序,如下图所示,根据系统位数选择x86或者x64进行下载安装,网址:Download .NET 6.0。 IIS启用与配置 启用IIS服务 打开控制面板ÿ…...
轻松搭建短域名短链接服务系统,可选权限认证,并自动生成证书认证把nginx的http访问转换为https加密访问,完整步骤和代码
轻松搭建短域名短链接服务系统,可选权限认证,并自动生成证书认证把nginx的http访问转换为https加密访问,完整步骤和代码。 在互联网信息爆炸的时代,网址复杂而冗长,很难在口头告知他人,也难以分享到社交媒体…...
JS 日期格式化
日期格式化 parseTime: // 日期格式化 export function parseTime(time, pattern) {if (arguments.length 0 || !time) {return null}const format pattern || {y}-{m}-{d} {h}:{i}:{s}let dateif (typeof time object) {date time} else {if ((typeof time st…...
右键菜单和弹出菜单的区别
接触windows开发10年了,一直以为"右键菜单"和"弹出菜单"是不同的。 最近刚刚发现,这两种菜单在定义的时候和消息循环处理程序中并没有什么不同,区别只是在于windows底层显示方式。 如下是右键菜单的显示方式࿱…...
查询数据库DQL
DQL 查询基本语法 -- DQL :基本语法; -- 1查询指定的字段 name entrydate 并返回select name , entrydate from tb_emp;-- 2 查询 所有字段 并返回select id, username, password, name, gender, image, job, entrydate, create_time, update_time from tb_emp;-- 2 查询…...
SpringBoot中文乱码问题解决方案
在Spring Boot中,确实没有像传统Web应用程序中需要使用web.xml配置文件。对于中文乱码问题,你可以采取以下几种方式来解决: 在application.properties文件中添加以下配置: spring.http.encoding.charsetUTF-8 spring.http.encod…...
京东联盟flutter插件使用方法
目录 1.京东联盟官网注册申请步骤略~2.安卓端插件配置:3.IOS端插件配置4.其它配置5.京东OAuth授权 文档地址:https://baiyuliang.blog.csdn.net/article/details/134444104 京东联盟flutter插件地址:https://pub.dev/packages/jdkit 1.京东联…...
python电影数据可视化分析系统的设计与实现【附源码】
电影数据可视化分析系统的设计与实现 (一)开题报告,就是确定设计(论文)选题之后,学生在调查研究的基础上撰写的研究计划,主要说明设计(论文)研究目的和意义、研究的条件以及如何开展研究等问题,也可以说是对设计(论文)的论证和设…...
SQLMAP --TAMPER的编写
跟着师傅的文章进行学习 sqlmap之tamper脚本编写_sqlmap tamper编写-CSDN博客 这里学习一下tamper的编写 这里的tamper 其实就是多个绕过waf的插件 通过编写tamper 我们可以学会 在不同过滤下 执行sql注入 我们首先了解一下 tamper的结构 这里我们首先看一个最简单的例子…...
美国服务器:全面剖析其主要优点与潜在缺点
服务器是网站搭建的灵魂。信息化的今天,我们仍需要它来为网站和应用程序提供稳定的运行环境。而美国作为全球信息技术靠前的国家之一,其服务器市场备受关注。那么,美国服务器究竟有哪些主要优点和潜在缺点呢? 优点 数据中心基础设施&a…...
验证二叉搜索树
二叉搜索树 二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
