Moe's CF Life

Appearance

F. Lost in Transliteration - 题解 ​

比赛与标签 ​

比赛: 2017-2018 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) 标签: implementation 难度: *1300

喵喵的题目解读 ​

主人，你好喵~ 这道题其实是一个非常有趣的字符串“找不同”游戏哦！(ฅ'ω'ฅ)

题目告诉我们，在一种叫做 Berland 的语言里，有些发音用拉丁字母写出来时会产生歧义。具体来说，有两种情况：

  1. 发音 u 可以写作 "u"，也可以写作 "oo"。它们是完全等价的。
  2. 发音 h 可以写作 "h"，也可以写作 "kh"。它们也是完全等价的。

因为可以来回替换，所以像 "ulyana" 和 "oolyana" 就是同一个名字。我们的任务是，给定 n 个用拉丁字母写成的名字，找出其中到底有多少个 独一无二 的名字。

简单来说，就是要把所有本质上是同一个名字的字符串算作一组，然后数一数总共有多少组，喵~

寻找标准写法的魔法喵~ ​

当一堆东西可以变来变去，但本质上是等价的时候，一个超级好用的魔法就是给它们找一个统一的 “标准形态” (Canonical Form)！只要两个字符串的“标准形态”是一样的，那它们就肯定是同一个名字啦，呐。

我们的目标就是设计一个函数，能把任何一个名字，都转换成它独一无二的标准形态。然后，我们只需要统计有多少种不同的标准形态就可以啦！用 C++ 的 std::set 来存放这些标准形态，它会自动帮我们去重，真是太方便了，喵！

那么，这个“标准形态”要怎么设计呢？我们可以分两步走：

第一步：梳理 h 和 kh ​

"h" 和 "kh" 的关系比较简单，一个长一个短。为了统一，我们不如总是把长的变成短的。就像把蓬松的猫毛梳顺一样，我们把所有 "kh" 都替换成 "h"。

比如，"mikhail" 就变成了 "mihail"。如果是 "kkkhoon" 这种复杂的，我们就一直替换，直到没有 "kh" 为止： "kkkhoon" -> "kkh"oon -> "kh"oon -> "hoon"。 这样一来，所有等价的名字在 h 的表示上就统一了！

第二步：驯服 u 和 oo ​

这个稍微麻烦一点，因为 "u" 和 "oo" 可以互相转换。

一个聪明的想法是，我们先让字符串里只剩下一种形式。比如说，我们先把所有的 "u" 都替换成 "oo"。

  • "kuooper" -> k + "oo" + ooper -> "kooooper"
  • "ulyana" -> "oo" + lyana -> "oolyana"

经过这一步，字符串里就只有 'o'，没有 'u' 了。现在的问题就变成了如何标准化一连串的 'o'。 既然两个 'o' ("oo") 等价于一个 'u'，那我们就可以把连续的 'o' 两两配对，每一对都换成一个 'u'。

  • 如果有一串 'o'，数量是 count。
  • 那么可以凑成 count / 2 对，也就是换成 count / 2 个 'u'。
  • 如果 count 是奇数，最后还会剩下 count % 2 (也就是1) 个 'o'，这个落单的 'o' 就保留下来好了。

举个例子： 对于 "kooooper"，中间有4个 'o'。4 / 2 = 2，4 % 2 = 0。所以 oooo 的标准形态是 uu。整个单词的标准形态就是 "kuuper"。 对于 "koouper"，先变成 "kooooper"，然后也得到 "kuuper"。 看，它们的标准形态一样了！问题解决，喵~

总结一下我们的魔法步骤：

  1. 读入一个名字字符串。
  2. 施展标准化魔法： a. 循环地将所有 "kh" 替换为 "h"。 b. 将所有 "u" 替换为 "oo"。 c. 遍历新字符串，将连续的 'o' 块按照上面的规则（每两个'o'换一个'u'）进行转换。
  3. 将最终得到的标准形态字符串放入一个 std::set 中。
  4. 重复以上步骤，直到处理完所有名字。
  5. set 的大小就是我们要求的答案啦！

猫娘的魔法代码 ​

cpp
#include <iostream>
#include <set>
#include <string>

using namespace std;

// 这个函数就是我们的标准化魔法喵！
// 它会把任何一个字符串 s 转换成它唯一的标准形态
string canonical(string s) {
    // 第一步：循环替换 "kh" 为 "h"，直到没有 "kh" 为止
    size_t pos;
    while ((pos = s.find("kh")) != string::npos) {
        s.replace(pos, 2, "h");
    }

    // 第二步：先把所有的 "u" 替换成 "oo"，方便后续统一处理
    string t = "";
    for (char c : s) {
        if (c == 'u') {
            t += "oo";
        } else {
            t += c;
        }
    }
    s = t; // 现在 s 中只有 'o'，没有 'u' 了

    // 第三步：标准化连续的 'o'
    string res = "";
    int i = 0;
    while (i < s.length()) {
        if (s[i] == 'o') {
            // 发现了一个 'o'，数数看后面有多少个连续的 'o'
            int count = 0;
            int j = i;
            while (j < s.length() && s[j] == 'o') {
                count++;
                j++;
            }
            // 每两个 'o' 换成一个 'u'
            for (int k = 0; k < count / 2; k++) {
                res += 'u';
            }
            // 如果 'o' 的数量是奇数，会剩下一个 'o'，把它加上
            if (count % 2 == 1) {
                res += 'o';
            }
            // 从这串 'o' 的末尾继续向后处理
            i = j;
        } else {
            // 如果不是 'o'，直接加到结果里
            res += s[i];
            i++;
        }
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    // 使用 set 来自动存储独一无二的标准形态字符串
    set<string> distinct;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        // 把每个名字转换成标准形态，然后插入 set
        distinct.insert(canonical(s));
    }
    // set 的大小就是最终答案啦！
    cout << distinct.size() << endl;
    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(n * (L² + L * log n)) 的说 这里的 n 是名字的数量，L 是名字的最大长度。 对于每个名字，canonical 函数的耗时是：

    1. 替换 kh 的 while 循环，每次 find 和 replace 大约是 O(L)，最坏情况下可能执行 O(L) 次，所以这部分是 O(L²)。
    2. u -> oo 的转换和 o 的标准化都只需要遍历一次字符串，是 O(L)。
    3. 所以 canonical 函数总共是 O(L²)。 在主函数中，我们对 n 个字符串执行此操作，并将结果插入 set。set 的插入操作需要比较字符串，时间是 O(L * log n)。 所以总时间复杂度是 O(n * (L² + L * log n))。对于题目给的 n=400, L=20 的范围，这个速度是绰绰有余的，喵~

  • 空间复杂度: O(n * L) 的说 我们需要一个 set 来存储最多 n 个标准形态的字符串，每个字符串长度最多为 L（实际上u->oo会临时加长，但最终长度差不多），所以空间主要是 set 占用的，为 O(n * L)。

知识点与总结 ​

这次的冒险旅程，我们学会了很重要的东西哦！

  1. 等价类与标准型: 这是解决这类问题的核心思想！当题目定义了一种“等价”关系时，尝试为每一个等价类找一个唯一的、易于计算的“代表”或“标准形态”，问题就会迎刃而解。
  2. std::set 的妙用: set 是 C++ STL 中一个超级棒的容器，它能自动保持元素的唯一性和有序性。在需要去重统计的时候，它就是我们的好朋友！
  3. 字符串处理技巧: 我们练习了 string::find、string::replace 等实用的字符串操作。要注意，对字符串进行修改时，有时先创建一个新字符串（像代码里处理u->oo那样）会比在原地修改更清晰、更不容易出错哦。
  4. 注意操作顺序: 设计标准形态时，处理步骤的顺序很重要。就像做小饼干，要先和面再放进烤箱，顺序错了就不好吃了喵！本题中先处理kh再处理u/oo就是一个稳定可靠的顺序。

希望这篇题解能帮助到你，主人！继续享受算法的乐趣吧，喵~ (´｡• ᵕ •｡`) ♡

Released under the MIT License.

Copyright © 2024-present Moe