当前位置: 首页 > 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…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...