CSP模拟53联测15 D. 子序列
CSP模拟53联测15 D. 子序列
文章目录
- CSP模拟53联测15 D. 子序列
- 题目大意
- 思路
- code
题目大意
(seq / 3s / 512 MiB)
给定一个长为 n n n 的仅有小写英文字母构成字符串 S = S 1 S 2 ⋯ S n S=S_1S_2\cdots S_n S=S1S2⋯Sn。我们定义一个字符串是好的,当且仅当它可以用两个不同的字母 x
和 y
表示成 xyxyxyx...
的形式。例如,字符串 abab
、tot
、z
是好的,但字符串 abc
、aa
不是好的。
现在有 q q q 组询问,每次给定 1 ≤ l ≤ r ≤ n 1 \le l \le r \le n 1≤l≤r≤n,你想要求出,对于串 S S S 的子串 S [ l ⋯ r ] S[l \cdots r] S[l⋯r],它最长的一个好的子序列的长度是多少,以及它可以被哪两个不同字符 x
和 y
来表示。如果有多个最长的串,则输出字典序最小的一个串的 x
与 y
。
思路
观察时限发现大概是 O ( 26 n ) O(26n) O(26n) 的做法
我们预处理两个数组 p r e v i , n e x t i prev_i , next_i previ,nexti 分别表示第 i i i 为的上一个、下一个字符 j j j 在什么位置。
再维护 a n s i , j ans_{i , j} ansi,j 表示 i → n i\to n i→n 里类似于 s [ i ] , j s[i] , j s[i],j 这样的排列的数量
考虑这个怎么维护。
从后往前枚举 i i i 和字符 j j j ,用 n e x t i , j next_{i , j} nexti,j 转移就好了
对于每个询问 l , r {l , r} l,r ,直接从小到枚举答案,用类似前缀和的方法求答案就好了。
前缀和的时候要考虑是否最后的那组字符都在区间内。
注意判断一下有没有多出来一个字符的情况。
code
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
using namespace std;
const int N = 1500005;
int n , lst[27] , pre[N][27] , nxt[N][27] , ans[N][27] , l , r;
char s[N] , c1 , c2;
int main () {freopen ("seq.in" , "r" , stdin);freopen ("seq.out" , "w" , stdout);scanf ("%s" , s + 1);n = strlen (s + 1);fu (i , 1 , n) {lst[s[i] - 'a' + 1] = i;fu (j , 1 , 26) pre[i][j] = lst[j]; }fu (i , 1 , 26) lst[i] = 0;fd (i , n , 1) {lst[s[i] - 'a' + 1] = i;fu (j , 1 , 26) nxt[i][j] = lst[j];}int now , k;fd (i , n , 1) {now = s[i] - 'a' + 1;fu (j , 1 , 26) {if (now == j) continue;k = nxt[i][j];if (k) ans[i][j] = 2 + ans[nxt[k][now]][j];else ans[i][j] = 1;}}int ans1 , ans2 , T , p , x , y;scanf ("%d" , &T);while (T --) {ans2 = 0;scanf ("%d%d" , &l , &r);fu (i , 1 , 26) {fu (j , 1 , 26) {if (i == j) continue;p = nxt[l][i];if (p > r) continue;x = pre[r][i] , y = pre[r][j];if (x > y) ans1 = ans[p][j] - ans[x][j] + 1;elseans1 = ans[p][j] - ans[nxt[r][i]][j];if (ans2 < ans1) {ans2 = ans1;c1 = i + 'a' - 1;c2 = j + 'a' - 1;}}}printf ("%d %c%c\n" , ans2 , c1 , c2);}return 0;
}
相关文章:
CSP模拟53联测15 D. 子序列
CSP模拟53联测15 D. 子序列 文章目录 CSP模拟53联测15 D. 子序列题目大意思路code 题目大意 (seq / 3s / 512 MiB) 给定一个长为 n n n 的仅有小写英文字母构成字符串 S S 1 S 2 ⋯ S n SS_1S_2\cdots S_n SS1S2⋯Sn。我们定义一个字符串是好…...
iceberg-flink 十一:在dlink代码中建表增加catalog地址。
一:catalog 是存储元数据的地方。 二:表中增加catalog地址’ 当我们映射iceberg表的时候,增加了地址,就会成功映射到表 CREATE CATALOG dk_empower WITH(typeiceberg,catalog-typehadoop,warehousehdfs://cluster/iceberg/war…...

多列等高实现
预期效果 多列等高,左右两列高度自适应且一样,分别设置不同背景色效果预览: 分别由6种方法实现 1、使用padding + margin + overflow 实现多列等高效果,具有良好的兼容性; 2、border实现多列等高,左边框宽度为200px,左列浮动,伪元素清除浮动; 3、父元素线性渐变背景色…...
2023 泰山杯 --- Crypto wp
文章目录 题目解题过程part1part2part3 解题代码 题目 from fastecdsa.curve import P521 as Curve from fastecdsa.point import Point from os import urandom from random import getrandbits import uuid from Crypto.PublicKey import DSA from Crypto.Util.number impor…...

蓝桥杯每日一题20233.10.10
题目描述 回文日期 - 蓝桥云课 (lanqiao.cn) 题目分析 对于此题,我们最先想到的是暴力解法,将每一种情况经行循环查找,在查找的过程中记录下答案,回文日期就是字符串判断回文,ABABBABA型回文日期可以将回文经行特判…...
366. 寻找⼆叉树的叶⼦节点
366. 寻找⼆叉树的叶⼦节点 这道题混用二叉树递归 「遍历」和「分解问题」 两种思维模式。 class FindLeaves:"""366. 寻找⼆叉树的叶⼦节点https://leetcode.cn/problems/find-leaves-of-binary-tree/"""def solution(self, root):self.res …...

python - excel 设置样式
文章目录 前言python - excel 设置样式1. 准备2. 示例2.1. 给单元格设置样式"等线"、大小为24磅、斜体、红色颜色和粗体2.2. 给第二行设置样式"宋体"、大小为16磅、斜体、红色颜色和粗体2.3. 给第三行数据设置垂直居中和水平居中2.4. 给第四行设置行高为30…...
Gemmini测试test文件chisel源码详解(一)
DMACommandTrackerTest.scala 源码如下: package gemminiimport scala.collection.mutable.ArrayBufferimport chisel3._ import chisel3.iotesters.{ChiselFlatSpec, PeekPokeTester}class DMACommandTrackerTester(c: DMAReadCommandTracker[UInt]) extends Pee…...
RabbitMQ中的手动应答和自动应答
当使用RabbitMQ来处理消息时,消息确认是一个重要的概念。RabbitMQ提供了两种不同的消息确认方式:自动应答(Automatic Acknowledgment)和手动应答(Manual Acknowledgment)。这两种方式适用于不同的应用场景&…...

【C语言】文件的操作与文件函数的使用(详细讲解)
前言:我们在学习C语言的时候会发现在编写一个程序的时候,数据是存在内存当中的,而当我们退出这个程序的时候会发现这个数据不复存在了,因此我们可以通过文件把数据记录下来,使用文件我们可以将数据直接存放在电脑的硬盘…...

ROS-PX4仿真笔记_1
offbord模式测试 rosrun offboard_pkg position stablelize模式 lqr控制器实验 roslaunch px4 fast_test.launch 无人机起飞1.5-2m sh mybot_gazebo.sh#roslaunch px4 fast_racing.launch & sleep 20; roslaunch ego_planner single_run_in_gazebo.launch & sleep 1…...
使用 Python 中的小波变换信号驾驭股票价格的波动
一、简介 股票上涨和下跌,创造出像海浪一样难以预测的模式和走势。然而,就像科学家通过了解下面的水流来预测波浪的运动一样,我们也可以使用类似的工具破译股票市场的一些模式。 通过利用小波变换的力量,我们深入表面,试图揭示驱动股价的深层原因。这段旅程不仅仅涉及数字…...

AndroidStudio模拟器,没有Google Play的就有ROOT权限
正确选择版本 测试 D:\>adb shell emulator64_x86_64:/ $ su emulator64_x86_64:/ #...
复选框 前端代码
表单中复选框选项 <el-form-item label="是否公开:" hidden="true"><input type="checkbox...
每日一练 | 网络工程师软考真题Day41
1、包过滤防火墙对通过防火墙的数据包进行检查,只有满足条件的数据包才能通过,对数据包的检查内容一般不包括 。 A.源地址 B.目的地址 C.协议 D.有效载荷 2、下面关于ARP木马的描述中,错误的…...
vue使用pinia存储数据并保持数据持久化
在Vue中使用Pinia存储数据并保持数据持久化,你可以遵循以下步骤: 安装Pinia:首先,你需要安装Pinia。可以通过npm或yarn来安装它。在终端中运行以下命令: npm install pinia# 或者使用yarn yarn add pinia创建Pinia St…...

k8s - Flannel
1.Flannel概念剖析 Flannel是 CoreOS 团队针对 Kubernetes 设计的一个覆盖网络(Overlay Network)工具,其目的在于帮助每一个使用 Kuberentes 的 CoreOS 主机拥有一个完整的子网。这次的分享内容将从Flannel的介绍、工作原理及安装和配置三方…...

服务器中了balckhoues勒索病毒怎么办?勒索病毒解密,数据恢复
近日,云天数据恢复中心发现,有多位用户的服务器中了一种名为balckhoues的勒索病毒,因为绝大多数用户是第一次遇到这种情况,所以对这种类型的勒索病毒并不是很了解。那接下来我们将对balckhoues勒索病毒做一个分析。 中毒特征 服务…...
react-pdf | Warning: TextLayer styles not found.
问题描述: 使用react-pdf展示pdf,但是报警告,Warning: TextLayer styles not found. 解决方法: <Pageloading{"加载中..."}renderAnnotationLayer{false}renderTextLayer{false}/> 添加属性如上,设…...
vue上传文件MD5加密
1.下载MD5依赖 npm install crypto-js 2.在utils文件夹中新增文件md5方法文件,文件名自定义(fileMd5Sum.js) import CryptoJs from crypto-js export default {// md5值计算fileMd5Sum(file) {let CryptoJS require("crypto-js"…...

XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...

2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...

dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...

GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...