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

NOIP2023模拟19联测40 诡异键盘

题目大意

有一个键盘,上面有 n + 1 n+1 n+1个按键,按下按键 1 ≤ i ≤ n 1\leq i\leq n 1in会打印出字符串 S i S_i Si,按下按键 n + 1 n+1 n+1会删掉结尾的 K K K个字符,如果不足 K K K个字符则全部删完,问打印出 S S S最少要按多少次。

T T T组数据。

1 ≤ T ≤ 100 , 10 ≤ n ≤ 5 × 1 0 3 , 1 ≤ ∑ K ≤ 2 × 1 0 3 1\leq T\leq 100,10\leq n\leq 5\times 10^3,1\leq \sum K\leq 2\times 10^3 1T100,10n5×103,1K2×103

1 ≤ ∑ ( ∑ ∣ S i ∣ ) ≤ 1 0 6 , 1 ≤ ∑ ∣ S ∣ ≤ 5 × 1 0 3 1\leq \sum(\sum|S_i|)\leq 10^6,1\leq \sum |S|\leq 5\times 10^3 1(Si)106,1S5×103

时间限制 2000 m s 2000ms 2000ms,空间限制 512 M B 512MB 512MB


题解

考虑 D P DP DP,设 f i f_i fi表示打出前 i i i个字符需要的最小操作次数。那我们要求的就是打出 S S S的第 i i i个字符到第 j j j个字符需要的最小操作次数。

先考虑如何得到 S S S [ i , j ] [i,j] [i,j]这一段。我们选择一个前 j − i + 1 j-i+1 ji+1个字符与 S S S [ i , j ] [i,j] [i,j]中的字符相同的 S p S_p Sp,然后将 S p S_p Sp打出并删到只剩下 S S S [ i , j ] [i,j] [i,j]这部分即可。我们可以建一棵字典树,每次加入一个 S i S_i Si时更新从根节点到达路径上每个点的最小操作次数。为了求这里的最小操作次数,我们还需要求出删除若干个字符所需要的最小操作次数,这个可以用一个类似“同余”的最短路来求出,用 dijkstra \text{dijkstra} dijkstra可以 O ( K 2 ) O(K^2) O(K2)解决(连边是 O ( k 2 ) O(k^2) O(k2)的,求最短路是 O ( K log ⁡ K ) O(K\log K) O(KlogK)的)。

得到了带到每个位置的最小操作次数之后,枚举每个 i i i,然后在字典树上按 S S S i i i往后枚举,设枚举到 j j j,则用 f i f_i fi来更新 f j f_j fj D P DP DP的时间复杂度为 O ( ∣ S ∣ 2 ) O(|S|^2) O(S2)

总时间复杂度为 O ( ∑ ( ∑ ∣ S i ∣ + ∣ S ∣ 2 + K 2 ) ) O(\sum(\sum |S_i|+|S|^2+K^2)) O((Si+S2+K2))

可以参考代码帮助理解。

code

#include<bits/stdc++.h>
using namespace std;
const int N=5000,M=1000000,K=2000;
int T,n,k,s1,now,bg[N+5],len[N+5],z[K+5],vs[K+5],cm[K+5];
int tot;
char s[N+5],t[M+5],ss[M+5];
long long dis[K+5],to[M+5],f[N+5];
struct node{int x;long long dis;bool operator<(const node ax)const{return dis>ax.dis;}
};
vector<pair<int,int>>g[K+5];
priority_queue<node>q;
struct trie{int a[26];
}w[M+5];
void pt(){int len=strlen(ss+1);for(int i=1;i<=len;i++){t[++now]=ss[i];}
}
void init(){for(int i=0;i<k;i++){z[i]=1e9;vs[i]=cm[i]=0;g[i].clear();}for(int i=1;i<=n;i++){len[i]=bg[i+1]-bg[i];z[len[i]%k]=min(z[len[i]%k],len[i]);vs[len[i]%k]=1;}for(int i=1;i<=n;i++){if(z[len[i]%k]!=len[i]) continue;if(!vs[len[i]%k]) continue;vs[len[i]%k]=0;for(int j=0;j<k;j++){g[(j+len[i])%k].push_back({j,1+(j+len[i])/k});}}for(int i=0;i<k;i++) dis[i]=1e16;dis[0]=dis[k]=0;q.push((node){0,0});while(!q.empty()){int u=q.top().x;q.pop();if(cm[u]) continue;cm[u]=1;for(auto p:g[u]){int v=p.first,w=p.second;if(dis[u]+w<dis[v]){dis[v]=dis[u]+w;q.push((node){v,dis[v]});}}}
}
void pt(int tw){int q,vq=1;for(int i=1;i<=len[tw];i++){q=t[bg[tw]+i-1]-'a';if(!w[vq].a[q]){w[vq].a[q]=++tot;to[tot]=1e16;}vq=w[vq].a[q];to[vq]=min(to[vq],1ll+(len[tw]-i)/k+dis[(len[tw]-i)%k]);}
}
void solve(int tw){int q,vq=1;for(int i=tw+1;i<=s1;i++){q=s[i]-'a';if(!w[vq].a[q]) return;vq=w[vq].a[q];f[i]=min(f[i],f[tw]+to[vq]);}
}
int main()
{
//	freopen("keyboard.in","r",stdin);
//	freopen("keyboard.out","w",stdout);scanf("%d",&T);while(T--){scanf("%d%d",&n,&k);now=0;for(int i=1;i<=n;i++){scanf("%s",ss+1);bg[i]=now+1;pt();}bg[n+1]=now+1;scanf("%s",s+1);s1=strlen(s+1);init();tot=1;for(int i=1;i<=n;i++) pt(i);for(int i=0;i<=s1;i++) f[i]=1e16;f[0]=0;for(int i=0;i<s1;i++) solve(i);if(f[s1]>=1e16) printf("-1\n");else printf("%lld\n",f[s1]);for(int i=1;i<=tot;i++){for(int j=0;j<26;j++) w[i].a[j]=0;}}return 0;
}

相关文章:

NOIP2023模拟19联测40 诡异键盘

题目大意 有一个键盘&#xff0c;上面有 n 1 n1 n1个按键&#xff0c;按下按键 1 ≤ i ≤ n 1\leq i\leq n 1≤i≤n会打印出字符串 S i S_i Si​&#xff0c;按下按键 n 1 n1 n1会删掉结尾的 K K K个字符&#xff0c;如果不足 K K K个字符则全部删完&#xff0c;问打印出 S …...

算法设计与分析 | 众数问题(c语言)

题目 所谓众数&#xff0c;就是对于给定的含有N个元素的多重集合&#xff0c;每个元素在S中出现次数最多的成为该元素的重数&#xff0c; 多重集合S重的重数最大的元素成为众数。例如&#xff1a;S{1,2,2,2,3,5}&#xff0c;则多重集S的众数是2&#xff0c;其重数为3。 现在你…...

sql server外键设置

SQL Server外键设置 简介 在关系型数据库中&#xff0c;外键是一种约束&#xff0c;用于确保数据的完整性和一致性。外键约束定义了一个表中的列与另一个表中的列之间的关系&#xff0c;它可以用来保证数据的一致性、防止数据的破坏和数据冗余。在SQL Server中&#xff0c;我们…...

R语言实现多变量孟德尔随机化分析(1)

多变量孟德尔随机化分析调整了潜在混杂因素的影响。 1、调整哪些因素&#xff1f;参考以往文献。可以分别调整&#xff0c;也可以一起调整。 2、解决了什么问题&#xff1f;某个暴露相关的SNP&#xff0c;往往与某个或者某几个混杂因素相关。可以控制混杂偏倚。 3、如何解释…...

搭建 AI 图像生成器 (SAAS) php laravel

今天来搭一套&#xff0c;AI 图像生成器 是基于 Openai DALLE 2 和 Openai DALLE 3 以及 Stability AI 和稳定扩散 API 构建的脚本&#xff0c;为用户提供了使用简单的提示和大小生成独特自定义图像的可能性。在这个平台上&#xff0c;创意得以快速、高效地实现&#xff0c;借助…...

Maven引用本地jar包

先上命令: ​ mvn install:install-file -Dfile..\.m2\repository\jl1.0.1.jar -DgroupId"com.liz.local" -DartifactId"jl" -Dversion"1.0.1" -Dpackagingjar​ 参数注释: -Dfile: jar 包路径&#xff08;建议放在 meven 的 repository&…...

一起学docker系列之五docker的常用命令--操作容器的命令

目录 前言1 启动容器2 查看容器3 退出容器4 启动已经停止的容器5 重启容器6 停止容器7 删除已经停止的容器8 启动容器说明和举例9 查看容器日志10 查看容器内运行的进程11 查看容器内部细节12 进入正在运行的容器并进行交互13 导入和导出容器结语 前言 当涉及到容器化技术&…...

WPF打开对话框选择文件、选择文件夹

在WPF中实现文件的打开和选择&#xff0c;可以通过使用Microsoft.Win32.OpenFileDialog类来完成。这是一个通用的对话框组件&#xff0c;允许用户在本地文件系统中浏览和选择文件。这个组件属于WPF的一部分&#xff0c;因此不需要引用额外的库。 以下是一个如何使用OpenFileDi…...

nginx学习(3)

Nginx 负载均衡 实战案例 实现效果 浏览器地址栏输入地址 http://172.31.0.99/oa/a.html&#xff0c;负载均衡效果&#xff0c;平均 8083 和 8084 端口中 一、配置 1、先创建2个文件夹&#xff0c;并将apache-tomcat-8.5.87解压到tomcat8083和tomcat8084中 &#xff08;或…...

【系统架构设计】计算机公共基础知识: 4 数据库系统

目录 一 数据库模式 二 分布式数据库 三 索引和视图 四 数据库设计 五 关系代数...

主键问题以及分布式 id

分布式 id 需要处理的问题主要是同一时间在多台机器中保证生成的 id 唯一&#xff0c;为了这么做我们可以这么做&#xff1a; 分布式 id 生成策略 先说几个已经被淘汰的策略引出分布式 id 的问题 1&#xff0c;UUID&#xff1a;UUID 随机并且唯一&#xff0c;在单一的数据库…...

ReentranReadWriteLock 使用案例

ReentranReadWriteLock使用案例 /*** ReentranReadWriteLock 使用案例* 读线程共享* 写线程互斥*/ public class ReentrantReadWriteLockExample {private String news;private ReentrantReadWriteLock lock new ReentrantReadWriteLock();public String readNews() {lock.re…...

“我们把最扎心的话,说给了自己最亲近的人” 何解?| IDCF

引子 我们把最好的一面给了陌生人&#xff0c;却把最扎心的话&#xff0c;说给了自己最亲近的人。 我们往往会对关心自己的人发脾气&#xff0c;很多时候意图是好的&#xff0c;表达方式却简单粗暴&#xff0c;结果自然不必多言。你认为自己给的是反馈和建议&#xff0c;对方…...

MongoDB之索引和聚合

文章目录 一、索引1、说明2、原理3、相关操作3.1、创建索引3.2、查看集合索引3.3、查看集合索引大小3.4、删除集合所有索引&#xff08;不包含_id索引&#xff09;3.5、删除集合指定索引 4、复合索引 二、聚合1、说明2、使用 总结 一、索引 1、说明 索引通常能够极大的提高查…...

【GEE】基于GEE进行非监督学习

1 简介与摘要 之前写了多季节叠加的监督学习&#xff0c;所以这次简单写一个非监督学习吧。。 这次为了简单明了&#xff0c;就不整那么多虚的了&#xff0c;在这里我不叠图层了&#xff0c;有需要的可以参考前一篇博客自己添加输入的图层。 2 制作输入影像 首先&#xff0c…...

多视图聚类的论文阅读(一)

当聚类的方式使用的是某一类预定义好的相似性度量时&#xff0c; 会出现如下情况&#xff1a; 数据聚类方面取得了成功&#xff0c;但它们通常依赖于预定义的相似性度量&#xff0c;而这些度量受原始方法的影响:当输入维数相对较高时&#xff0c;往往是无效的。 1. Deep Mult…...

K-Means算法进行分类

已知数据集D中有9个数据点&#xff0c;分别是&#xff08;1,2&#xff09;&#xff0c;(2,3), (2,1), (3,1),(2,4),(3,5),(4,3),(1,5),(4,2)。采用K-Means算法进行聚类&#xff0c;k2&#xff0c;设初始中心点为&#xff08;1.1,2.2&#xff09;&#xff0c;&#xff08;2.3,3.…...

深度学习交通车辆流量分析 - 目标检测与跟踪 - python opencv 计算机竞赛

文章目录 0 前言1 课题背景2 实现效果3 DeepSORT车辆跟踪3.1 Deep SORT多目标跟踪算法3.2 算法流程 4 YOLOV5算法4.1 网络架构图4.2 输入端4.3 基准网络4.4 Neck网络4.5 Head输出层 5 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; *…...

网络协议入门 笔记一

一、服务器和客户端及java的概念 JVM (Java Virtual Machine) : Java虚拟机&#xff0c;Java的跨平台:一次编译&#xff0c;到处运行&#xff0c;编译生成跟平台无关的字节码文件 (class文件)&#xff0c;由对应平台的JVM解析字节码为机器指令 (010101)。 如下图所示&#xff0…...

系列十一、你平时工作用过的JVM常用基本配置参数有哪些?

一、常用参数 1.1、-Xms 功能&#xff1a;初始内存大小&#xff0c;默认为物理内存的1/64&#xff0c;等价于 -XX:InitialHeapSize 1.2、-Xmx 功能&#xff1a;最大分配内存&#xff0c;默认为物理内存的1/4&#xff0c;等价于 -XX:MaxHeapSize 1.3、-Xss 功能&#xff1a;设置…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

大模型——基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程

基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程 下载安装Docker Docker官网:https://www.docker.com/ 自定义Docker安装路径 Docker默认安装在C盘,大小大概2.9G,做这行最忌讳的就是安装软件全装C盘,所以我调整了下安装路径。 新建安装目录:E:\MyS…...

SQL进阶之旅 Day 22:批处理与游标优化

【SQL进阶之旅 Day 22】批处理与游标优化 文章简述&#xff08;300字左右&#xff09; 在数据库开发中&#xff0c;面对大量数据的处理任务时&#xff0c;单条SQL语句往往无法满足性能需求。本篇文章聚焦“批处理与游标优化”&#xff0c;深入探讨如何通过批量操作和游标技术提…...

mcts蒙特卡洛模拟树思想

您这个观察非常敏锐&#xff0c;而且在很大程度上是正确的&#xff01;您已经洞察到了MCTS算法在不同阶段的两种不同行为模式。我们来把这个关系理得更清楚一些&#xff0c;您的理解其实离真相只有一步之遥。 您说的“select是在二次选择的时候起作用”&#xff0c;这个观察非…...

第14节 Node.js 全局对象

JavaScript 中有一个特殊的对象&#xff0c;称为全局对象&#xff08;Global Object&#xff09;&#xff0c;它及其所有属性都可以在程序的任何地方访问&#xff0c;即全局变量。 在浏览器 JavaScript 中&#xff0c;通常 window 是全局对象&#xff0c; 而 Node.js 中的全局…...