首页/新闻资讯/正文详情

【题解】Codeforces 2260 E. Cyclic Balance

发布时间:2026/9/27 22:56:10 来源:云帆数科 栏目:资讯中心
【题解】Codeforces 2260 E. Cyclic Balance
涉及知识点前缀和我发现我这个想法比官方题解的时间复杂度更低且更容易理解一点分享一下题目大意给定一个长度为 n 的 01 二进制串 s定义字符串的循环平衡状态在它的相邻字符对中00,01,10,11 这四类字符对的数量全部相等并且头尾相邻。共 q 次询问每次给出区间 ( lr ) 一个字串每一次我们可以在子串的任何位置插入一个0或1求对应子串达到循环平衡状态的最小代价。先给个链接Educational Codeforces Round 194 (Div. 2) E. Cyclic Balance核心思路首先我们可以知道一个头尾相连的字符串相邻对数就等于该字符串的长度而要达成题目中所要求的循环平衡状态四种字符对的数量必须相等也就是说我们目标字符串肯定得是 4 的倍数。假设子串长为 m一个字符对出现的次数是 T 次那么目标字符串总长为 4T 。我们需要插入的字符数量就为 4T - m 个。对于所有符合要求的最小四单元子串0011011011001001 我们可以发现本质上就是 0011的循环位移。因此任何长度为 4T 的循环平衡串本质上都可以看作是由 T 个 0011 单元拼接而成的。对于每一个 [l, r] 的区间我们用以下字母统计各字符对的数量a子串中00字符对的数量b子串中11字符对的数量c子串中01或10字符对的数量每一个0011子串单元有以下要求1 个00字符对1 个11字符对1 个01字符对1 个10字符对。由于我们只能插入字符问题就转化成了我们最少需要多少个0011积木单元才能满足所有的条件。约束条件在一个包含01字符对的串中因为首尾相连形成了闭环所以 01 字符对和 10 字符对的数量是相等的对于一个子串lr我们可以预处理出相邻对 01 和 10 的字符对有多少个。假设加上 a[ l ] 和 a[ r ] 是否也是由 0 到 1总共有 d 个字符对那么 01 字符对就有 d / 2 个这里我们记为 c 个 那么我们至少需要 c 个字串单元所以T c。记区间内含 0 的字符对数量为 cnt0 因为含 0 开头的字符串有00、01所以字符对 00 的数量 a 为 cnt0 - c。每个单元至少有两个所以T 记区间内含 1 的字符对数量为 cnt1 因为含 1 开头的字符串有10、11所以字符对 11 的数量 b 为 cnt1 - c。每个单元至少有两个所以T 由于一个子串一定要包含三个字符对a, b, cT 对于上述4个条件由于必须全部都要满足我们应取四个限制条件的 max 这样才是满足所有条件的最小的 T max( t1, t2, t3, t4 )具体实现为了快速求出任意区间 [l, r] 的 cnt1 和01变换次数 d我们预处理两个前缀和数组pre[i]前 i 个字符中1的个数。通过pre[r] - pre[l-1]即可 O(1) 得到区间内 1 的个数 cnt1。pre_diff[i]前 i 个字符中满足 s[i] ! s[i-1] 的相邻位置数量。通过pre_diff[r] - pre_diff[l-1]得到区间内相邻字符不同的次数再结合端点 s[l] 与 s[r] 的关系即可得到 01 变换次数 d。AC代码时间复杂度 O(n q) 官题解是O(n qlogn)#include bits/stdc.h using namespace std; #define int long long #define endl \n typedef pairint,int PII; const int INF0x3f3f3f3f3f3f3f3f; int cal(int a, int b, int c){ int t1 c; int t2 (a c 1) /2; int t3 (b c 1) /2; int t4 (a b c 2) / 3; return max({t1,t2,t3,t4}); } void solve() { int n, q; cin n q; vectorint pre(n 1), pre_diff(n 1); string s; cin s; s s; for(int i 1; i n; i){ pre[i] pre[i - 1] (s[i] - 0); if(i 1) pre_diff[i] pre_diff[i - 1] (s[i] ! s[i - 1]); } while(q--){ int l, r; cin l r; int cnt1 pre[r] - pre[l - 1]; int cnt0 r - l 1 - cnt1; int d pre_diff[r] - pre_diff[l - 1]; d (s[r] ! s[l]); int c d/2; int a cnt0 - c; int b cnt1 - c; int cnt cal(a, b, c); cout 4 * cnt - (r - l 1) endl; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int t 1; // cin t; while(t--){ solve(); } return 0; }

相关推荐

汇川PLC与上位机通讯怎么配?以太网/Modbus TCP/串口参数设置与通讯不上排查
汇川PLC与上位机通讯怎么配?以太网/Modbus TCP/串口参数设置与通讯不上排查

摘要:本文围绕汇川PLC与上位机通讯,系统讲解以太网直连、Modbus TCP、RS485与RS232三类常用通道的配置方法,涵盖主从角色、IP规划、端口与站号、寄存器地址映射(H5U/H3U的D区、R区以及AM/AC的%MW)、功能码与错误响应&a… · 2026/9/27 22:56:10

Python标准库string模块中的Template类提供了一种更为简单、安全且基于规则的字符串替换机制
Python标准库string模块中的Template类提供了一种更为简单、安全且基于规则的字符串替换机制

在Python的软件开发与数据处理流程中,字符串格式化是一项极高频的操作。从生成动态的HTML页面、构建复杂的SQL查询语句,到配置文件的参数注入以及日志信息的标准化输出,开发者无时无刻不在与字符串打交道。Python语言本身提供了多种字符串格式… · 2026/9/27 22:56:04

寻花问柳专注做一家男人喜欢的网站性能优化实战
寻花问柳专注做一家男人喜欢的网站性能优化实战

寻花问柳专注做一家男人喜欢的网站性能优化实战 网站做好了没人访问,这是很多老板建完站后最头疼的事。别急着怀疑内容写得烂,很多时候问题出在加载速度上。用户耐心只有3秒,页面卡一下,人就走了一半。今天聊的这个案例,就是典型的 性能优化… · 2026/9/27 22:55:58

VSCODE加ESP-IDF配置指南:ESP32开发环境搭建与调试
VSCODE加ESP-IDF配置指南:ESP32开发环境搭建与调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 23:31:02

Linux 上 WFDB 心电信号分析实战:从 wfdb.tar.gz 到 HRV 频域分析
Linux 上 WFDB 心电信号分析实战:从 wfdb.tar.gz 到 HRV 频域分析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 23:31:02

ESP32-S3 免驱 USB 摄像头实战:TinyUSB UVC 协议与 OV2640 图像传输
ESP32-S3 免驱 USB 摄像头实战:TinyUSB UVC 协议与 OV2640 图像传输

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 23:30:56

建设的访问网站需要密码?3步搞定完整流程不慌
建设的访问网站需要密码?3步搞定完整流程不慌

建设的访问网站需要密码?3步搞定完整流程不慌 自己不会代码想做网站,却卡在访问需要密码这一步,其实并非技术难题,而是流程认知偏差。很多新手误以为“密码”是技术壁垒,实则是权限配置缺失。本文拆解【建设的访问网站需要密码】背后的完整流程,从原理… · 2026/9/27 23:30:56

VMware虚拟机安全移除非系统磁盘完整指南
VMware虚拟机安全移除非系统磁盘完整指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/27 23:30:56

青岛优化网站关键词实战:从模板站突围到精准获客
青岛优化网站关键词实战:从模板站突围到精准获客

青岛优化网站关键词实战:从模板站突围到精准获客 别再说模板网站太丑了,更可怕的是它丑得连搜索引擎都懒得看。很多老板拿着网上几百块的模板站,问建站报价时觉得便宜,上线后发现排名为零,客户根本搜不到你。青岛这边做本地生意的特别多,从海鲜批发到工… · 2026/9/27 23:30:56

MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现

简介:这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程,从线性调频(LFM)信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑,面向电子信息工程、计算机、数学等专业学生,适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南:5大注意事项救急
汕头网站建设制作厂家避坑指南:5大注意事项救急

汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习

简介:基于PyTorch的多模态虚假新闻检测项目完整代码包,面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者,解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征,以Res… · 2026/9/27 0:00:01

MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现
MATLAB雷达信号脉冲压缩仿真:LFM线性调频、匹配滤波与距离分辨率实现

简介:这套Matlab仿真工具完整呈现雷达信号脉冲压缩过程,从线性调频(LFM)信号生成、目标回波仿真到匹配滤波压缩处理均有可运行代码支撑,面向电子信息工程、计算机、数学等专业学生,适用于课程设计、期末大作… · 2026/9/27 0:00:01

汕头网站建设制作厂家避坑指南:5大注意事项救急
汕头网站建设制作厂家避坑指南:5大注意事项救急

汕头网站建设制作厂家避坑指南:5大注意事项救急 改个需求建站公司拖一周,这种憋屈事我见得太多了。 很多汕头老板找本地建站团队,签合同前看着方案挺美,一上线就变脸。 今天不聊虚的,直接拆解找 汕头网站建设制作厂家 时的5个核心 注意事项… · 2026/9/27 0:00:01

多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习
多模态虚假新闻检测实战:BERT+ResNet双塔与对比学习

简介:基于PyTorch的多模态虚假新闻检测项目完整代码包,面向自然语言处理与计算机视觉交叉方向的开发者、科研人员及毕业设计选题者,解决社交媒体中文本与图像联合识别虚假新闻的问题。系统以BERT预训练模型提取文本语义特征,以Res… · 2026/9/27 0:00:01

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码