Moe's CF Life

喵哈喽~！各位主人，今天由我这只小猫娘来给大家讲解一道非常经典的题目——注册系统（Registration System）哦！这道题就像是我们猫咪抢地盘，先来的就有名字，后来的就得在名字后面加个小标记，喵~ ฅ(＾・ω・＾ฅ)

题目大意

这道题呀，是让我们模拟一个简单的网站注册系统。规则是这样哒：

当一个新用户来注册时，他会提交一个想要的用户名。
我们的小系统需要检查一下，这个用户名是不是已经被别的小伙伴用掉了。
如果这个名字没被用过，那太好啦！系统就回复一个 OK，表示注册成功，然后把这个名字记在咱们的小本本（数据库）上。
如果这个名字已经被用过了，系统就要帮他想一个新名字。规则是：在原来的名字后面加上数字，从 1 开始试。比如，如果 cat 被占用了，就试试 cat1。如果 cat1 也被占用了，就试试 cat2，以此类推，直到找到一个没被用过的名字 cat + i。然后把这个新名字告诉用户，并同样记在小本本上。

总的来说，就是对 n 次注册请求，依次给出 OK 或者建议的新名字。很简单对吧？喵~

题解方法

要解决这个问题，我们首先需要一个“小本本”来记录所有已经注册过的用户名。每次来一个新请求，我们都要快速地翻开本本查一下。那么，用什么数据结构来当这个“小本本”最合适呢？

锵锵~！答案就是哈希表（Hash Table）！在 C++ 中，我们可以用 std::unordered_map 来实现。哈希表就像一个有魔法的柜子，你给它一个名字（key），它能瞬间告诉你这个名字对应的东西（value）在哪里，查找和插入的速度都非常快，平均接近 O(1) 哦，简直是为我们这种急性子猫娘量身定做的，嘿嘿。

我们可以让 unordered_map 的键（key）是 std::string 类型的用户名，值（value）呢？

一个简单的想法是，值存一个布尔值，true 表示存在。但这样的话，如果 s 被占用了，我们每次都得从 s1, s2, s3... 一个个重新检查，太慢啦！

更聪明的猫娘会这样做：map 的值（value）存一个整数！这个整数代表什么呢？ db[s] 代表：如果下次再有人想注册 s 这个名字，我们应该从 s 后面接上数字 db[s] 开始尝试。

举个例子吧：

第一次来个用户叫 neko。
- db 里没有 neko。
- 我们输出 OK。
- 然后在 db 里记下：db["neko"] = 1。这表示 neko 这个名字被占用了，如果再有人想要 neko，下一个建议的名字从 neko1 开始。
第二次又来个用户叫 neko。
- db 里有 neko！它的值是 1。
- 我们就尝试生成 neko1。db 里没有 neko1，太棒了！
- 我们输出 neko1。
- 然后更新记录：db["neko"] 的值要更新成 2（因为 1 已经被用掉了），并且要把新名字 neko1 也加到数据库里，记为 db["neko1"] = 1。
第三次又来了个 neko...
- db 里有 neko，它的值是 2。
- 我们尝试 neko2，发现可用！
- 输出 neko2，然后更新 db["neko"] 为 3，并加入 db["neko2"] = 1。

看明白了吗？通过记录下一个要尝试的数字，我们避免了大量的重复检查，让我们的系统跑得飞快，喵~！

题解

下面就是 C++ 的实现代码啦，我已经加上了详细的注释，就像给鱼干做上标记一样清晰！

cpp

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

// 一个让输入输出变快的小魔法，对付大量数据时很有用哦！
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

int main() {
    fast_io(); // 施展魔法！

    int n;
    std::cin >> n;

    // 这就是我们的魔法柜子（数据库）啦！
    // key 是 string 类型的用户名
    // value 是 int 类型，表示如果这个 key 被再次请求，下一个要尝试的后缀数字
    std::unordered_map<std::string, int> db;

    for (int i = 0; i < n; ++i) {
        std::string s;
        std::cin >> s;

        // 在柜子里找一找，有没有叫 s 的名字
        auto it = db.find(s);

        // 如果 it == db.end()，说明没找到，是个新名字！
        if (it == db.end()) {
            // 名字可用，成功注册！
            std::cout << "OK\n";
            // 把这个新名字 s 存进数据库，并标记如果下次再遇到 s，
            // 应该从后缀 1 开始尝试。
            db[s] = 1;
        } else {
            // 哎呀，名字被占用了。
            // 我们从之前记录的数字 k 开始找新名字。
            // it->second 就是 db[s] 的值
            int k = it->second;
            std::string new_name;

            // 一直循环，直到找到一个没被占用的新名字
            while (true) {
                // 拼接出新名字，比如 s + "1" -> "s1"
                new_name = s + std::to_string(k);
                // 检查新名字在不在数据库里
                if (db.count(new_name) == 0) {
                    // 找到了！这个名字可以用，跳出循环
                    break;
                }
                // 如果被占用了，就试试下一个数字
                k++;
            }

            // 输出找到的新名字
            std::cout << new_name << "\n";

            // 更新数据库，非常重要哦！
            // 1. 对于原始名字 s，下次要从 k+1 开始试了
            it->second = k + 1;
            // 2. 新生成的名字 new_name 也要加入数据库
            db[new_name] = 1;
        }
    }

    return 0;
}

知识点介绍

1. 哈希表 (Hash Table)

哈希表是一种非常强大的数据结构，它通过一个叫做“哈希函数”的映射关系，将一个较大的键（比如一个很长的字符串）转换成一个较小的索引值，然后把数据存到这个索引对应的位置。这样，当我们想查找、插入或删除一个元素时，只需要通过哈希函数计算出它的位置，直接操作即可，速度非常快。

优点：平均情况下，增、删、查的时间复杂度都是 O(1)，超级高效！
缺点：在最坏的情况下（比如所有键都映射到同一个位置，称为“哈希冲突”），性能会下降到 O(n)。不过这种情况很少见，std::unordered_map 内部有很好的机制来处理冲突。

2. `std::unordered_map`

这是 C++ 标准库（STL）中哈希表的实现。它储存的是“键-值对”（key-value pairs）。

声明：std::unordered_map<KeyType, ValueType> map_name;
常用操作：
- map[key] = value;: 插入或修改一个键值对。
- map.find(key): 查找一个键。如果找到，返回指向该元素的迭代器；如果没找到，返回 map.end()。
- map.count(key): 检查一个键是否存在。如果存在，返回 1；否则返回 0。这比 find 后再判断要简洁一些。
- iterator->first: 获取迭代器指向元素的键。
- iterator->second: 获取迭代器指向元素的值。

在这道题里，unordered_map 完美地满足了我们快速存取用户名的需求，是解决问题的最佳选择之一，喵~

好啦，今天的讲解就到这里啦！希望主人能从中学到东西。如果还有不懂的，随时可以再来问我哦！拜拜，喵~ (ฅ'ω'ฅ)

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

1. 哈希表 (Hash Table) ​

2. std::unordered_map ​

题目大意

题解方法

题解

知识点介绍

1. 哈希表 (Hash Table)

2. `std::unordered_map`