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

B. 攻防演练 (2021CCPC女生赛)

题意:

给出一个长度为n的字符,字符是前m个小写字母,有q个询问,每次询问一个最短子序列的长度满足不是[l,r]内任意一个子序列

思路:

[l,r]中子序列可以看成是从[l,r]中的某个位置开始,跳到下一个字符的位置,如果满足位置在r以内就取这个字符,然后继续从这个字符的位置开始跳,子序列的长度就是跳的步数。

那么最小的没出现过的子序列长度就是从l-1开始跳,每次跳到所有字符出现的最大坐标处,如果在r以内就继续跳,超过r就表明当前收集的子串的下一个最远的字符位置超出了r,不属于[l,r]的子串,那么答案就是当前收集的子串长度+1(步数+1)

用nxt[i][j]表示从第i个位置往后的下一个字符为j的坐标,那么我们从后往前处理

用f[i][j]表示从第i个位置开始走,走2^j步能走到的最大坐标,先预处理f[i][0],转换方程是f[i][j]=f[f[i][j-1]][j-1]

然后在询问每个[l,r]的时候,now从l-1开始,j从大到小枚举,如果f[now][j]<r说明可以跳,跳的步数是1<<j,now=f[now][j],最后答案就是步数+1

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,m,q;
string s;
int nxt[N][30];
int f[N][30];
int pos[30];
void sove(){cin>>m>>n;cin>>s;s=" "+s;for(int i=0;i<m;i++)nxt[n][i]=n+1;for(int i=n;i>=1;i--){pos[s[i]-'a']=i;for(int j=0;j<m;j++){if(pos[j])nxt[i-1][j]=pos[j];else nxt[i-1][j]=n+1;
//			cout<<"i-1=="<<i-1<<" j=="<<j<<" nxt="<<nxt[i-1][j]<<endl;}}for(int i=0;i<=n;i++){int mx=0;for(int j=0;j<m;j++)mx=max(mx,nxt[i][j]);f[i][0]=mx;
//		cout<<"i=="<<i<<" f=="<<f[i][0]<<endl;for(int j=0;j<19;j++) f[n][j]=f[n+1][j]=n+1;}for(int j=1;j<19;j++){for(int i=0;i<=n;i++){f[i][j]=f[f[i][j-1]][j-1];
//			cout<<"i=="<<i<<" j=="<<j<<" f="<<f[i][j]<<endl;}}cin>>q;while(q--){int ans=0;int l,r;cin>>l>>r;int now=l-1;for(int j=18;j>=0;j--){if(f[now][j]<=r){
//				cout<<"now=="<<now<<" j=="<<j<<" f=="<<f[now][j]<<endl;ans+=1<<j;now=f[now][j];}}cout<<ans+1<<endl;}
}
int main(){ios::sync_with_stdio(false);cin.tie(),cout.tie();int t=1;
//	cin>>t;while(t--){sove();}return 0;
}

相关文章:

B. 攻防演练 (2021CCPC女生赛)

题意&#xff1a; 给出一个长度为n的字符&#xff0c;字符是前m个小写字母&#xff0c;有q个询问&#xff0c;每次询问一个最短子序列的长度满足不是[l,r]内任意一个子序列 思路&#xff1a; [l,r]中子序列可以看成是从[l,r]中的某个位置开始&#xff0c;跳到下一个字符的位…...

MAC环境,在IDEA执行报错java: -source 1.5 中不支持 diamond 运算符

Error:(41, 51) java: -source 1.5 中不支持 diamond 运算符 (请使用 -source 7 或更高版本以启用 diamond 运算符) 进入设置 修改java版本 pom文件中加入 <plugin><groupId>org.apache.maven.plugins</groupId><artifactId>maven-compiler-plugin&l…...

Tomcat日志中文乱码

修改安装目录下的日志配置 D:\ProgramFiles\apache-tomcat-9.0.78\conf\logging.properties java.util.logging.ConsoleHandler.encoding GBK...

最小生成树 — Prim算法

同Kruskal算法一样&#xff0c;Prim算法也是最小生成树的算法&#xff0c;但与Kruskal算法有较大的差别。 Prim算法整体是通过“解锁” “选中”的方式&#xff0c;点 -> 边 -> 点 -> 边。 因为是最小生成树&#xff0c;所以针对的也是无向图&#xff0c;所以可以随意…...

如何使用PHP Smarty模板进行AJAX交互?

首先&#xff0c;我们要明白&#xff0c;AJAX是一种在无需刷新整个页面的情况下&#xff0c;与服务器进行通信的技术。这对于改善用户体验来说&#xff0c;是个大宝贝。而PHP Smarty模板则是PHP的一种模板引擎&#xff0c;它使得设计和开发人员能够更好地分离逻辑和显示。 现在…...

nginx反向代理、负载均衡

修改nginx.conf的配置 upstream nginx_boot{# 30s内检查心跳发送两次包&#xff0c;未回复就代表该机器宕机&#xff0c;请求分发权重比为1:2server 192.168.87.143 weight100 max_fails2 fail_timeout30s; server 192.168.87.1 weight200 max_fails2 fail_timeout30s;# 这里的…...

React Native文本添加下划线

import { StyleSheet } from react-nativeconst styles StyleSheet.create({mExchangeCopyText: {fontWeight: bold, color: #1677ff, textDecorationLine: underline} })export default styles...

微服务-Nacos(配置管理)

配置更改热更新 在Nacos中添加配置信息&#xff1a; 在弹出表单中填写配置信息&#xff1a; 配置获取的步骤如下&#xff1a; 1.引入Nacos的配置管理客户端依赖&#xff08;A、B服务&#xff09;&#xff1a; <!--nacos的配置管理依赖--><dependency><groupId&…...

UML图绘制 -- 类图

1.类图的画法 类 整体是个矩形&#xff0c;第一层类名&#xff0c;第二层属性&#xff0c;第三层方法。 &#xff1a;public- : private# : protected空格: 默认的default 对应的类写法。 public class Student {public String name;public Integer age;protected I…...

SAP ME2L/ME2M/ME3M报表增强添加字段(包含:LMEREPI02、SE18:ES_BADI_ME_REPORTING)

ME2L、ME2M、ME3M这三个报表的字段增强&#xff0c;核心点都在同一个结构里 SE11:MEREP_OUTTAB_PURCHDOC 在这里加字段&#xff0c;如果要加的字段是EKKO、EKPO里的数据&#xff0c;直接加进去&#xff0c;啥都不用做&#xff0c;就完成了 如果要加的字段不在EKKO和EKPO这两个…...

探讨uniapp的数据缓存问题

异步就是不管保没保存成功&#xff0c;程序都会继续往下执行。同步是等保存成功了&#xff0c;才会执行下面的代码。使用异步&#xff0c;性能会更好&#xff1b;而使用同步&#xff0c;数据会更安全。 1 uni.setStorage(OBJECT) 将数据存储在本地缓存中指定的 key 中&#x…...

服务的拆分

纵向拆分 是从业务维度进行拆分。标准是按照业务的关联程度来决定&#xff0c;关联比较密切的业务适合拆分为一个微服务&#xff0c;而功能相对比较独立的业务适合单独拆分为一个微服务。 以社交App为例&#xff0c;你可以认为首页信息流是一个服务&#xff0c;评论是一个服务…...

Uniapp Syntax Error: Error: Unbalanced delimiter found in string

报错 in ./src/pages/user/components/tasks.vue?vue&typescript&langjs&Syntax Error: Error: Unbalanced delimiter found in string...这边导致文件的原因&#xff1a;可能是条件编译语法不小心删了某个字符&#xff0c;导致不全&#xff0c;无法形成一对。 //…...

视频集中存储EasyCVR视频汇聚平台定制项目增加AI智能算法

安防视频集中存储EasyCVR视频汇聚平台&#xff0c;可支持海量视频的轻量化接入与汇聚管理。平台能提供视频存储磁盘阵列、视频监控直播、视频轮播、视频录像、云存储、回放与检索、智能告警、服务器集群、语音对讲、云台控制、电子地图、平台级联、H.265自动转码等功能。为了便…...

确保Django项目的稳定运行和持续改进

确保Django项目的稳定运行和持续改进 引言 Django是一个强大的Python Web框架&#xff0c;用于构建高效、可靠的Web应用程序。然而&#xff0c;部署一个Django项目并不意味着工作已经完成。在项目上线之后&#xff0c;确保项目的稳定运行并不断进行改进是非常重要的。本博客将…...

HAProxy负载均衡 代理

1.安装 yum -y install haproxy 2.配置文件 /etc/haproxy 下 global log 127.0.0.1 local2 #日志定义级别 chroot /var/lib/haproxy #当前工作目录 pidfile /var/run/haproxy.pid #进程id maxconn 4000 #最大连接…...

前端面试的游览器部分(8)每天10个小知识点

目录 系列文章目录前端面试的游览器部分&#xff08;1&#xff09;每天10个小知识点前端面试的游览器部分&#xff08;2&#xff09;每天10个小知识点前端面试的游览器部分&#xff08;3&#xff09;每天10个小知识点前端面试的游览器部分&#xff08;4&#xff09;每天10个小知…...

【【verilog典型电路设计之流水线结构】】

verilog典型电路设计之流水线结构 下图是一个4位的乘法器结构&#xff0c;用verilog HDL 设计一个两级流水线加法器树4位乘法器 对于流水线结构 其实需要做的是在每级之间增加一个暂存的数据用来存储 我们得到的东西 我们一般来说会通过在每一级之间插入D触发器来保证数据的联…...

大数据课程K2——Spark的RDD弹性分布式数据集

文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 了解Spark的RDD结构; ⚪ 掌握Spark的RDD操作方法; ⚪ 掌握Spark的RDD常用变换方法、常用执行方法; 一、Spark最核心的数据结构——RDD弹性分布式数据集 1. 概述 初学Spark时,把RDD看…...

Seaborn数据可视化(一)

目录 1.seaborn简介 2.Seaborn绘图风格设置 21.参数说明&#xff1a; 2.2 示例&#xff1a; 1.seaborn简介 Seaborn是一个用于数据可视化的Python库&#xff0c;它是建立在Matplotlib之上的高级绘图库。Seaborn的目标是使绘图任务变得简单&#xff0c;同时产生美观且具有信…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

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

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

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

如何做好一份技术文档?从规划到实践的完整指南

如何做好一份技术文档&#xff1f;从规划到实践的完整指南 &#x1f31f; 嗨&#xff0c;我是IRpickstars&#xff01; &#x1f30c; 总有一行代码&#xff0c;能点亮万千星辰。 &#x1f50d; 在技术的宇宙中&#xff0c;我愿做永不停歇的探索者。 ✨ 用代码丈量世界&…...

el-amap-bezier-curve运用及线弧度设置

文章目录 简介示例线弧度属性主要弧度相关属性其他相关样式属性完整示例链接简介 ‌el-amap-bezier-curve 是 Vue-Amap 组件库中的一个组件,用于在 高德地图 上绘制贝塞尔曲线。‌ 基本用法属性path定义曲线的路径,可以是多个弧线段的组合。stroke-weight线条的宽度。stroke…...

MySQL基本操作(续)

第3章&#xff1a;MySQL基本操作&#xff08;续&#xff09; 3.3 表操作 表是关系型数据库中存储数据的基本结构&#xff0c;由行和列组成。在MySQL中&#xff0c;表操作包括创建表、查看表结构、修改表和删除表等。本节将详细介绍这些操作。 3.3.1 创建表 在MySQL中&#…...