题解 CF1537E2 Erase and Extend (Hard Version)

CF1537E2 Erase and Extend (Hard Version)

简要题意

给你一个字符串，找到该字符串的一个前缀并不断复制，可以删除末尾元素，最终要使得得到的字符串长度为 $k$ 且字典序最小。

策略分析

对于此类构造题，我们一般需要运用逆向思维，也就是说我们要从前往后扫而不是从后往前删。为什么这样想呢？我们可以发现，字典序最小当且仅当我们要找的前缀的第 $i$ 位比第 $i \bmod len$ 位的字典序小，这样拼接起来才能够使得字典序最小，这个结论是显然的，证明可以使用反证法。

参考代码

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;

namespace SHAWN {
    int n, k, l = 1;
    string s;
    int work()
    {
        cin >> n >> k >> s;
        for (int i = 0; i < n; ++i) {
            if (s[i] < s[i % l]) { l = i + 1; }
            else if (s[i] > s[i % l]) { break; }
        }
        for (int i = 0; i < k; ++i) {
            cout << s[i % l];
        }
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}