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"…...

基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...

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

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...

mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...

Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...
解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist
现象: android studio报错: [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决: 不要动CMakeLists.…...