E - 11/22 Subsequence题解
文章目录
- 大致思路
- 代码
大致思路
-
预处理:
-
用
pos1,pos2,posls分别记录 1 1 1, 2 2 2 , / / / 在字符串中的『位置』 -
用
cum1和cum2分别存储了 1 1 1 和 2 2 2 的前缀和,这样可以快速获取任意区间内的 1 1 1 和 2 2 2 的『数量』
-
-
查询处理:
-
对于每个查询,使用**『前缀和』**来快速获取指定区间内的 1 1 1 和 2 2 2 的数量
-
然后使用
lower_bound和upper_bound查找指定区间内的 / / / 的位置 -
我们对于每个
/的位置,需要计算左侧的 1 1 1 的数量和右侧的 2 2 2 的数量,取小的那个值乘以 2 2 2 再加 1 1 1,接着就可以可以形成的最长的 11 / 22 11/22 11/22 字符串部分序列的『长度』啦 -
最后输出答案就可以了
-
代码
#include <iostream> // 基本输入输出流
#include <algorithm> // 通用算法(排序、查找、去重、二分查找等)
#include <vector> // 动态数组(空间不够会自动扩容)
#include <queue> // 队列(先进先出)
#include <stack> // 栈(先进后出)
#include <set> // 集合(有序不重复)
#include <map> // 键值对容器(映射)
#include <list> // 双向链表
#include <math.h> // 数学函数
#include <functional> // 通用的函数绑定和调用机制#define endl '\n'
#define pii pair<int, int>
#define pdd pair<double, double>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define int long long
using namespace std;const int inf = 1e9 + 7;
const int mod = 998244353;
const int N = 2e5 + 10, M = N << 1;void solve(){int n, q;cin >> n >> q;string s;cin >> s;// 前処理: 1, /, 2 の位置を記録vector<int> pos1, pos2, posls;for (int i = 0; i < n; i++) {if (s[i] == '1') pos1.push_back(i);else if (s[i] == '2') pos2.push_back(i);else if (s[i] == '/') posls.push_back(i);}// 1, 2 の累積和を計算vector<int> cum1(n + 1, 0), cum2(n + 1, 0);for (int i = 0; i < n; i++) {cum1[i + 1] = cum1[i] + (s[i] == '1');cum2[i + 1] = cum2[i] + (s[i] == '2');}while (q--) {int l, r;cin >> l >> r;--l; // 0-indexed に変換// 指定範囲内の 1, 2 の数を取得int count1 = cum1[r] - cum1[l];int count2 = cum2[r] - cum2[l];// 指定範囲内の / の位置を取得auto it1 = lower_bound(posls.begin(), posls.end(), l);auto it2 = upper_bound(posls.begin(), posls.end(), r - 1);vector<int> sah(it1, it2);int maxlen = 0;for (int mid : sah) {if (mid < l || mid >= r) continue;// 左側の 1 の数int l1 = cum1[mid] - cum1[l];// 右側の 2 の数int r2 = cum2[r] - cum2[mid + 1];// 11/22 文字列の部分列の長さを計算int len = min(l1, r2) * 2 + 1;maxlen = max(maxlen, len);}cout << maxlen << endl;}
}signed main(){//重定向输入输出
// freopen("pow.in", "r", stdin);
// freopen("pow.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int _ = 1;
// cin >> _; // 非多组测试数据请注释该行while(_--) solve();return 0;
}相关文章:
E - 11/22 Subsequence题解
文章目录 大致思路代码 大致思路 预处理: 用pos1, pos2, posls 分别记录 1 1 1, 2 2 2 , / / / 在字符串中的『位置』 用cum1 和 cum2 分别存储了 1 1 1 和 2 2 2 的前缀和,这样可以快速获取任意区间内的 1 1 1 和 2 2 2 的『数量』 查询处理: 对于每个查询…...
PyPI 攻击:ChatGPT、Claude 模仿者通过 Python 库传播 JarkaStealer
《Java代码审计》http://mp.weixin.qq.com/s?__bizMzkwNjY1Mzc0Nw&mid2247484219&idx1&sn73564e316a4c9794019f15dd6b3ba9f6&chksmc0e47a67f793f371e9f6a4fbc06e7929cb1480b7320fae34c32563307df3a28aca49d1a4addd&scene21#wechat_redirect 《Web安全》h…...
单片机学习笔记 9. 8×8LED点阵屏
更多单片机学习笔记:单片机学习笔记 1. 点亮一个LED灯单片机学习笔记 2. LED灯闪烁单片机学习笔记 3. LED灯流水灯单片机学习笔记 4. 蜂鸣器滴~滴~滴~单片机学习笔记 5. 数码管静态显示单片机学习笔记 6. 数码管动态显示单片机学习笔记 7. 独立键盘单片机学习笔记 8…...
【大模型-智能体】AutoGen Studio测试和导出工作流程
1. 测试工作流程 AutoGen Studio允许用户针对任务交互式地测试工作流程,并审查由此产生的成果物(如图像、代码和文档)。此外用户还可以查看Agent工作流程在处理任务时的“内心独白”,并查看诸如运行成本(如回合数、令牌…...
【Linux】-学习笔记04
第十二章、磁盘管理 1.查看磁盘空间使用量 1.1df命令 作用: 列出文件系统的磁盘空间占用情况 df,disk free,通过文件系统来快速获取空间大小的信息,当我们删除一个文件的时候,这个文件 不是马上就在文件系统当中消…...
计算机网络:应用层知识点概述及习题
网课资源: 湖科大教书匠 1、概述 习题1 1 在计算机网络体系结构中,应用层的主要功能是 A. 实现进程之间基于网络的通信 B. 通过进程之间的交互来实现特定网络应用 C. 实现分组在多个网络上传输 D. 透明传输比特流 2 以下不属于TCP/IP体系结构应用层范畴…...
如何构建高效的接口自动化测试框架?
🍅 点击文末小卡片 ,免费获取软件测试全套资料,资料在手,涨薪更快 在选择接口测试自动化框架时,需要根据团队的技术栈和项目需求来综合考虑。对于测试团队来说,使用Python相关的测试框架更为便捷。无论选…...
【C++习题】10.反转字符串中的单词 lll
题目: 链接🔗:557.反转字符串中的单词 lll 题目: 代码: class Solution { public:void Reverse(string &s, int start, int end){char tmp;while(start < end){tmp s[start];s[start] s[end];s[end] tmp;…...
undefined symbol: __nvJitLinkComplete_12_4, version libnvJitLink.so.12 问题解决
在部署运行opencompass项目时遇到了如下报错: ImportError: /data/conda/envs/opencompass/lib/python3.10/site-packages/torch/lib/../../nvidia/cusparse/lib/libcusparse.so.12: undefined symbol: __nvJitLinkComplete_12_4, version libnvJitLink.so.12…...
C语言——数组逐元素操作练习
定义一个能容纳10个元素的整形数组a,从键盘读取9个整数存放到前9个数组元素中。 一. 从键盘读取一个整数n和位置p(0<p<8),插入n到数组a中,插入位置:下标p。要求插入点及后续的数组元素都要后移动。 代码如下: …...
HTML的自动定义倒计时,这个配色存一下
<!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>自定义倒计时</title><style>* {mar…...
CUDA补充笔记
文章目录 一、不同核函数前缀二、指定kernel要执行的线程数量三、线程需要两个内置坐标变量来唯一标识线程四、不是blocksize越大越好,上限一般是1024个blocksize 一、不同核函数前缀 二、指定kernel要执行的线程数量 总共需要线程数是: 1 * N N个线程…...
C++二级:满足条件的数的累加
现有n个整数,将其中个位数为k的数进行累加求和。 输入 第一行1个整数n。( 0 < n < 1000) 第二行n个非负整数,以空格分隔,每个数不大于100000。 第三行1个整数k。(0 ≤ k ≤ 9) 输出 输出满足题目要求的累加和。…...
【山大909算法题】2014-T1
文章目录 1.原题2.算法思想3.关键代码4.完整代码5.运行结果 1.原题 为带表头的单链表类Chain编写一个成员函数Reverse,该函数对链表进行逆序操作(将链表中的结点按与原序相反的顺序连接),要求逆序操作就地进行,不分配…...
【MySQL实战45讲笔记】基础篇——深入浅出索引(上)
系列文章 基础篇——MySQL 的基础架构 基础篇——redo log 和 binlog 基础篇——事务隔离 目录 系列文章深入浅出索引(上)4.1 索引的常见模型4.2 InnoDB 的索引模型4.3 索引维护4.4 思考:为什么要重建索引以及如何做? 深入浅出索…...
通关C语言自定义类型:联合和枚举
C语言的自定义类型有四个分别是:数组;结构体(struct);联合体(union);枚举(enum)。前面已经讨论过数组和结构体,这期让我们来学习一下联合体和枚举…...
python高阶技巧一
闭包 简单认识一下闭包 以下代码,内层inner函数不仅依赖于自身的参数b,还依赖于外层outer函数的参数a。inner就是一个闭包函数,既能访问外部变量,又保证外部变量不是全局的,不会被篡改掉,确保了外部变量的…...
Java 对象头、Mark Word、monitor与synchronized关联关系以及synchronized锁优化
1. 对象在内存中的布局分为三块区域: (1)对象头(Mark Word、元数据指针和数组长度) 对象头:在32位虚拟机中,1个机器码等于4字节,也就是32bit,在64位虚拟机中࿰…...
鸿蒙网络编程系列50-仓颉版TCP回声服务器示例
1. TCP服务端简介 TCP服务端是基于TCP协议构建的一种网络服务模式,它为HTTP(超文本传输协议)、SMTP(简单邮件传输协议)等高层协议的应用程序提供了可靠的底层支持。在TCP服务端中,服务器启动后会监听一个或…...
软件测试基础(自动化测试、性能测试)
🍅 点击文末小卡片 ,免费获取软件测试全套资料,资料在手,涨薪更快 自动化测试的意义 缩短软件开发测试周期,可以让产品更快投放市场 测试效率高,充分利用硬件资源 节省人力资源,降低测试…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
