题解 CF1537E2 【Erase and Extend (Hard Version)】
meyi
2021-06-19 02:20:37
以下将字符串 $s$ 的前缀 $s[1..n]$ 称为 $\text{prefix}(n)$，将字符串 $s$ 无限连接自身构成的字符串的前 $k$ 个字符称为 $f_k(s)$，即 $f_k(s)=\left\{
\begin{array}{l}
s[1..k]\ \ (|s|\ge k) \\ f_k(s+s)\ \ (|s|<k)
\end{array}
\right.$。
将题意转化为求 $f_k(prefix(x))$ 最小的 $x$，有一种贪心做法如下：
枚举前缀的结尾位置 $i$ ，设当前找到的最优前缀为 $pos$ ，$f_k(prefix(pos))[i]$ 为 $t$，比较 $s[i]$ 与 $t$ 的大小关系，有如下三种情况：
1. $s[i]>t$，此时由于 $i$ 以后的每个位置的前缀都会包含 $s[i]$，所以 $i$ 以后不会有更优解，因此直接退出循环。
2. $s[i]<t$，此时若有 $s[1..i-1]=f_k(\text{prefix}(pos))[1..i-1]$ ，则此时 $i$ 优于 $pos$，更新答案。反证一下满足条件，按上述方式循环，若 $s[1..i-1]> f_k(\text{prefix}(pos))[1..i-1]$，则在 $i-1$ 或更早的位置就已退出循环；若 $s[1..i-1]<f_k(\text{prefix}(pos))[1..i-1]$，则不符合 $pos$ 是最优解的定义。故 $s[1..i-1]=f_k(\text{prefix}(pos))[1..i-1]$，满足更新答案的条件。
3. $s[i]=t$，此时直接继续枚举 $i+1$。易得 $f_k(prefix(i))[i+1]=s[1]$，$f_k(prefix(pos))[i+1]=s[(i\mod pos)+1]$，此时必有 $s[(i\mod pos)+1]\le s[1]$，因为若 $s[(i\mod pos)+1]>s[1]$，则我们直接在此处填 $s[1]$ 会更优，不符合 $pos$ 是最优解的定义，同理 $f_k(prefix(i))$ 与 $f_k(prefix(pos))$ 的第 $i+2$，$i+3$，$\cdots$，$k$ 个字符也可按上述方式比较大小关系。因此 $i$ 不会比 $pos$ 更优，但继续枚举下去可能会有更优解。
相关代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ri register int
#define x (i-1)%pos+1
const int maxn=5e5+10;
int m,n;
char t[maxn];
int main(){
scanf("%d%d%s",&n,&m,t+1);
ri k=min(m,n),pos=1;
for(ri i=2;i<=k;++i)
if(t[i]<t[x])pos=i;
else if(t[i]>t[x])break;
for(ri i=1;i<=m;++i)putchar(t[x]);
return 0;
}
```