一道好题——分治
一道好题应该有一个简洁的题面。
有一个长度为 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),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
