首页 > 其他分享 >【JZOJ7839】神秘代码

【JZOJ7839】神秘代码

时间:2023-08-17 22:44:06浏览次数:62  
标签:神秘 Part 代码 JZOJ7839 height hi 字符串 SA

image
凯尔希我谢谢你
lcp的题所以考虑使用 $ S A $ 或者 $ SAM $
此处使用大佬提供的 $ SA $ 思路

Part I

首先我们考虑不反转怎么做
这其实是一道SA板子题
我们将所有的字符串全部用特殊符号隔开变成一个字符串
然后把每个点的 $ height $ 数组跑出来
对于每一个点的 $ height $ 值我们独立算贡献
怎么算?
前置芝士1 : 将 $ height $ 按照 $ SA $ 跑出来的排名排序,对于任意两个后缀 $ i $ 和 $ j $,它们的 $ LCP $ 即为

\[ \min_{k=i+1}^j hi_k \]

所以我们就可以对于每一个 $ hi_i $ ,运用二分加 $ ST $ 表的思想,找出最左&最右边的 $ hi_j \ge $ 自己的位置
统计数量再乘上 $ hi_i $即可~

Part II

接下来我们考虑加上反转这个限制

标签:神秘,Part,代码,JZOJ7839,height,hi,字符串,SA
From: https://www.cnblogs.com/2020ljh/p/17639100.html

相关文章

  • 订单统计_代码开发
             ......
  • 路径规划算法:基于郊狼算法的机器人路径规划算法- 附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • python 中如何快速查看代码的性能 DebugInfo 秒表装饰器
    背景我们在python编程时,在有性能优化需求的场景下,我们可能一个需求存在多个解决方案的情况,这些解决方案可能在不同的模块/库中实现。那么对于可以实现两样的功能,但实现方式不同的情况下,我们直接测试一下每个方式的运行性能,是最直观评估不同的实现方案性能的办法。一般解决方法......
  • 异步代码微任务宏任务案例
    案例一案例01process.nextTick(()=>{console.log("111");})constpromise=newPromise(resolve=>{console.log("222");resolve()})setTimeout(()=>{console.log("333");},100)promise.then(()=>{console.log(&quo......
  • 黑魂233 导演动画和代码联动
    给Director物体新建一个脚本,TesterDirector 然后将Director插件放进pd变量里: 在代码里添加导演动画激活的按钮:只要按下T键,就会执行。前提是得先把PlayOnWake消钩。 然后再添加这几个代码,让导演动画可以重复播放: ......
  • [代码随想录]Day20-二叉树part09
    题目:669.修剪二叉搜索树思路:遍历到的值小于最小值,说明左子树里的所有节点都小于最小值,舍弃左子树。遍历到的值大于最大值,说明右子树里的所有节点都大于最大值,舍弃右子树。如果在范围内,就拼接左右子树然后返回节点代码:/***Definitionforabinarytreenode.*typeTr......
  • 用户统计_代码开发
           ......
  • 必备Python代码
    Python是机器学习最广泛采用的编程语言,它最重要的优势在于编程的易用性。如果读者对基本的Python语法已经有一些了解,那么这篇文章可能会给你一些启发。1.重复元素判定以下方法可以检查给定列表是不是存在重复元素,它会使用set()函数来移除所有重复元素。defall_unique(lst):......
  • 静态代码测试工具HelixQAC新版对MISRA C规则提供100%覆盖率
    HelixQAC 2023.2中的新增功能HelixQAC2023.2对MISRAC:2012和MISRAC:2023规则提供了100%的覆盖率,并更新了相应的合规性模块以适用于MISRAC:2023。此外,此版本还包括改进的C23语言支持、对Validate平台的改进和HelixQAC和Validate的集成,以及其他质量增强功能。......
  • 你能发现这段 Python 代码中的 bug 吗?
    点击链接了解详情【CSDN编者按】大家一起来找Bug。原文链接:https://dwrodri.gitlab.io/can-you-spot-the-bug-in-this-python-code/本文已获作者授权,未经允许,禁止转载!作者|DerekRodriguez译者|弯月责编|夏萌出品|CSDN(ID:CSDNnews)最近,在解析文本时,我遇到了一个......