UVA12538 Version Controlled IDE 题解 crope
Version Controlled IDE
传送门
题面翻译
维护一种数据结构,资磁三种操作。
1.在p位置插入一个字符串s
2.从p位置开始删除长度为c的字符串
3.输出第v个历史版本中从p位置开始的长度为c的字符串
1 ≤ n ≤ 50000 1 \leq n \leq 50000 1≤n≤50000,所有字符串总长度小于等于 1 0 6 10^6 106,输出字符串总长度小于等于 20000 20000 20000
强制在线,每次输入中的数字都要减去你的所有输出中字母c的个数
Translated by @litble
题目描述
输入格式
输出格式
样例 #1
样例输入 #1
6
1 0 abcdefgh
2 4 3
3 1 2 5
3 3 3 4
1 4 xy
3 5 4 6
样例输出 #1
bcdef
bcg
bxyc
注明
以上来自 U V a ,翻译来源:洛谷。 以上来自 UVa,翻译来源:洛谷。 以上来自UVa,翻译来源:洛谷。
不如在洛谷看 UVa 的题,在 vjudge 上交。
易懂版题面来自大佬 @shiyihang。
解题思路
前置知识
- crope [ 1 ] ^{[1]} [1]。
正文
需要简化一下题意:
初始有一个空字符串,下标从 1 1 1 开始,进行 N N N 次操作:
- 在第 p p p 个字符后插入一个字符串 s s s 。
- 删除从第 p p p 个字符(包括第 p p p 个)开始的长度为 c c c 的字符串。
- 输出第 v v v 个历史版本中从 p p p 个字符(包括第 p p p 个)开始的长度为 c c c 的字符串。
每次 1 , 2 1,2 1,2 操作形成一个新的版本,初始版本为 0 0 0,编号依次递增。强制在线,每一个输入中的数字减去目前所有输出中字母 c 的个数才是题目描述中的值。
对于所有的数据,满足以下条件:
- 2 ≤ N ≤ 5 × 1 0 4 2 \le N \le 5 \times 10^4 2≤N≤5×104 ;
- 0 ≤ p ≤ 1 0 6 0 \le p \le 10^6 0≤p≤106;
- 0 < ∣ s ∣ , c ≤ 1 0 6 0 \lt |s|, c \le 10^6 0<∣s∣,c≤106。
保证输入数据中的 v v v 在 1 1 1 到 先前输入中 操作一或二 的总数 之间。
对于 2 , 3 2,3 2,3 操作,保证子串不超过原串末尾 p + c ≤ ∣ s ∣ p + c \le |s| p+c≤∣s∣。
很好的 crope 模版题,直接用 crope 按照题意模拟即可。
AC Code
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
int n;
char s[1000005];
crope Rope, His[50005];
int Length;
signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cin >> n;int opt, v, p, c, sum = 0;crope temp;while (n--) {cin >> opt;if (opt == 1) cin >> p >> s, p -= sum, Rope.insert(p, s), His[++Length] = Rope;else if (opt == 2) cin >> p >> c, p -= sum, c -= sum, Rope.erase(p - 1, c), His[++Length] = Rope;else cin >> v >> p >> c, v -= sum, p -= sum, c -= sum, temp = His[v].substr(p - 1, c), sum += count(temp.begin(), temp.end(), 'c'), cout << temp << endl;}return 0;
}
资料来源
- [1]:博客园 @mekdull 实用 STL —— rope 学习笔记。
相关文章:

UVA12538 Version Controlled IDE 题解 crope
Version Controlled IDE 传送门 题面翻译 维护一种数据结构,资磁三种操作。 1.在p位置插入一个字符串s 2.从p位置开始删除长度为c的字符串 3.输出第v个历史版本中从p位置开始的长度为c的字符串 1 ≤ n ≤ 50000 1 \leq n \leq 50000 1≤n≤50000,所…...

OAuth2.0客户端和服务端Java实现
oauth2 引言 读了《设计模式之美》和《凤凰架构》架构安全篇之后,决定写一个OAuth2.0的认证流程的Demo,也算是一个阶段性的总结,具体原理实现见《凤凰架构》(架构安全设计篇)。 涉及到的源码可以从https://github.com/WeiXiao-Hyy/oauth2获…...

物流自动分拣系统激光雷达漫反射板
早在二十世纪六十年代,激光器的诞生为激光雷达技术的发展奠定了基础。随后,激光雷达技术开始应用于各种领域,包括军事、航空、地理勘测等。然而,在物流自动分拣领域,激光雷达的应用相对较晚。 随着物流行业的快速发展和…...

2024 抖音欢笑中国年(三):编辑器技巧与实践
前言 本次春节活动中,我们大部分场景使用内部的 SAR Creator互动方案来实现。 SAR Creator 是一款基于 TypeScript 的高性能、轻量化的互动解决方案,目前支持了Web和字节内部跨端框架平台,服务于字节内部的各种互动业务,包括但不限…...
Python学习入门(1)——基础语句(二)
14. 迭代器和迭代协议 在Python中,迭代器是支持迭代操作的对象,即它们可以一次返回其成员中的一个。任何实现了 __iter__() 和 __next__() 方法的对象都是迭代器。 class Count:def __init__(self, low, high):self.current lowself.high highdef __i…...

vue 百度地图 使用 vue-baidu-map 进行当前位置定位和范围展示
vue 百度地图 使用 vue-baidu-map 进行当前位置定位和范围展示(考勤打卡) 一、创建百度地图账号,获取秘钥二、 引入插件1、安装vue-baidu-map2、在main.js中引入 三、 简单使用 最近写项目的时候,做到了考勤打卡的模块内容&#x…...

使用idea运行程序,发现控制台的中文出现乱码
修改UTF-8发现没有效果,寻找.idea文件夹的encodings.xml文件,将里面的UTF-8全部变成GBK....

基于javassm实现的大学生兼职信息系统
开发语言:Java 框架:ssm JDK版本:JDK1.8 服务器:tomcat7 数据库:mysql 5.7(一定要5.7版本) 数据库工具:Navicat11 开发软件:eclipse/myeclipse/idea Maven包&…...

O2OA开发平台如何查看数据表结构?
在访问后端api地址,页面最下方有列示平台的各个服务,点击进入可查看具体的表内容 后端api地址: http://{hostIP}/x_program_center/jest/list.html 其中:{hostIP}为中心服务器所在域名或者IP地址 如下图:...

心理测评性格测试矩阵版h5微信抖音QQ快手小程序app开源版开发
心理测评性格测试矩阵版h5微信抖音QQ快手小程序app开源版开发 支持SAAS、支持独立加密、支持独立开源、价格不同。 自带题库数据,后台一键初始,支持自己上传题目 心理测评 微信公众号微信小程序抖音小程序可打包APP 支持单题、跳跃题、计分题、因子题、…...
【蓝桥杯】十六进制转八进制 C++实现
1.题目信息 时间限制:1.0s 内存限制:512.0MB 问题描述 给定n个十六进制正整数,输出它们对应的八进制数。 输入格式 输入的第一行为一个正整数n (1<n<10)。 接下来n行,每行一个由09、大写字母AF组成…...

明明设置数字居中对齐,为什么excel的数字却不居中?
有时候在excel里,选中数据,设置对齐方式 左右居中,然而,数字却怎么都不居中,为什么呢? 1.按快捷键Ctrl1,打开单元格自定义格式对话框,看到是初始界面是在数字的会计专用,…...

深入解析API技术:原理、实现与应用
在现代软件开发中,API(应用程序接口)扮演着至关重要的角色。API 允许不同的软件应用程序和系统之间进行通信和数据交换,从而构建出更加高效、灵活和可扩展的软件解决方案。本文将深入解析API技术的原理、实现方法,并附…...
C语言——数组指针变量
一、什么是数组指针 数组指针变量是指向数组的指针,它可以用来遍历数组元素、进行数组操作以及作为函数参数传递数组等操作。在C语言中,数组名本身就是数组的首地址,因此数组指针可以指向数组的首地址。 数组指针变量的基本形式:…...
Redis的过期策略与内存淘汰机制原理及实践
Redis作为高性能的键值存储系统,其对数据过期与内存管理的设计直接影响到系统的性能与资源利用率。本文将以生动的比喻、通俗的语言,深入剖析Redis的过期策略与内存淘汰原理,助您全面理解数据在Redis中的生命周期管理艺术。 一、Redis过期策…...
【24届数字IC秋招总结】提前批面试经验1——小米、百度昆仑芯、长鑫存储
文章目录 前言一、小米-SOC验证工程师1.1 面试问题二、百度昆仑芯-芯片验证工程师2.1 一面面试问题2.2 二面面试问题三、长鑫存储-数字电路前言 提前批面试公司:小米、百度昆仑芯、长鑫存储 一、小米-SOC验证工程师 面试时间:7.23 周末 1.1 面试问题 1、 问研究生项目,自…...
第7章、ReactRedux 实战 - 登录注册验证;
一、登录注册认证系统课程介绍; 1、基本概念; ; 2、代码; 二、搭建前端环境; 1、基本概念; ; 2、代码; 三、搭建后端环境; 1、基本概念; ࿱…...

16路HDMI+AV流媒体IPTV高清编码器JR-3216HD
产品简介: JR-3216HD 16路高清HDMIAV编码器是专业的高清音视频编码产品,该产品具有支持16路高清HDMI音视频采集功能,16路标清AV视频采集功能,16路3.5MM独立外接音频输入,编码输出双码流H.264格式,音频MP3/…...
vscode 配置文件settings.json和c_cpp_properties.json的作用
前言 在 Visual Studio Code (VSCode) 中,settings.json 和 c_cpp_properties.json 都是配置文件,它们分别用于不同的目的。 settings.json settings.json 文件是 VSCode 的用户或工作区设置文件。它允许你自定义 VSCode 的各种行为和外观。 用户设置…...
【postgresql 基础入门】入门教程成形了,八大章节,涵盖库,表,事务,约束,数据类型,聚集函数,轻松入门
Postgresql 基础入门 专栏内容: postgresql内核源码分析手写数据库toadb并发编程 个人主页:我的主页 管理社区:开源数据库 座右铭:天行健,君子以自强不息;地势坤,君子以厚德载物. 序言 Postg…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...

从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...
用鸿蒙HarmonyOS5实现中国象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

高保真组件库:开关
一:制作关状态 拖入一个矩形作为关闭的底色:44 x 22,填充灰色CCCCCC,圆角23,边框宽度0,文本为”关“,右对齐,边距2,2,6,2,文本颜色白色FFFFFF。 拖拽一个椭圆,尺寸18 x 18,边框为0。3. 全选转为动态面板状态1命名为”关“。 二:制作开状态 复制关状态并命名为”开…...
大模型真的像人一样“思考”和“理解”吗?
Yann LeCun 新研究的核心探讨:大语言模型(LLM)的“理解”和“思考”方式与人类认知的根本差异。 核心问题:大模型真的像人一样“思考”和“理解”吗? 人类的思考方式: 你的大脑是个超级整理师。面对海量信…...
OpenGL-什么是软OpenGL/软渲染/软光栅?
软OpenGL(Software OpenGL)或者软渲染指完全通过CPU模拟实现的OpenGL渲染方式(包括几何处理、光栅化、着色等),不依赖GPU硬件加速。这种模式通常性能较低,但兼容性极强,常用于不支持硬件加速…...

Ray框架:分布式AI训练与调参实践
Ray框架:分布式AI训练与调参实践 系统化学习人工智能网站(收藏):https://www.captainbed.cn/flu 文章目录 Ray框架:分布式AI训练与调参实践摘要引言框架架构解析1. 核心组件设计2. 关键技术实现2.1 动态资源调度2.2 …...