题解 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 的大小关系，有如下三种情况：

相关代码：

#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;
}