文档章节

[CF594E]Cutting the Line

o
 osc_zoa3moe9
发布于 2019/12/07 17:32
字数 1273
阅读 17
收藏 0

精选30+云产品,助力企业轻松上云!>>>

$\newcommand{qed}{\square}$字符串神题。

要点:Lyndon分解,扩展KMP, 最小循环表示,贪心。

题目链接

题意

已知字符串 $S$, 请你把它切成不超过 $k$ 段,并翻转其中若干段,使得最终字符串的字典序最小。

题解

先想一想如果 $k=|S|$, 即不限制切的段数怎么做。此时我们发现可以去掉“是否翻转”的决策,因为如果有一段不翻转,我们就把它拆成若干个单字符分别翻转。

我们的策略是:

策略1. 设反串 $S^r$ 的Lyndon分解为 $s_1, s_2, \ldots, s_n, t_1, t_2, \ldots, t_m$, 其中 $s_n \ne t_1=t_2=\cdots=t_m$. 每次取出 $t_1 t_2 \cdots t_m$ 对应的原串前缀 $S[:L]$ 作为第一段,余下的化归为关于 $S[L:], k-1$ 的问题。

证明 简化问题的操作等价于每次剪切出一个反串的后缀,按剪切的顺序先后从左到右连接。因此我们应该使最小后缀,即 $t_1$ 在开头出现尽可能多次。$S^r$ 可以写成 $A_1(c_1 \times t_1)A_2(c_2 \times t_1) \cdots A_t(c_t \times t_1)$ 的形式,$c_t=m$. 那么最优情况下应该使 $c_t+\max\{c_1+c_2+\cdots+c_{t-1}\}$ 个 $t_1$ 作为先导。为取到该最大值,最优策略应该先切出最后的 $m$ 个 $t_1$.

$\qed$

于是简化的问题得到解决。想一想原问题,我们仍然假设每一段都必须翻转,并加入修正规则:如果连续若干个段都是单字符,它们实际上只占据一段。

当 $k\ge3$ 时,策略1改进后也成立:

策略1-改. 设反串 $S^r$ 的Lyndon分解为 $s_1, s_2, \ldots, s_n, t_1, t_2, \ldots, t_m$, 其中 $s_n \ne t_1=t_2=\cdots=t_m$ 或者 $|s_n|>|t_1|=|t_2|=\cdots=|t_m|=1$. 每次取出 $t_1 t_2 \cdots t_m$ 对应的原串前缀 $S[:L]$ 作为第一段,余下的化归为关于 $S[L:], k-1$ 的问题。

证明 如果 $|t_1| \ge 2$, 由于 $k \ge 3$, 策略1的证明仍然有效。如果 $|t_1|=1$, 那么为了节省段数一定一并取出这些单字符。

$\qed$

先对 $k \ge 3$ 的情况反复应用策略1-改,所以现可不妨假设 $k \le 2$.

如果 $S^r$ 已经是Lyndon串,那么显然答案就是 $S^r$; 如果 $k=1$, 那么显然答案就是 $\min\{S, S^r\}$.

处理完上述两种情况,现在,字符串将被我们分为前后两部分,并按照这两部分是否翻转分为三大类操作,或者不操作直接留下 $S$.

(一)前一部分翻转,后一部分不翻转,设为 $S^r[L:]S[-L:]$.

设 $S^r$ 的Lyndon分解合并相等段后为 $S^r[:d_1], S^r[d_1:d_2], \ldots, S^r[d_{n-1}:d_n]$, 其中 $d_n=|S|$, 那么我们有结论:

性质1. 存在整数 $q \in [1, n]$ 使得 $L=d_q$ 为本情况的最优解之一。

证明 若 $L$ 不是Lyndon分解中两相邻字符串的分界点,那么取它之后的一个分界点作为 $L$ 更优;若 $L$ 是两相等字符串的分界点,分类讨论可发现此相等段的两端点中至少有一个是不会更劣的决策。

$\qed$

性质2. 如果设 $p$ 为最大的小于 $n$ 的正整数,满足 $S^r[d_p:]$ 不为 $S^r[d_{p+1}:]$ 的前缀,特别地,若不存在如此的正整数则设 $p=0$, 则 $q>p$.

证明 此命题等价于 $\forall q<i \le n$, $S^r[d_i:]$ 为 $S^r[d_q:]$ 的前缀。否则取 $d_i$ 更优。

$\qed$

性质3. $\forall p<i<n,$ $d_{i+1}-d_i>|S|-d_{i+1}$. 这表明枚举查找 $p$ 的时间为 $O(|S|)$.

证明 假设性质不成立,得 $S[d_i:]$ 有长度为 $d_{i+1}-d_i>{1\over2}(|S|-d_i)$ 的周期,矛盾。

$\qed$

性质4. 当 $p<m \le n$ 时,设 $T_m=S^r[d_m:]S[-d_m:]$, 若 $T_{m-1}>T_m$, 则 $\forall p<i<m, T_i>T_m$.

证明 $\because T_{m-1}>T_m$, $T_m[-d_{m-1}:]=T_{m-1}[-d_{m-1}:]$

$\therefore T_m[:-d_{m-1}]<T_{m-1}[:-d_{m-1}]=S^r[d_{m-1}:]=T_i[:-d_{m-1}]$

$\therefore T_m<T_i$.

$\qed$

因此只需要枚举找到最大的整数 $q$ 使得 $q=p+1$ 或 $S^r[d_q:]S[-d_q:]<S^r[d_{q-1}:]S[-d_{q-1}:]$, 后者等价于 $S[-d_{q-1}:-d_q]<S^r[d_{q-1}-d_q+|S|:]$, 因此直接比较的总时间也是 $O(|S|)$.

(二)前一部分不翻转,后一部分翻转,设为 $S[:L]S^r[:-L]$.

设 $i<j$, 比较 $S[:i]S^r[:-i]$ 与 $S[:j]S^r[:-j]$ 实际上相当于比较 $S^r[:-i]=S^r[:j-i]S^r[j-i:-i]$ 与 $S^r[i:j]S^r[:-j]$, 于是可以考虑用扩展 $KMP$ 算法求这两个串的最长公共前缀以比较大小。

(三)两部分都翻转,即 $S^r$ 的循环表示。求最小循环表示即可。

综上所述,本题可以在 $O(|S|)$ 时空内解决。

不知道有没有漏洞的实现链接

o
粉丝 1
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
每日一记 3分钟从编译后的代码里学 let 和 const 命令

新系列导读 学习编程语言是一件持之以恒的事情,从学会简单的语法就能写出程序,到理解类型和设计模式,再到考虑代码的组织架构。谁不是从这样一点点深入和积累的呢?入门总是轻松又令人愉悦...

罗小黑写写文字
2019/01/21
0
0
House Lawn Kattis - houselawn

Problem You have just bought a new house, and it has a huge, beautiful lawn. A lawn that needs cutting. Several times. Every week. The whole summer. After pushing the lawnmower ......

osc_8g11urw7
2018/10/17
6
0
A1132. Cut Integer

Cutting an integer means to cut a K digits lone integer Z into two integers of (K/2) digits long integers A and B. For example, after cutting Z = 167334, we have A = 167 and B =......

osc_e3nle85o
2018/08/29
2
0
Sticks(剪枝+BFS)

Problem Description George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state......

osc_bhmyqusc
2018/07/31
0
0
POJ-1011(Sticks)

Description George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he......

潘少online
2015/05/11
63
0

没有更多内容

加载失败,请刷新页面

加载更多

使用命名管道承载gRPC

最近GRPC很火,感觉整RPC不用GRPC都快跟不上时髦了。 gRPC设计 gRPC是一种与语言无关的高性能远程过程调用 (RPC) 框架。刚好需要使用一个的RPC应用系统,自然而然就盯上了它,但是它真能够解...

osc_nq69o22c
51分钟前
16
0
06-敏捷开发框架-apis 脚本库 引用位置无关性设计

动态引入技术的设计,对我们来说非常重要。 同时也说明动态语言的使用对我们来说也是非常重要。 没有动态语言的支撑,有些想法可能不容易实现,或者有替代方案,可能会花更大的代价。 前端开...

osc_5zg9z6t1
53分钟前
21
0
(三)学习了解OrchardCore笔记——灵魂中间件ModularTenantContainerMiddleware的第一行①的模块部分

  了解到了OrchardCore主要由两个中间件(ModularTenantContainerMiddleware和ModularTenantRouterMiddleware)构成,下面开始了解ModularTenantContainerMiddleware中间件第一行代码。   ...

osc_kdarxvx0
54分钟前
15
0
50Mn18Cr4V锻锻环件

电机无磁护环怎么锻性能才能《高高》?50Mn18Cr4V高锰无磁钢在变形温度为900~1 100℃、应变速率为0.1 ~10s-1条件下的热变形行为. 结果,VC第二相的应变诱导析出对50Mn18Cr4V的热变形行为产生...

无磁钢
55分钟前
16
0
【遇见offer】一汽-大众实习生专场来啦!成长+学习+福利,一个也不能少~

在上次一汽-大众的社招直播之后,实习生的专场招聘也终于来啦! 针对2020年暑期,我们提供了非常多的实习岗位给大家选择。 如果你想得到大厂实习的宝贵经验,如果你想得到更快速的成长,如果...

osc_b88oux8w
56分钟前
25
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部