Moe's CF Life

喵哈~ 主人，今天我们来解决一个关于字符串的有趣问题，就像把一团乱糟糟的毛线整理成 k 个一模一样的小线球一样，很有趣的喵！

题目大意

这道题叫做 k-string，听起来就很特别，对吧喵？

一个字符串如果能由某个子串重复 k 次拼接而成，那它就是一个 k-string。比如说，"ababa" 就不是一个 k-string（除了 k=1 的情况）。但是 "abcabc" 就是一个 2-string（由 "abc" 重复2次得到），也是一个 1-string。

题目会给我们一个正整数 k 和一个字符串 s。我们的任务是重新排列字符串 s 里的字母，让它变成一个 k-string。如果可以做到，就输出重新排列后的字符串；如果无论如何都做不到，就输出 -1 喵。

举个栗子：

k = 2, s = "aazz"
我们可以把 s 排列成 "azaz"。它是由 "az" 重复 2 次构成的，所以是一个 2-string。输出 "azaz" 就好啦。
k = 3, s = "abcabcabz"
这个字符串里有3个'a'，3个'b'，3个'c'，但只有1个'z'。'z'的数量是1，不能被3整除，所以不管怎么排列，都不可能构成由某个子串重复3次的形式。所以这种情况就无解，输出 -1 喵。

解题思路

主人，要解决这个问题，我们得抓住最关键的一点喵！

一个字符串 S 如果是 k-string，那么它是由某个基础单元 base 重复 k 次得到的。这意味着 S 中每一种字母的数量，都必须是 k 的倍数！

为什么呢？你想呀，如果基础单元 base 中有 n 个字母 'a'，那么由它重复 k 次构成的 k-string S 中就一定有 n * k 个 'a'。反过来说，如果 S 中 'a' 的数量不是 k 的倍数，那它就不可能分解成 k 个完全相同的部分，对吧？

所以，我们的思路就清晰多啦：

统计频率：首先，我们要数一数输入字符串 s 中每个字母（'a' 到 'z'）分别出现了多少次。就像猫猫数自己的小鱼干一样，要数清楚哦。
检查整除：然后，我们检查每个字母的出现次数。如果有任何一个字母的数量不能被 k 整除，那就说明我们的小鱼干没法平均分给 k 只小猫，也就意味着无法构成 k-string。这时候就可以直接判断无解，输出 -1。
构建基础单元：如果所有字母的数量都能被 k 整除，那就说明有解！我们可以构建出那个基础的子串 base。对于每个字母，它在 base 中出现的次数就是它在原字符串 s 中总次数除以 k。比如 s 中有6个'a'，k 是3，那么基础单元 base 中就应该有 6 / 3 = 2 个'a'。
拼接答案：我们把所有字母按照计算出的数量放进 base 字符串里（为了方便，可以按字母表顺序放）。最后，把这个 base 字符串重复 k 次，就是我们的答案啦！喵~

题解

下面就是本喵为主人准备的 C++ 代码，里面有详细的注释哦！

cpp

#include <iostream>
#include <string>
#include <vector>
#include <numeric>

// 解决问题的核心函数喵
void solve() {
    int k;
    std::cin >> k;
    std::string s;
    std::cin >> s;

    // 用一个大小为26的向量来统计每个字母('a'到'z')的出现次数
    // 就像为每种小鱼干准备一个盘子一样喵
    std::vector<int> counts(26, 0);
    for (char c : s) {
        counts[c - 'a']++;
    }

    // 这个字符串用来存放 k-string 的基础单元
    std::string base_unit;
    
    // 要想构成 k-string，原字符串中每个字符的数量都必须能被 k 整除。
    // 我们来检查一下从 'a' 到 'z' 的所有字符。
    for (int i = 0; i < 26; ++i) {
        // 如果某个字符的数量不能被 k 整除，那就不可能啦
        if (counts[i] % k != 0) {
            std::cout << -1 << std::endl;
            return; // 直接结束程序
        }
        
        // 如果可以整除，就计算这个字符在基础单元中应该出现多少次
        int num_in_unit = counts[i] / k;
        
        // 把这个字符按照计算出的次数，添加到基础单元字符串中
        // 这样构建出的 base_unit 是按字母顺序的，很整齐喵
        for (int j = 0; j < num_in_unit; ++j) {
            base_unit += (char)('a' + i);
        }
    }

    // 如果程序能走到这里，说明一个合法的基础单元 base_unit 已经构建好了
    // 最终的 k-string 就是把 base_unit 重复 k 次
    // 我们直接把 base_unit 输出 k 次就好啦
    for (int i = 0; i < k; ++i) {
        std::cout << base_unit;
    }
    std::cout << std::endl;
}

int main() {
    // 稍微加速一下输入输出，让程序跑得更快一点喵
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    solve();

    return 0;
}

知识点介绍

这道题虽然简单，但是涉及到的知识点在编程竞赛中可是非常基础和重要的哦，喵~

频率统计 (Frequency Counting)
- 这是算法问题中的一个常见操作。对于处理字符问题，特别是只包含小写英文字母的情况，使用一个大小为26的整型数组（或 std::vector）是非常高效的方法。数组的索引 i (从0到25) 对应字母 'a' + i。counts[c - 'a']++ 这种写法可以巧妙地将字符 'a'-'z' 映射到索引 0-25，是需要牢牢记住的小技巧喵！
整除性质 (Divisibility Property)
- 这是解决本题的数学核心。能够从 "重新排列成 k 个重复子串" 这个要求，推导出 "每个字符的个数必须是 k 的倍数" 这个性质，是解题的关键一步。这种从问题现象反推其必要条件的思维方式非常重要。
字符串的构建 (String Construction)
- 在 C++ 中，我们可以很方便地使用 += 操作符来向 std::string 的末尾追加字符或另一个字符串。在循环中重复追加，是构建新字符串的常用方法。代码中 base_unit += (char)('a' + i); 就是一个很好的例子。

希望本喵的讲解对主人有帮助！如果还有其他问题，随时可以再来找我玩哦，喵~

题目大意 ​

解题思路 ​

题解 ​

知识点介绍 ​

题目大意

解题思路

题解

知识点介绍