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

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 1n50000,所有字符串总长度小于等于 1 0 6 10^6 106,输出字符串总长度小于等于 20000 20000 20000

强制在线,每次输入中的数字都要减去你的所有输出中字母c的个数

Translated by @litble

题目描述

PDF

输入格式

输出格式

样例 #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 次操作:

  1. 在第 p p p 个字符后插入一个字符串 s s s
  2. 删除从第 p p p 个字符(包括第 p p p 个)开始的长度为 c c c 的字符串。
  3. 输出第 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 2N5×104
  • 0 ≤ p ≤ 1 0 6 0 \le p \le 10^6 0p106
  • 0 < ∣ s ∣ , c ≤ 1 0 6 0 \lt |s|, c \le 10^6 0<s,c106


保证输入数据中的 v v v 1 1 1 到 先前输入中 操作一或二 的总数 之间。
对于 2 , 3 2,3 2,3 操作,保证子串不超过原串末尾 p + c ≤ ∣ s ∣ p + c \le |s| p+cs

很好的 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 传送门 题面翻译 维护一种数据结构&#xff0c;资磁三种操作。 1.在p位置插入一个字符串s 2.从p位置开始删除长度为c的字符串 3.输出第v个历史版本中从p位置开始的长度为c的字符串 1 ≤ n ≤ 50000 1 \leq n \leq 50000 1≤n≤50000&#xff0c;所…...

OAuth2.0客户端和服务端Java实现

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

物流自动分拣系统激光雷达漫反射板

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

2024 抖音欢笑中国年(三):编辑器技巧与实践

前言 本次春节活动中&#xff0c;我们大部分场景使用内部的 SAR Creator互动方案来实现。 SAR Creator 是一款基于 TypeScript 的高性能、轻量化的互动解决方案&#xff0c;目前支持了Web和字节内部跨端框架平台&#xff0c;服务于字节内部的各种互动业务&#xff0c;包括但不限…...

Python学习入门(1)——基础语句(二)

14. 迭代器和迭代协议 在Python中&#xff0c;迭代器是支持迭代操作的对象&#xff0c;即它们可以一次返回其成员中的一个。任何实现了 __iter__() 和 __next__() 方法的对象都是迭代器。 class Count:def __init__(self, low, high):self.current lowself.high highdef __i…...

vue 百度地图 使用 vue-baidu-map 进行当前位置定位和范围展示

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

使用idea运行程序,发现控制台的中文出现乱码

修改UTF-8发现没有效果&#xff0c;寻找.idea文件夹的encodings.xml文件&#xff0c;将里面的UTF-8全部变成GBK....

基于javassm实现的大学生兼职信息系统

开发语言&#xff1a;Java 框架&#xff1a;ssm JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09; 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&…...

O2OA开发平台如何查看数据表结构?

在访问后端api地址&#xff0c;页面最下方有列示平台的各个服务&#xff0c;点击进入可查看具体的表内容 后端api地址&#xff1a; http://{hostIP}/x_program_center/jest/list.html 其中&#xff1a;{hostIP}为中心服务器所在域名或者IP地址 如下图&#xff1a;...

心理测评性格测试矩阵版h5微信抖音QQ快手小程序app开源版开发

心理测评性格测试矩阵版h5微信抖音QQ快手小程序app开源版开发 支持SAAS、支持独立加密、支持独立开源、价格不同。 自带题库数据&#xff0c;后台一键初始&#xff0c;支持自己上传题目 心理测评 微信公众号微信小程序抖音小程序可打包APP 支持单题、跳跃题、计分题、因子题、…...

【蓝桥杯】十六进制转八进制 C++实现

1.题目信息 时间限制&#xff1a;1.0s 内存限制&#xff1a;512.0MB 问题描述 给定n个十六进制正整数&#xff0c;输出它们对应的八进制数。 输入格式 输入的第一行为一个正整数n &#xff08;1<n<10&#xff09;。 接下来n行&#xff0c;每行一个由09、大写字母AF组成…...

明明设置数字居中对齐,为什么excel的数字却不居中?

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

深入解析API技术:原理、实现与应用

在现代软件开发中&#xff0c;API&#xff08;应用程序接口&#xff09;扮演着至关重要的角色。API 允许不同的软件应用程序和系统之间进行通信和数据交换&#xff0c;从而构建出更加高效、灵活和可扩展的软件解决方案。本文将深入解析API技术的原理、实现方法&#xff0c;并附…...

C语言——数组指针变量

一、什么是数组指针 数组指针变量是指向数组的指针&#xff0c;它可以用来遍历数组元素、进行数组操作以及作为函数参数传递数组等操作。在C语言中&#xff0c;数组名本身就是数组的首地址&#xff0c;因此数组指针可以指向数组的首地址。 数组指针变量的基本形式&#xff1a…...

Redis的过期策略与内存淘汰机制原理及实践

Redis作为高性能的键值存储系统&#xff0c;其对数据过期与内存管理的设计直接影响到系统的性能与资源利用率。本文将以生动的比喻、通俗的语言&#xff0c;深入剖析Redis的过期策略与内存淘汰原理&#xff0c;助您全面理解数据在Redis中的生命周期管理艺术。 一、Redis过期策…...

【24届数字IC秋招总结】提前批面试经验1——小米、百度昆仑芯、长鑫存储

文章目录 前言一、小米-SOC验证工程师1.1 面试问题二、百度昆仑芯-芯片验证工程师2.1 一面面试问题2.2 二面面试问题三、长鑫存储-数字电路前言 提前批面试公司:小米、百度昆仑芯、长鑫存储 一、小米-SOC验证工程师 面试时间:7.23 周末 1.1 面试问题 1、 问研究生项目,自…...

第7章、ReactRedux 实战 - 登录注册验证;

一、登录注册认证系统课程介绍&#xff1b; 1、基本概念&#xff1b; &#xff1b; 2、代码&#xff1b; 二、搭建前端环境&#xff1b; 1、基本概念&#xff1b; &#xff1b; 2、代码&#xff1b; 三、搭建后端环境&#xff1b; 1、基本概念&#xff1b; &#xff1…...

16路HDMI+AV流媒体IPTV高清编码器JR-3216HD

产品简介&#xff1a; JR-3216HD 16路高清HDMIAV编码器是专业的高清音视频编码产品&#xff0c;该产品具有支持16路高清HDMI音视频采集功能&#xff0c;16路标清AV视频采集功能&#xff0c;16路3.5MM独立外接音频输入&#xff0c;编码输出双码流H.264格式&#xff0c;音频MP3/…...

vscode 配置文件settings.json和c_cpp_properties.json的作用

前言 在 Visual Studio Code (VSCode) 中&#xff0c;settings.json 和 c_cpp_properties.json 都是配置文件&#xff0c;它们分别用于不同的目的。 settings.json settings.json 文件是 VSCode 的用户或工作区设置文件。它允许你自定义 VSCode 的各种行为和外观。 用户设置…...

【postgresql 基础入门】入门教程成形了,八大章节,涵盖库,表,事务,约束,数据类型,聚集函数,轻松入门

Postgresql 基础入门 ​专栏内容&#xff1a; postgresql内核源码分析手写数据库toadb并发编程 个人主页&#xff1a;我的主页 管理社区&#xff1a;开源数据库 座右铭&#xff1a;天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物. 序言 Postg…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...