D. Unnatural Language Processing - 题解

比赛与标签

比赛: Codeforces Round 918 (Div. 4) 标签: greedy, implementation, strings 难度: *900

题目大意喵~

喵~ 主人 sama，来看看这道有趣的字符串题吧！(ฅ'ω'ฅ)

题目里定义了一种简单的语言，它只有 a, b, c, d, e 这五个字母。

元音 (Vowel, V): a 和 e
辅音 (Consonant, C): b, c, 和 d

这种语言的 "音节" 只有两种固定的结构：

CV: 一个辅音跟着一个元音 (比如 ba, de)
CVC: 一个元音，前后各一个辅音 (比如 bab, ced)

一个 "单词" 就是由这些音节一个接一个组成的。现在呢，Lura 小姐姐写好了一个单词，但是忘记了怎么把它划分成音节了。我们的任务就是帮她把单词正确地切分开，并在音节之间加上一个点 .。

比如，对于单词 bacedbab，正确的划分是 ba.ced.bab 呐。

题目保证给定的单词一定能被成功划分，我们只需要输出一种划分方式就可以啦！

解题思路喵！

这道题呀，第一眼看上去可能会想从左到右一个一个地去匹配音节。但是很快就会发现问题喵！比如说，如果一个单词开头是 CVCV...，我们是应该把它看成 CVC + V... 还是 CV + CV... 呢？V... 开头的音节是不存在的，所以前者不行，但判断起来就有点小麻烦了。

这时候，聪明的猫娘就要换个思路啦！让我们从后往前看，会不会有什么奇妙的发现呢？喵~ (´｡• ᵕ •｡`) ♡

我们再来观察一下音节的结构：

CV 结构的音节，最后一个字母一定是 元音 (V)。
CVC 结构的音节，最后一个字母一定是 辅音 (C)。

哇！发现了没有？一个音节的最后一个字母，直接决定了这个音节的类型和长度！

如果一个音节的结尾是元音，它只可能是 CV 结构，长度为 2。
如果一个音节的结尾是辅音，它只可能是 CVC 结构，长度为 3。

这个性质太棒了！这意味着我们从单词的末尾开始处理，每次都能唯一确定最后一个音节是什么。这不就是完美的贪心策略嘛！

所以，我们的算法就出来啦：

从字符串的最后一个字符开始往前看。
检查当前指向的（也就是未处理部分的最后一个）字符是元音还是辅音。
如果是元音，那么它一定是 CV 音节的结尾。我们就从当前位置往前取 2 个字符，这就是一个完整的音节。
如果是辅音，那么它一定是 CVC 音节的结尾。我们就从当前位置往前取 3 个字符，这也是一个完整的音节。
把切下来的音节存起来，然后继续处理剩下的字符串部分，直到整个字符串都被处理完。
因为我们是从后往前找的音节，所以得到的音节列表是反的。最后只需要把这个列表反转一下，再用 . 连接起来输出，就大功告成啦！

举个栗子 bacedbab：

末尾是 b (辅音)，切下 bab (CVC)。剩下 baced。
末尾是 d (辅音)，切下 ced (CVC)。剩下 ba。
末尾是 a (元音)，切下 ba (CV)。剩下空字符串。我们得到的音节序列是 [bab, ced, ba]。反转一下就是 [ba, ced, bab]。完美！

代码实现的说~

下面就是具体的代码实现啦，我已经加上了详细的注释，方便主人 sama 理解哦~

cpp

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

// 一个判断是不是元音的小帮手函数喵~ 'a' 和 'e' 是元音哦！
bool is_vowel(char c) {
    return c == 'a' || c == 'e';
}

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // 我们准备一个 vector 来存放找到的音节们
    std::vector<std::string> syllables;
    int i = n - 1; // 从字符串的最后一个字符开始处理

    // 这就是我们从后往前贪心切割的核心逻辑啦！
    while (i >= 0) {
        if (is_vowel(s[i])) {
            // 如果最后一个字母是元音，那它肯定是 CV 结构，长度为 2
            // 我们就把它切下来~
            syllables.push_back(s.substr(i - 1, 2));
            i -= 2; // 指针向前移动 2 位
        } else {
            // 如果最后一个字母是辅音，那它肯定是 CVC 结构，长度为 3
            // 也把它切下来！
            syllables.push_back(s.substr(i - 2, 3));
            i -= 3; // 指针向前移动 3 位
        }
    }

    // 因为我们是倒着找的，所以要把音节的顺序正过来才行哦~
    std::reverse(syllables.begin(), syllables.end());

    // 最后用 '.' 把可爱的音节们串起来输出就好啦！
    for (size_t j = 0; j < syllables.size(); ++j) {
        std::cout << syllables[j];
        if (j < syllables.size() - 1) {
            std::cout << ".";
        }
    }
    std::cout << "\n";
}

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

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析喵

时间复杂度: O(N) 的说。这里的 N 是所有测试用例中字符串长度的总和。我们对每个字符串都只从后往前遍历了一次，每次切分音节的操作（substr）合起来的总成本也和字符串长度成正比。所以整体是线性的，非常高效！
空间复杂度: O(N) 的说。我们用了一个 vector 来存储切分好的音节们，在最坏的情况下（比如全是 CV 音节），需要存储整个字符串的内容。所以空间开销也是线性的。

知识点与总结呐~

这道题虽然不难，但是个很好的例子，告诉我们一些重要的解题思想哦！

贪心大法好喵 (Greedy Algorithm): 这道题的核心就是贪心。我们通过分析问题性质，找到了一个在每一步都做出局部最优选择（根据最后一个字符判断音节类型）的策略，而这个策略恰好能导向全局最优解。
逆向思维的重要性 (Reverse Thinking): 当从正面思考问题遇到困难或变得复杂时，不妨试试从反面、从结尾来思考。就像这道题，从后往前看，问题立刻就变得清晰明了了！这在很多字符串和动态规划问题中都是一个非常有用的技巧。
对问题性质的洞察: 解决问题的关键在于发现“音节最后一个字母决定其结构”这一隐藏性质。多观察、多分析，才能找到解题的突破口！

希望这篇题解能帮到主人 sama！只要找到问题的关键，再复杂的题目也会变得像毛线球一样好解开的！继续加油喵~ ヾ(๑╹◡╹)ﾉ"

D. Unnatural Language Processing - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵！ ​

代码实现的说~ ​

复杂度分析喵 ​

知识点与总结呐~ ​