E1. Erase and Extend (Easy Version) - 题解

比赛与标签

比赛: Codeforces Round 726 (Div. 2) 标签: binary search, brute force, dp, greedy, hashing, implementation, string suffix structures, strings, two pointers 难度: *1600

题目大意喵~

主人你好呀！这道题是说，我们有一个字符串 s，可以对它做两种可爱的操作，喵~

删除操作: 把字符串的最后一个字符给删掉。
复制操作: 把整个字符串复制一遍，然后拼接到自己的尾巴上（也就是 s := s + s）。

我们可以任意次地使用这两种操作。我们的最终目标是，通过这些操作，得到一个长度正好是 k 的，并且字典序最小的字符串。请把它找出来吧，的说！

解题思路分析呐

喵~ 看到这两种操作，可能会觉得组合起来千变万化，有点头晕。但是我们来仔细分析一下，就能发现其中的小秘密啦！

我们的目标是生成一个长度为 k 的字符串。这个字符串是怎么来的呢？它一定是由某个“基本单元”不断重复，然后截取前 k 个字符得到的。

那这个“基本单元”又是什么呢？它一定是我们对原始字符串 s 进行若干次（可能为0次）“删除操作”后得到的字符串。也就是说，这个“基本单元”必定是 s 的一个前缀！

为什么呢？主人请想一下，假如我们先复制，再删除，比如 s -> ss -> ss（去掉最后一个字符）。这和我们先从 s 中得到 s 的某个前缀，再用这个前缀去复制，效果是一样的呀。任何复杂的操作序列，最终都可以归结为：

第一步：选择一个基础模板。 通过删除操作，我们从原字符串 s 中选择一个前缀作为我们的“基本单元”。
第二步：无限复制。 将这个选定的前缀不断地自我复制，直到长度超过或等于 k。
第三步：精确裁剪。 从这个长长的字符串里，截取前 k 个字符作为最终的候选字符串。

这么一想，问题是不是就清晰多啦？我们的任务，就变成了从 s 的所有可能的前缀中，找到一个最优的前缀。用这个最优前缀生成的长度为 k 的字符串，就是所有可能结果中字典序最小的那个！

s 的前缀有哪些呢？就是 s[0]、s[0...1]、s[0...2]... 一直到 s[0...n-1]。因为 n 和 k 的数据范围都不大（最大5000），我们可以用最简单直接的方法——暴力枚举！喵哈哈~

我们的策略就是：

遍历 s 的所有前缀，从长度 1 到 n。
对于每一个前缀，我们都用它来生成一个长度为 k 的候选字符串。
在所有这些候选字符串中，我们挑一个字典序最小的，就是最终的答案啦！

举个例子，如果 s = "abcd", k = 5：

用前缀 "a" 生成："a" -> "aa" -> "aaaa" -> "aaaaaaaa"... 截取长度5，得到 "aaaaa"。
用前缀 "ab" 生成："ab" -> "abab" -> "ababab"... 截取长度5，得到 "ababa"。
用前缀 "abc" 生成："abc" -> "abcabc"... 截取长度5，得到 "abcab"。
用前缀 "abcd" 生成："abcd" -> "abcdabcd"... 截取长度5，得到 "abcda"。

把这些候选者 "aaaaa", "ababa", "abcab", "abcda" 放在一起比较，"aaaaa" 明显是最小的！所以它就是答案啦，喵~

代码实现的说

cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;

    // 初始化一个字典序理论上最大的字符串，方便后面比较和更新喵~
    // 'z' + 1 是不行的，所以直接用全'z'串就好啦
    string ans(k, 'z'); 

    // 遍历所有可能的前缀长度 i，从 1 到 n
    for (int i = 1; i <= n; i++) {
        // 取出长度为 i 的前缀作为我们的“基本单元”
        string base = s.substr(0, i);
        string candidate = "";
        
        // 不断复制这个基本单元，直到长度不小于 k
        while (candidate.length() < k) {
            candidate += base;
        }
        
        // 将生成的字符串截断到长度 k，得到一个候选答案
        candidate = candidate.substr(0, k);
        
        // 如果当前生成的字符串比我们记录的最小答案还要小，就更新答案！
        if (candidate < ans) {
            ans = candidate;
        }
    }

    // 输出最终找到的最小字符串，任务完成喵！
    cout << ans << endl;

    return 0;
}

复杂度分析喵

时间复杂度: O(n * k) 的说。我们的代码有一个外层循环，它会遍历 n 个不同的前缀（从长度1到n）。在循环内部，我们构建一个长度为 k 的字符串。虽然 while 循环和字符串拼接看起来有点复杂，但实际上构建一个长度为 k 的字符串总的字符操作次数是 O(k) 级别的。所以，总的时间复杂度就是 n 次循环乘以每次循环的 O(k) 操作，即 O(n * k)。对于本题的数据范围，这是完全可以接受的！
空间复杂度: O(k) 的说。我们在程序中主要需要存储最终答案 ans 和临时的候选字符串 candidate，它们的长度都是 k。所以，额外占用的空间主要是由这些字符串决定的，空间复杂度就是 O(k) 啦。

知识点与总结

这道题虽然标签很多，看起来很吓人，但核心思想却非常质朴可爱，喵~

问题转化: 最关键的一步！把一个看似复杂的操作问题，转化为一个简单的“寻找最优前缀”的枚举问题。这种“化繁为简”的思维是解决算法题的一大利器哦！
暴力枚举 (Brute Force): 当问题规模不大时，不要害怕暴力！直接、清晰地枚举所有可能性，往往就是最有效的正解。这道题就是暴力美学的胜利，喵哈哈！
字符串处理: 题目也考察了对 std::string 的熟练运用。substr() 截取子串，+= 拼接字符串，以及直接用 <、> 比较字符串的字典序，都是非常基础且强大的工具，主人要熟练掌握呐！
贪心思想: 我们的解法其实也蕴含了贪心的思想。我们相信，最优的解一定是由某个前缀生成的，所以我们只需要在所有前缀生成的结果中，贪心地选择那个最小的即可。

总的来说，这是一道非常好的思维入门题，它告诉我们，面对问题时先不要慌，静下心来分析操作的本质，往往能找到意想不到的简单出路。希望这篇题解能帮到你，加油哦，主人！喵~ >w<

E1. Erase and Extend (Easy Version) - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路分析呐 ​

代码实现的说 ​

复杂度分析喵 ​

知识点与总结 ​