当前位置: 首页 > news >正文

一道好题——分治

一道好题应该有一个简洁的题面。
有一个长度为 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&#xff0c;初始全为 0 的序列 a&#xff0c;另有一个长度为 n 的序列 b&#xff0c;你希望将 a 变成 b&#xff0c;你可以执行如下两种操作&#xff1a; 1 x&#xff1a;将 a 中所有值为 x 的数 11。 2 x&#xff1a;将 a 中下…...

庖丁解牛:NIO核心概念与机制详解 02 _ 缓冲区的细节实现

文章目录 PreOverview状态变量概述PositionLimitCapacity演示&#xff1a; 观察变量 访问方法get() 方法put()方法类型化的 get() 和 put() 方法 缓冲区的使用&#xff1a;一个内部循环 Pre 庖丁解牛&#xff1a;NIO核心概念与机制详解 01 接下来我们来看下缓冲区内部细节 Ov…...

Python itertools模块中的combinations() 函数用法

Python itertools模块中的combinations 函数用法 调用方法示例1示例2 调用方法 itertools.combinations(iterable, r)各个参数意义&#xff1a; iterable&#xff1a;输入数据&#xff0c;数据应该是可迭代的。 r&#xff1a;子序列的长度 返回值&#xff1a;从输入的可迭代数…...

在线预览excel,luckysheet在vue项目中的使用

一. 需求 需要在内网项目中在线预览excel文档&#xff0c;并可以下载 二.在项目中下载并引入luckysheet 1.打开项目根目录&#xff0c;npm i luckyexcel 安装 npm i luckyexcel2.在项目的index.html文件中引入依赖 外网项目中的引入&#xff08;CDN引入&#xff09;&#…...

【python】OpenCV—Image Pyramid(8)

文章目录 1 图像金字塔2 拉普拉斯金字塔 1 图像金字塔 高斯金字塔 在 OpenCV 中使用函数 cv2.pyrDown()&#xff0c;实现图像高斯金字塔操作中的向下采样&#xff0c;使用函数 cv2.pyrUp() 实现图像金字塔操作中的向上采样 import cv2img cv2.imread(C://Users/Administrat…...

vue3父组件提交校验多个子组件

实现功能&#xff1a;在父组件提交事件中校验多个子组件中的form 父组件&#xff1a; <script setup lang"ts">import {ref, reactive} from vueimport childForm from ./childForm.vueimport childForm2 from ./childForm2.vuelet approvalRef ref()let ap…...

系统移植-uboot

uboot概述&#xff1a; 操作系统运行之前运行的一小段代码&#xff0c;用于将软硬件环境初始化到 一个合适的状态&#xff0c;为操作系统的加载和运行做准备&#xff08;其本身不是操作系统&#xff09; Bootloader基本功能 1.初始化软硬件环境 2.引导加载linux内核 3. 给lin…...

使用FFmpeg合并多个ts视频文件转为mp4格式

前言 爬取完视频发现都是ts文件&#xff0c;而且都是几百KB的视频片段&#xff0c;.ts 全名叫&#xff1a;MPEG Transport Stream&#xff0c;它是一个万能的多媒体容器&#xff0c;可以装下音频、视频、字幕。有时我们需要将.ts文件转换为其他更加广泛被支持的格式&#xff0…...

大模型之十二十-中英双语开源大语言模型选型

从ChatGPT火爆出圈到现在纷纷开源的大语言模型&#xff0c;众多出入门的学习者以及跃跃欲试的公司不得不面临的是开源大语言模型的选型问题。 基于开源商业许可的开源大语言模型可以极大的节省成本和加速业务迭代。 当前&#xff08;2023年11月17日)开源的大语言模型如下&#…...

.Net6 部署到IIS示例

基于FastEndpoints.Net6 框架部署到IIS 环境下载与安装IIS启用与配置访问网站 环境下载与安装 首先下载环境安装程序&#xff0c;如下图所示,根据系统位数选择x86或者x64进行下载安装,网址&#xff1a;Download .NET 6.0。 IIS启用与配置 启用IIS服务 打开控制面板&#xff…...

轻松搭建短域名短链接服务系统,可选权限认证,并自动生成证书认证把nginx的http访问转换为https加密访问,完整步骤和代码

轻松搭建短域名短链接服务系统&#xff0c;可选权限认证&#xff0c;并自动生成证书认证把nginx的http访问转换为https加密访问&#xff0c;完整步骤和代码。 在互联网信息爆炸的时代&#xff0c;网址复杂而冗长&#xff0c;很难在口头告知他人&#xff0c;也难以分享到社交媒体…...

JS 日期格式化

日期格式化 parseTime&#xff1a; // 日期格式化 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年了&#xff0c;一直以为"右键菜单"和"弹出菜单"是不同的。 最近刚刚发现&#xff0c;这两种菜单在定义的时候和消息循环处理程序中并没有什么不同&#xff0c;区别只是在于windows底层显示方式。 如下是右键菜单的显示方式&#xff1…...

查询数据库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中&#xff0c;确实没有像传统Web应用程序中需要使用web.xml配置文件。对于中文乱码问题&#xff0c;你可以采取以下几种方式来解决&#xff1a; 在application.properties文件中添加以下配置&#xff1a; spring.http.encoding.charsetUTF-8 spring.http.encod…...

京东联盟flutter插件使用方法

目录 1.京东联盟官网注册申请步骤略~2.安卓端插件配置&#xff1a;3.IOS端插件配置4.其它配置5.京东OAuth授权 文档地址&#xff1a;https://baiyuliang.blog.csdn.net/article/details/134444104 京东联盟flutter插件地址&#xff1a;https://pub.dev/packages/jdkit 1.京东联…...

python电影数据可视化分析系统的设计与实现【附源码】

电影数据可视化分析系统的设计与实现 (一)开题报告&#xff0c;就是确定设计(论文)选题之后&#xff0c;学生在调查研究的基础上撰写的研究计划&#xff0c;主要说明设计(论文)研究目的和意义、研究的条件以及如何开展研究等问题&#xff0c;也可以说是对设计(论文)的论证和设…...

SQLMAP --TAMPER的编写

跟着师傅的文章进行学习 sqlmap之tamper脚本编写_sqlmap tamper编写-CSDN博客 这里学习一下tamper的编写 这里的tamper 其实就是多个绕过waf的插件 通过编写tamper 我们可以学会 在不同过滤下 执行sql注入 我们首先了解一下 tamper的结构 这里我们首先看一个最简单的例子…...

美国服务器:全面剖析其主要优点与潜在缺点

​  服务器是网站搭建的灵魂。信息化的今天&#xff0c;我们仍需要它来为网站和应用程序提供稳定的运行环境。而美国作为全球信息技术靠前的国家之一&#xff0c;其服务器市场备受关注。那么&#xff0c;美国服务器究竟有哪些主要优点和潜在缺点呢? 优点 数据中心基础设施&a…...

验证二叉搜索树

二叉搜索树 二叉查找树&#xff08;Binary Search Tree&#xff09;&#xff0c;&#xff08;又&#xff1a;二叉搜索树&#xff0c;二叉排序树&#xff09;它或者是一棵空树&#xff0c;或者是具有下列性质的二叉树&#xff1a; 若它的左子树不空&#xff0c;则左子树上所有结…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...

针对药品仓库的效期管理问题,如何利用WMS系统“破局”

案例&#xff1a; 某医药分销企业&#xff0c;主要经营各类药品的批发与零售。由于药品的特殊性&#xff0c;效期管理至关重要&#xff0c;但该企业一直面临效期问题的困扰。在未使用WMS系统之前&#xff0c;其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...

基于单片机的宠物屋智能系统设计与实现(论文+源码)

本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢&#xff0c;连接红外测温传感器&#xff0c;可实时精准捕捉宠物体温变化&#xff0c;以便及时发现健康异常&#xff1b;水位检测传感器时刻监测饮用水余量&#xff0c;防止宠物…...