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

CF Edu152 C

Problem - C - Codeforces

题意:

思路:

首先,观察样例可知

这种是等效的

推广一下

0000.....111111

..l..............r......

这种是等效的

容易想到维护后面第一个1的位置和前面第一个0的位置,然后把所有区间都等效一下,开一个二元组的set

但是有点问题,考虑一些特殊case

0001111

这样的,很明显等效之后左端点在右端点后面

1

这种的也是

这些特殊case有什么共同点呢?这些区间一个区间sort之后对应一种情况

因此直接插入 {-1, -1}即可

111100000

那么这种呢?等效前和等效后的区间是一样的,直接插入即可

Code:

#include <bits/stdc++.h>#define int long longusing i64 = long long;constexpr int N = 2e5 + 10;
constexpr int M = 2e5 + 10;
constexpr int P = 2600;
constexpr i64 Inf = 1e18;
constexpr int mod = 1e9 + 7;
constexpr double eps = 1e-6;std::string s;int n, m;
int a[N];
int pre0[N];//前面第一个0的位置
int suf1[N];//后面第一个1的位置void solve() {std::cin >> n >> m >> s;s = " " + s;for (int i = 1; i <= n; i ++) {a[i] = s[i] - '0';}pre0[0] = 0;suf1[n + 1] = n + 1;for (int i = 1; i <= n; i ++) {if (a[i] == 0) pre0[i] = i;else pre0[i] = pre0[i - 1];}for (int i = n; i >= 1; i --) {if (a[i] == 1) suf1[i] = i;else suf1[i] = suf1[i + 1];}std::set<std::pair<int,int> > S;for (int i = 1; i <= m; i ++) {int l, r;std::cin >> l >> r;int tl = suf1[l];int tr = pre0[r];if (tl > tr) S.insert({-1, -1});else S.insert({tl, tr});}std::cout << S.size() << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while (t--) {solve();}return 0;
}

相关文章:

CF Edu152 C

Problem - C - Codeforces 题意&#xff1a; 思路&#xff1a; 首先&#xff0c;观察样例可知 这种是等效的 推广一下 0000.....111111 ..l..............r...... 这种是等效的 容易想到维护后面第一个1的位置和前面第一个0的位置&#xff0c;然后把所有区间都等效一下&…...

iBooker 技术评论 20230902

一、女子同时供职 16 家公司却从不上班&#xff0c;全国骗薪群体至少有七八百人&#xff0c;为何会出现此类骗薪群体&#xff1f; 社保其实很好绕过。就是这些骗薪者一起创立一个外包公司&#xff0c;然后通过这个公司把自己外包出去。这些人和外包公司签的是劳务合同&#xf…...

视频动态壁纸 Dynamic Wallpaper for Mac中文

Dynamic Wallpaper是一款Mac平台上的动态壁纸应用程序&#xff0c;它可以根据时间等因素动态切换壁纸&#xff0c;提供更加生动和多样化的桌面体验。 Dynamic Wallpaper包含了多个动态壁纸&#xff0c;用户可以根据自己的喜好选择和切换。这些动态壁纸可以根据时间等因素进行自…...

Java“牵手”京东商品列表数据,关键词搜索京东商品数据接口,京东API申请指南

京东商城是一个网上购物平台&#xff0c;售卖各类商品&#xff0c;包括服装、鞋类、家居用品、美妆产品、电子产品等。要获取京东商品列表和商品详情页面数据&#xff0c;您可以通过开放平台的接口或者直接访问京东商城的网页来获取商品详情信息。以下是两种常用方法的介绍&…...

springboot实战(三)之多环境部署配置文件生效方式

环境&#xff1a; jdk&#xff1a;1.8 springboot版本&#xff1a;2.7.15 配置&#xff1a; 1.新建yml文件 在resources包中创建application-dev.yml、application-testing.yml两个yml文件 2.配置 在application.yml进行配置生效文件 3.注意事项 新建yml的名称必须以&qu…...

java透传参数至logback,自定义日志文件名。过期日志文件自动删除

LogFilter filter日志拦截&#xff0c;把不需要打印的日志信息拦截在外&#xff0c;只录入有key参数的&#xff08;filterReply FilterReply.ACCEPT;&#xff09;。 package com.***.***.filter;import ch.qos.logback.classic.Level; import ch.qos.logback.classic.spi.IL…...

HFSS 3维曲线导入

HFSS 3维曲线导入 简介环境参考代码使用结果 简介 如图一所示&#xff0c;CST中可以通过导入和到出由任意点组成的曲线&#xff0c;但是HFSS中貌似不能导入&#xff08;如图二所示&#xff09;&#xff0c;如果我们要将matlab的产生的曲线的点的数据导入特变麻烦&#xff0c;特…...

【消息中心】kafka消费失败重试10次的问题

Kafka消费失败重试10次的问题通常可以通过配置Kafka消费者来调整。在Kafka中&#xff0c;可以通过设置max.poll.interval.ms、fetch.min.bytes、fetch.max.bytes、fetch.max.wait.ms等参数来控制消费者的拉取消息的行为。 在Spring-Kafka中&#xff0c;消费失败的重试次数可以…...

无涯教程-Python机器学习 - Semi-supervised Learning函数

Python机器学习 中的 Semi - 无涯教程网无涯教程网提供https://www.learnfk.com/python-machine-learning/machine-learning-with-python-semi-supervised-learning.html...

7 | 计算每个键对应的平均值,并按降序排序

假设您有一个包含销售订单的RDD,其中每个元素是一个键值对,其中键表示产品名称,值表示销售数量。您希望按产品名称对销售订单进行分组,并计算每个产品的总销售数量。最后,希望获得每个产品的总销售数量以及按产品名称分组的详细销售订单列表。 计算每个键对应的总和和计数…...

kafka详解二

kafka详解二 1、 offset 1.1 offset介绍 老版本 Consumer 的位移管理是依托于 Apache ZooKeeper 的&#xff0c;它会自动或手动地将位移数据提交到 ZooKeeper 中保存。当 Consumer 重启后&#xff0c;它能自动从 ZooKeeper 中读取位移数据&#xff0c;从而在上次消费截止的地…...

SAP_ABAP_接口技术_RFC远程函数实践总结

SAP ABAP顾问能力模型梳理_企业数字化建设者的博客-CSDN博客SAP Abap顾问能力模型&#xff0c;ALV/REPORT|SMARTFROM|SCREEN|OLE|BAPI|BDC|PI|IDOC|RFC|API|WEBSERVICE|Enhancement|UserExits|Badi|Debughttps://blog.csdn.net/java_zhong1990/article/details/132469977 SAP接…...

计算机 --> 磁盘 --> 分区

一、分区&#xff1b;步骤较完整&#xff0c;未测试 网址&#xff1a;电脑硬盘怎么分区&#xff1f;C盘/D盘/E盘......快来创建自己的DIY磁盘吧&#xff01;_e盘怎么创建_布 迪的博客-CSDN博客...

3D视觉测量:形位公差 平面度测量(附源码)

文章目录 0. 测试效果1. 基本内容2. 实现方法3. 代码实现4. 参考文章目录:3D视觉测量目录微信:dhlddxB站: Non-Stop_0. 测试效果 1. 基本内容 平面度是一个表达平面平整程度的度量指标,它描述了一个表面与一个理想平面之间的偏差程度。在工程和制造领域,平面度是一个重要的…...

vmware虚拟机远程开发

目录 1. 下载vmware2. 下载ubuntu镜像3. 安装4. 做一些设置4.1 分辨率设置4.2 语言下载4.3 输入法设置4.4 时区设置 5. 直接切换管理员权限6. 网络6.1 看ip6.2 ssh 7. 本地编译器连接远程服务器7.1 创建远程部署的配置7.2 文件同步7.3 远程启动项目 8. ubuntu安装golang环境8.1…...

Web安全——穷举爆破上篇(仅供学习)

Web安全 一、概述二、常见的服务1、burpsuite 穷举后台密码2、burpsuite 对 webshell 穷举破解密码3、有 token 防御的网站后台穷举破解密码3.1 burpsuite 设置宏获取 token 对网站后台密码破解3.2 编写脚本获取token 对网站后台密码破解 4、针对有验证码后台的穷举方法4.1 coo…...

POJ 3045 Cow Acrobats 二分+优先队列

一、题目大意 题目中给出了N头牛&#xff0c;这些牛要互相叠罗汉&#xff0c;牛i承担的风险risk[i]为牛i上面的牛的质量之和sum[i]&#xff08;如果上面没有牛就是0&#xff09;减去牛i的力量strength[i]&#xff0c;即risk[i]sum[i]-strength[i] 我们要优化这个叠罗汉的顺序…...

手写实现call() apply() bind()函数,附有详细注释,包含this指向、arguments讲解

手写实现call() apply() bind()函数是很经典的问题&#xff0c;但是能掰扯清楚的文章确实不算多&#xff0c;于是笔者才决定写下本文&#xff0c;希望能给读者带来一些启发&#xff0c;如有错误欢迎指正。 目录 补充知识 函数中的this指向 类数组对象arguments call() 原理…...

MySQL中日期、时间直接相减的坑

前言 在牛客网上写一道 SQL 题时&#xff0c;需要计算两个日期之间相隔的秒数&#xff0c;我在写的时候直接将两个日期进行相减&#xff0c;得出来的值却不是相差的秒数。 情景再现 我在 MySQL 中进行了测试&#xff0c;得出的结论是&#xff1a;如果日期类型直接相减&#…...

漏洞发现-web应用发现探针类型利用(43)

关于在真实环境下面&#xff0c;这个漏洞该如何发现 这里老师把它分成了三块第一类是 #已知cms 如常见的dedecms&#xff0c;discuz&#xff0c;wordpress等源码结构&#xff0c;这些都是网上比较知名的php源码的cms的名称&#xff0c;这是我们在国内常见的几个程序&#xf…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...