CF700E Cool Slogans
2021/12/23 23:15:55
本文主要是介绍CF700E Cool Slogans,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
首先可以发现选出的字符串序列一定可以调整成 \(s_i\) 为 \(s_{i + 1}\) 的一段后缀。
注意到这本质上是一个关于子串选择,与子串出现位置有关的问题,于是考虑借助 \(\rm endpos\) 来解决。
那么这个问题本质上就是选择后缀自动机 \(\rm parent\) 树上一条合法的祖先链。
由于 \(\rm endpos\) 集是一个整体,为了优化复杂度我们最好能找到本题当中一个 \(\rm endpos\) 集整体满足的性质:
- 相同 \(\rm endpos\) 集内的字符串不能同时选入字符串序列。
即 \(\rm endpos\) 集内字符串两两之间不会包含两次。
反证法:若包含两次根据 \(\rm endpos\) 集的性质,这两个字符串可以无限往前延伸,矛盾。
- 假设 \(v\) 是 \(u\) 在 \(\rm parent\) 树上的祖先,\(\mathrm{longest}(u)\) 为 \(u\) 节点的最长串,则 \(v\) 内所有节点在 \(\mathrm{longest}(u)\) 内出现次数相同。
首先显然 \(v\) 内节点在 \(\mathrm{longest}(u)\) 内出现次数按照长度不增。
反证法:假设对于 \(a, b \in v, b = sa\),有 \(a\) 与 \(b\) 在 \(s\) 内出现次数不同,那么显然只有 \(s\) 会在 \(\mathrm{longest}(u)\) 的外面。
假设将 \(\mathrm{longest}(u)\) 往左延长知道恰好使得 \(b\) 与 \(a\) 出现次数相同的串为 \(t\),根据 \(\rm endpos\) 集的性质 \(\mathrm{endpos}(\mathrm{longest}(u)) \subseteq \mathrm{endpos}(t) \Rightarrow \mathrm{endpos}(\mathrm{longest}(u)) = \mathrm{endpos}(t)\) 可知 \(t \in u\) 而 \(|t| > |\mathrm{longest}(u)|\) 矛盾。
令 \(f_s\) 为以 \(s\) 这个子串作为选出序列的结尾的最大长度,那么可知同一等价类内按照串长 \(f\) 递增(性质三)。
我们只关心最后每个等价类 \(u\) 中 \(f_{\mathrm{longest}(u)}\) 的取值,根据性质一二,转移显然只需要枚举祖先 \(v\) 中所有节点的 \(f_{\mathrm{longest}(v)}\) 查看 \(\mathrm{longest}(v)\) 是否在 \(\mathrm{longest}(u)\) 中出现两次即可,这个可以用线段树合并维护 \(\rm endpos\) 集,直接在线段树上查询 \(\mathrm{longest}(v)\) 在某区间是否出现即可。
这样状态数优化到了线性,但转移复杂度仍然是不能接受的,考虑优化。
注意到每次可以转移的区间一定是一段后缀,根据性质三可以找到第一个可以转移的节点,这里可以使用倍增,复杂度 \(\mathcal{O}(n \log ^ 2n)\).
还可以继续优化,发现我们只关心 \(v\) 往上第一个遇到的极长的 \(f\) 相等的区间内的转移,因为根据性质三 \(f_v\) 至少内取到这个值。
于是只需要记录极长区间的顶部位置即可,这样只需要判定一次,复杂度 \(\mathcal{O}(n \log n)\).
这篇关于CF700E Cool Slogans的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升