【JZOJ4964】【GDKOI2017模拟1.21】Rhyme
2024-09-03 05:55:10
hafy
由于多次交换邮票没有满足所有人的需求,小Z被赶出了集邮部。无处可去的小Z决定加入音乐部,为了让音乐部的人注意到自己的才华,小Z想写一首曲子。为了让自己的曲子更好听,小Z找到了一些好听曲子作为模板。曲谱可以表示成只包含小写字母的字符串,小Z希望自己最终的曲谱中任意一个长度为K的子串都是一个模板的子串。现在小Z想知道自己的曲谱最长可以是多长,如果可以无限长的话请输出INF。
forget
对于30%的数据:K=2。
对于70%的数据:每组数据字符串总长不超过1000。
对于100%的数据:每组数据字符串总长不超过100000,1≤K≤100000。每个测试点数据不超过10组。
anfa
刨根问底:
这道题究竟在求些什么?
在即将要求的曲谱中,我们希望它的所有长度为k子串都必须是一个模板的子串。
出于我必须明白这个曲谱究竟会有什么样的性质这个目的,我倒过来思考。
曲谱它的每个长度为k的子串都并非独立而言的;
对于一个长度为k−1的子串,如果能够后接字符,就等同于在某个包含这个子串的模板中的后接字符。
如果我要解题,肯定是在这个特殊之处做手脚。
这个特殊之处给我们什么启发呢?
挖掘:
1.要维护的子串数量较少;
2.可以建立DAG来映射。
这样就好做了,一个哈希套上去就是了。
最新文章
- c#操作MangoDB 之MangoDB CSharp Driver驱动详解
- 使用vlc进行二次开发做自己的播放器
- 在react native用到的javascript 的一些关键知识(整理中)
- VSO-Branch和Merge
- With语句以及@contextmanager的语法解析
- Buffer篇
- CMWAP CMWAP是手机上网使用的接入点的名称
- php Memcache
- COM学习(三)——数据类型
- 使用aespython进行ECB加解密示例
- poj1797 - Heavy Transportation(最大边,最短路变形spfa)
- find系列之xargs命令
- 通过线程监控socket服务器是否done机
- 201521123108 《Java程序设计》第11周学习总结
- String、StringBuilder和StringBuffer
- python 基础语法练习回顾
- 数组去重--ES5和ES6
- yum -y install php-mysql 版本冲突
- Maven教程(3)--Maven导入工程常见问题(编码、MavenArchiver、Lifecycle Mapping、maven install 没有反应)
- linux下usb转串口驱动分析【转】
热门文章
- tp5异常全局返回处理
- 如何使用Tunnel SDK上传/下载MaxCompute复杂类型数据
- JavaSE_08_Collections常用功能
- 在三维场景中加载shp(skyline)
- SQLServer-SQLServer2017:安装 SQL Server 的硬件和软件要求
- 关于mybatis-config.xml文件的基础解释
- $(...).live is not function
- webServices学习一(了解基础和作用。)
- std::map插入失败会返回什么
- Latex报错: Could not start the command: xelatex.exe -synctex=1 -interaction=nonstopmode?