蓝桥杯 20. 压缩变换
压缩变换
原题目链接
题目描述
小明最近在研究压缩算法。他知道,压缩时如果能够使数值很小,就能通过熵编码得到较高的压缩比。然而,要使数值变小是一个挑战。
最近,小明需要压缩一些正整数序列,这些序列的特点是:后面出现的数字,很可能是刚出现过不久的数字。为了压缩这些特殊序列,小明设计了一种变换规则,来减小数值大小。
变换规则如下:
从左到右枚举序列,对每个数字进行如下操作:
- 如果该数字没有出现过,将其变换为它的相反数;
- 如果该数字出现过,则找到它上一次出现的位置,计算从那次出现之后到当前位置之间出现了多少种不同的数字,并将这个种类数替换原来的数字。
示例说明:
给定序列 (1, 2, 2, 1, 2)
,变换过程如下:
原序列位置 | 值 | 说明 | 变换后值 |
---|---|---|---|
a₁ | 1 | 首次出现 | -1 |
a₂ | 2 | 首次出现 | -2 |
a₃ | 2 | 上次出现在 a₂,a₂ 到 a₃ 之间无新数字 | 0 |
a₄ | 1 | 上次出现在 a₁,a₁ 到 a₄ 之间有 1 个不同数字(2) | 1 |
a₅ | 2 | 上次出现在 a₃,a₃ 到 a₅ 之间有 1 个不同数字(1) | 1 |
变换后序列为:-1 -2 0 1 1
输入描述
- 第一行包含一个整数
n
,表示序列的长度。 - 第二行包含
n
个正整数,表示原始序列。
数据范围:
1 ≤ n ≤ 10⁵
1 ≤ aᵢ ≤ 10⁹
输出描述
输出一行包含 n
个整数,表示变换后的序列,用空格分隔。
输入样例
5
1 2 2 1 2
输出样例
-1 -2 0 1 1
c++代码
#include<bits/stdc++.h>
#include<stdio.h>using namespace std;class query {
public:int l, r, key;
};int n, m;
vector<int> trees, arr;
vector<query> querys;
vector<vector<int>> end_by_r;
unordered_map<int, int> mp;
vector<string> temp;
unordered_map<string, int> ans;bool mycom(query a, query b) { return a.r < b.r; }void build(int p, int l, int r) {if (l == r) {trees[p] = 1;return;}int mid = (l + r) / 2;build(2 * p, l, mid);build(2 * p + 1, mid + 1, r);trees[p] = trees[2 * p] + trees[2 * p + 1];
}void update(int p, int l, int r, int k) {if (l == r && l == k) {trees[p] = 0;return;}int mid = (l + r) / 2;if (k <= mid) update(2 * p, l, mid, k);else update(2 * p + 1, mid + 1, r, k);trees[p] = trees[2 * p] + trees[2 * p + 1];
}int ask(int p, int l, int r, int range_l, int range_r) {if (range_l <= l && range_r >= r) return trees[p];int mid = (l + r) / 2, ans = 0;if (mid >= range_l) ans += ask(2 * p, l, mid, range_l, range_r);if (mid < range_r) ans += ask(2 * p + 1, mid + 1, r, range_l, range_r);return ans;
}int main() {scanf("%d", &n);trees = vector<int>(4 * n), arr = vector<int>(n + 1), end_by_r = vector<vector<int>>(n + 1);for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);build(1, 1, n);for (int i = 1; i <= n; i++) {if (mp.find(arr[i]) != mp.end()) {int x = mp[arr[i]], y = i;x++, y--;if (x <= y) {query q;q.l = x, q.r = y, q.key = querys.size();querys.push_back(q);}}mp[arr[i]] = i;}mp.clear();m = querys.size();sort(querys.begin(), querys.end(), mycom);for (int i = 0; i < m; i++) end_by_r[querys[i].r].push_back(i);for (int i = 1; i <= n; i++) {if (mp.find(arr[i]) != mp.end()) update(1, 1, n, mp[arr[i]]);mp[arr[i]] = i;for (int x : end_by_r[i]) {string s = to_string(querys[x].l) + " " + to_string(querys[x].r);ans[s] = ask(1, 1, n, querys[x].l, querys[x].r);}}mp.clear();for (int i = 1; i <= n; i++) {if (mp.find(arr[i]) == mp.end()) {mp[arr[i]] = i;arr[i] = -arr[i];}else {int x = mp[arr[i]], y = i;mp[arr[i]] = i;x++, y--;if (x > y) arr[i] = 0;else arr[i] = ans[to_string(x) + " " + to_string(y)];}}for (int i = 1; i <= n; i++) {printf("%d", arr[i]);if (i != n) printf(" ");}return 0;
}//by wqs
题目解析
我们需要设计一个算法快速求出[L,R]区间上有多少个不同的数,可以用线段树,或者树状数组,莫队算法。
线段树法
然后就是套模版进去就行。
相关文章:
蓝桥杯 20. 压缩变换
压缩变换 原题目链接 题目描述 小明最近在研究压缩算法。他知道,压缩时如果能够使数值很小,就能通过熵编码得到较高的压缩比。然而,要使数值变小是一个挑战。 最近,小明需要压缩一些正整数序列,这些序列的特点是&a…...
BY免费空间去掉?i=1
BY免费空间去掉?i1 使用说明 支持域名:tae.dpdns.org 前提绑定主机,申请主机–控制面板选择–子域名,绑定xxx.tae.dpdns.org子域名 默认开启DDoS防御,无防火墙规则,建议用.htaccess来防御 默认去掉访问统计?i1 …...
中篇:深入剖析 L2CAP 与 ATT 协议模块(约5000字)
引言 在 BLE 协议栈中,L2CAP 与 ATT 承担了关键的数据分发、协议复用与属性访问职责。对多协议并存和大数据场景的应用,深入理解这两层协议的分片重组、流控机制、MTU/MTU 协商和 ATT 操作流程,对于提升系统性能与稳定性至关重要。本篇将全面拆解 L2CAP 与 ATT 的原理与实战…...
【C语言】C语言结构体:从基础到高级特性
前言 在C语言的世界里,结构体是一种强大而灵活的自定义数据类型,它能够将不同类型的数据组合在一起,形成一个逻辑上的整体。从简单的数据聚合到复杂的内存对齐优化,再到高效的位段操作,结构体在系统编程、嵌入式开发和…...
电控---JTAG协议
一、物理层架构与信号特性 1. 引脚定义与电气规范 核心引脚: TCK(测试时钟):频率范围0.1MHz至50MHz(如Xilinx Spartan-6支持25MHz),上升沿采样数据。TMS(测试模式选择)…...
FreeRTOS【3】任务调度算法
重要概念 在运行的任务,被称为"正在使用处理器",它处于运行状态。在单处理系统中,任何时间里只能有一个任务处于运行状态。 非运行状态的任务,它处于这 3 中状态之一:阻塞(Blocked)、暂停(Suspended)、就绪…...
高德地图API + three.js + Vue3基础使用与使用 + 标记不显示避坑
three.js小白的学习之路。 最近闲来无事,突然想起来之前好像项目有需求说是要将模型放在地图上。加上在浏览别的大佬写的博客时,也找到了一些大佬写的相关文章。基本上都是使用的高德地图开放平台的JS API。我也随之开启了自己的学习之路。 先简单学习…...
书籍推荐:《价值心法》一姜胡说
书名 :《价值心法》一姜胡说 摘录 每天问问自己,如果今天只做一件事,这件事是什么?找到它。拿出2—3个小时,专门处理这件事。其他所有事全部排在那2—3个小时之外。 集中一段时间用来做最重要的事。这段时…...
Linux GPIO驱动开发实战:Poll与异步通知双机制详解
1. 引言 在嵌入式Linux开发中,GPIO按键驱动是最基础也最典型的案例之一。本文将基于一个支持poll和异步通知双机制的GPIO驱动框架,深入剖析以下核心内容: GPIO中断与防抖处理环形缓冲区设计Poll机制实现异步通知(SIGIO)实现应用层交互方式 …...
x-cmd install | brows - 终端里的 GitHub Releases 浏览器,告别繁琐下载!
目录 核心功能与优势安装适用场景 还在为寻找 GitHub 项目的特定 Release 版本而苦恼吗?还在网页上翻来覆去地查找下载链接吗?现在,有了 brows,一切都将变得简单高效! brows 是一款专为终端设计的 GitHub Releases 浏览…...
一天学完Servlet!!!(万字总结)
文章目录 前言Servlet打印Hello ServletServlet生命周期 HttpServletRequest对象常用api方法请求乱码问题请求转发request域对象 HttpServletResponse对象响应数据响应乱码问题请求重定向请求转发与重定向区别 Cookie对象Cookie的创建与获取Cookie设置到期时间Cookie注意点Cook…...
c#-命名和书写规范
文章目录 1. 接口名称以大写 I 开头2. 属性类型以单词 Attribute 结尾3. 枚举类型对非标记使用单数名词,对标记使用复数名词4. 标识符不应包含两个连续下划线(__)字符5. 对变量、方法和类使用有意义的描述性名称6. 将 PascalCase 用于类名和方法名称7. 对方法参数和局部变量…...
【双指针】和为s的两个数字
57. 和为target的两个数字 剑指 Offer 57. 和为s的两个数字 输入一个递增排序的数组和一个数字target,在数组中查找两个数,使得它们的和正好是target。如果有多对数字的和等于target,则输出任意一对即可。 示例 1: 输入&…...
【Vue】TypeScript与Vue3集成
个人主页:Guiat 归属专栏:Vue 文章目录 1. 前言2. 环境准备与基础搭建2.1. 安装 Node.js 与 npm/yarn/pnpm2.2. 创建 Vue3 TypeScript 项目2.2.1. 使用 Vue CLI2.2.2. 使用 Vite(推荐)2.2.3. 目录结构简述 3. Vue3 TS 基础语法整…...
win11中wsl在自定义位置安装ubuntu20.04 + ROS Noetic
wsl的安装 环境自定义位置安装指定ubuntu版本VsCodeROS备份与重载备份重新导入 常用命令参考文章 环境 搜索 启用或关闭 Windows 功能 勾选这2个功能,然后重启 自定义位置安装指定ubuntu版本 从网上找到你所需要的相关wsl ubuntu版本的安装包,一般直…...
【数据可视化-29】食物营养成分数据可视化分析
🧑 博主简介:曾任某智慧城市类企业算法总监,目前在美国市场的物流公司从事高级算法工程师一职,深耕人工智能领域,精通python数据挖掘、可视化、机器学习等,发表过AI相关的专利并多次在AI类比赛中获奖。CSDN…...
手动实现legend 与 echarts图交互 通过js事件实现图标某项的高亮 显示与隐藏
通过html实现legend的样式 提供调用echarts的api实现与echarts图表交互的效果 实现饼图element实现类似于legend与echartstu表交互效果 效果图 配置代码 <template><div style"height: 400px; width: 500px;background-color: #CCC;"><v-chart:opti…...
C语言编程--16.删除链表的倒数第n个节点
题目: 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 示例 1: 输入:head [1,2,3,4,5], n 2 输出:[1,2,3,5] 示例 2: 输入:head [1], n 1 输出:…...
centos7使用certbot完成nginx ssl证书续期
没有废话纯干货 yum源配置(配置好的可以跳过) #到/etc/yum.repos.d/下mkdir bak,将所用东西mv到bak下 cd /etc/yum.repos.d/ mkdir bak mv ./* bak/ wget https://mirrors.aliyun.com/repo/Centos-7.repo 没有安装nginx的话,配…...
ECharts学习之 toolbox 工具栏
toolbox: {show: true,feature: {//数据视图工具,可以展现当前图表所用的数据dataView: {title: "数据视图",readOnly: false, //是否不可编辑,即只读lang:[数据视图,关闭,刷新] //数据视图上有三个话术},magicType: {type: ["line"…...
修改el-select背景颜色
修改el-select背景颜色 /* 修改el-select样式--直接覆盖默认样式(推荐) */ ::v-deep .el-select .el-input__inner {background-color: #1d2b72 !important; /* 修改输入框背景色 */color: #fff; } ::v-deep .el-select .el-input__wrapper {background-…...
Qt 使用 MySQL 数据库的基本方法
在 Qt 中,使用 MySQL 数据库的基本方法主要是通过 QSqlDatabase、QSqlQuery 等类来进行数据库的连接、查询和数据操作。以下是 Qt 中连接和操作 MySQL 数据库的基本步骤。 1. 安装 MySQL 驱动 首先,确保您的 Qt 环境已经配置了 MySQL 驱动。通常&#…...
BLIP 系列论文(BLIP、BLIP-2、InstructBLIP)
BLIP BLIP 是 Salesforce 团队在多模态领域中的经典工作,影响力巨大,BLIP 系列包括:BLIP、BLIP-2、InstructBLIP。 BLIP 在多模态大模型之前,多模态领域中最流行的是视觉-语言预训练(Vision-Language Pre-training,…...
【玩转全栈】—— 无敌前端究极动态组件库--Inspira UI
目录 Inspira UI 介绍 配置环境 使用示例 效果: Inspira UI 学习视频: 华丽优雅 | Inspira UI快速上手_哔哩哔哩_bilibili 官网:https://inspira-ui.com/ Inspira UI 介绍 Inspira UI 是一个设计精美、功能丰富的用户界面库,专为…...
Java24新增特性
Java 24(Oracle JDK 24)作为Java生态的重要更新,聚焦AI开发支持、后量子安全、性能优化及开发者效率提升,带来20余项新特性和数千项改进。以下是核心特性的分类解析: 一、语言特性增强:简化代码与模式匹配 …...
Git多人协作与企业级开发模型
目录 1.多人协作一 2.多人协作二 3.远程分⽀删除后,本地gitbranch-a依然能看到的解决办法 4.企业级开发模型 4.1.Git的重要性 4.2.系统开发环境 4.3.Git 分⽀设计规范 1.多人协作一 ⽬前,我们所完成的⼯作如下: 基本完成Git的所有本…...
Android学习总结之扩展基础篇(一)
一、IdleHandler工作原理 1. IdleHandler 接口定义 IdleHandler 是 MessageQueue 类中的一个接口,定义如下: public static interface IdleHandler {/*** 当消息队列空闲时会调用此方法。* return 如果返回 true,则该 IdleHandler 会保留在…...
C语言教程(十六): C 语言字符串详解
一、字符串的表示 在C语言中,字符串是由一系列字符组成,并且以空字符 \0 作为结束标志。字符串通常用字符数组来表示。例如: char str[] {H, e, l, l, o, \0};也可以使用字符串字面量来初始化字符数组:char str[] "Hello&…...
Redis LFU 策略参数配置指南
一、基础配置步骤 设置内存上限 在 redis.conf 配置文件中添加以下指令,限制 Redis 最大内存使用量(例如设置为 4GB): maxmemory 4gb选择 LFU 淘汰策略 根据键的作用域选择策略: # 所有键参与淘汰 maxmemory-…...
Pikachu靶场-unsafe upfileupload
不安全的文件上传漏洞防御与对抗方式对照表 防御方式 防御实现 攻击者对抗方式 对抗原理 文件类型白名单验证 仅允许指定扩展名(如 .jpg, .png) if (!in_array($ext, [jpg, png])) { die(); } 伪造文件类型: 1. 修改文件头(…...
Python基础语法:查看数据的类型type(),数据类型转换,可变和不可变类型
目录 查看数据类型type() 使用type()语句查看数据的类型 变量无类型而数据有类型 数据类型转换 在字符串,整型,浮点数之间相互转换 可变类型和不可变类型 查看数据类型type() 使用type()语句查看数据的类型 Python中使用type(被查看数据的类型)语…...
高防IP是如何防护DDoS攻击和CC攻击的
高防IP是一种针对网络攻击(如DDoS和CC攻击)设计的防护服务,其核心原理是通过流量调度、智能清洗和分布式防护节点等技术,将恶意流量拦截在目标服务器之外。以下是其防护DDoS和CC攻击的具体机制: 一、防御DDoS攻击的机制…...
从认证到透传:用 Nginx 为 EasySearch 构建一体化认证网关
在构建本地或云端搜索引擎系统时,EasySearch 凭借其轻量、高性能、易部署等优势,逐渐成为众多开发者和技术爱好者的首选。但在实际部署过程中,如何借助 Nginx 为 EasySearch 提供高效、稳定且安全的访问入口,尤其是在身份认证方面…...
利用deepseek快速生成甘特图
一、什么是甘特图 甘特图(Gantt Chart)是一种直观的项目管理工具,广泛应用于多个领域,主要用于时间规划、任务分配和进度跟踪。 直观性:时间轴清晰展示任务重叠或延迟。 灵活性:支持…...
突破厚铜PCB阻抗控制难题:多级阻抗实现方法
随着电子技术的发展,电子设备对电路板的性能要求越来越高。其中,阻抗控制是电路板设计中的一个重要环节,尤其是对于高频、高速的电子设备。厚铜电路板由于其优良的导电性能和机械强度,被广泛应用于各种高端电子设备中。然而&#…...
JCP官方定义的Java技术体系组成部分详解
JCP官方定义的Java技术体系组成部分详解 1. Java平台规范(Java Platform Specifications) 定义:由JCP制定的Java平台核心规范,包括Java SE(标准版)、Java EE(企业版,现为Jakarta EE…...
如何在 Windows上安装 Python 3.6.5?
Windows 系统安装步骤 下载安装包 安装包下载链接:https://pan.quark.cn/s/9294ca0fd46a 运行安装程序 双击下载的 .exe 文件(如 python-3.6.5.exe)。 勾选 Add Python 3.6 to PATH(重要!这将自动配置环境变量&…...
OpenHarmony 开源鸿蒙北向开发——hdc工具使用及常用命令(持续更新)
hdc(OpenHarmony Device Connector)是为开发人员提供的用于设备连接调试的命令行工具,该工具需支持部署在 Windows/Linux/Mac 等系统上与 OpenHarmony 设备(或模拟器)进行连接调试通信。简单来讲,hdc 是 Op…...
【C语言】C语言动态内存管理
前言 在C语言编程中,内存管理一直是程序员需要重点关注的领域。动态内存管理更是如此,它不仅涉及到内存的灵活分配和释放,还隐藏着许多潜在的陷阱。本文将从动态内存分配的基础讲起,逐步深入到常见的错误、经典笔试题分析&#x…...
Java 运算符:深度解析
前言 作为Java开发者,运算符是我们每天都会接触的基础元素。然而,很多开发者对运算符的理解仅停留在表面层次。本文将全面深入地剖析Java中的各类运算符,揭示其底层原理、使用技巧和最佳实践,帮助您成为真正的Java运算符专家。 …...
健康养生小窍门
健康养生是我们对美好生活的追求,掌握一些实用的小窍门,能让我们轻松拥抱健康。 在生活起居方面,要注重环境的营造。卧室的窗帘选择遮光性好的材质,保证睡眠时的黑暗环境,有助于提高睡眠质量。在室内放置一些绿植&…...
4月24号
网络编程: //IP的对象一台电脑的对象 InetAddress address InetAddress.getByName("DESKTOP-5OJJSAM"); System.out.println(address); String name address.getHostName(); System.out.println(name);//DESKTOP-5OJJSAM String ip address.getHostAddress(); Sys…...
【RocketMq源码篇-01】环境搭建、基本使用、可视化界面
RocketMq源码核心篇整体栏目 内容链接地址【一】环境搭建、基本使用、可视化界面https://zhenghuisheng.blog.csdn.net/article/details/147481401 环境搭建、基本使用、可视化界面 一,RocketMq源码分析1. docker安装rocketMq2. rocketMq基本使用2.1,创建…...
Mysql的深度分页查询优化
一、深度分页为什么慢? 当执行 SELECT * FROM orders ORDER BY id LIMIT 1000000, 10 时: MySQL 会扫描前 1,000,010 行,丢弃前 100 万行,仅返回 10 行。偏移量(offset)越大,扫描行数越多&…...
OpenCv高阶(十一)——物体跟踪
文章目录 前言一、OpenCV 中的物体跟踪算法1、均值漂移(Mean Shift):2、CamShift:3、KCF(Kernelized Correlation Filters):4、MIL(Multiple Instance Learning)…...
第一章:Model Context Protocol (MCP)
Chapter 1: Model Context Protocol (MCP) 🌟 为什么需要MCP? 想象你正在训练一只小狗,希望它能听懂你的指令并执行任务。但如果你和小狗用不同语言交流,它可能完全不知道你的意思。类似地,大型语言模型(L…...
【SAP PP】COOIS报表分析
本文目录 一、基本查询操作 二、订单参数文件 三、COOIS报表增强BADI COOIS报表是PP模块核心报表,是系统中一个功能强大的标准报表,COOIS可查询查询生产订单的状态、进度、组件、工序、报工等信息的综合型报表,,关联了生产订单…...
2025上海车展|紫光展锐发布新一代旗舰级智能座舱芯片平台A888
4月24日,在第二十一届上海国际汽车工业展览会(以下简称“上海车展”)期间,紫光展锐重磅推出新一代旗舰级智能座舱芯片平台A8880,以强劲实力全面助力汽车座舱智能化迈向新征程。 三大核心能力,紧抓市场机遇 …...
蓝牙4.0与蓝牙5.0的区别
蓝牙4.0与蓝牙5.0的主要区别: 传输速度:蓝牙5.0的传输速度是蓝牙4.0的两倍,理论速率可达2Mbps,而蓝牙4.0为1Mbps。 传输距离:蓝牙5.0的传输距离是蓝牙4.0的四倍,在开放空间可达300米,而蓝牙4.0…...
Vue 的单文件组件(.vue 文件)script 标签的使用说明
在 Vue 的单文件组件(.vue 文件)中,最多可以编写 2 个 <script> 标签,但需要满足特定条件: 1. Vue 3 的情况(主流用法) 从 Vue 3.2 开始,官方支持以下两种形式共存࿱…...