CF1537E2 Erase and Extend 题解

分析

通过观察题目，可以证明结果一定是由多次前缀复制得来的。

题目要求你进行删和复制的操作，与其交替着操作，不如直接先删到最优的前缀再进行复制。

现在就是要找最优的前缀。从头一位一位往后遍历。用 \(l\) 来存储目前最优前缀的长度，第 \(i\) 位对应复制后的 \(k\) 位最优前缀就是第 \(i\bmod l\) 位。在往后遍历时，如果下一位的 ASCII 码比最优前缀第 \(i\bmod l\) 位的大，就说明后面没有最优解了，直接 break。如果小于的话，说明当前的解更优，更新一下长度即可。

复杂度 \(\mathcal O(n)\)。

代码

#include<bits/stdc++.h>
using namespace std;
namespace Raiden
{
    int work()
    {
        string s;
        int n,k;
        int l=1;
        cin>>n>>k>>s;
        for(int i=0;i<n;i++)
        {
            if(s[i]>s[i%l])
                break;
            else if(s[i]<s[i%l])
                l=i+1;
        }
        for(int i=0;i<k;i++)
            cout<<s[i%l];
        return 0;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    return Raiden::work();
}