喵~ 主人，今天我们来一起看看 Codeforces 上的一个有趣问题：汤姆·里德尔的日记！听起来是不是有点神秘呀？别担心，让本猫娘带你一步步解开这个谜题，超级简单的说！

Codeforces 855A: Tom Riddle's Diary

---

题目大意喵

哈利·波特正在追查魂器，第一个遇到的就是汤姆·里德尔的日记。为了查清楚日记到底影响了多少人，他拿到了一份按时间顺序记录的、曾经拥有过日记的人员名单。

我们的任务很简单哦~ 对于名单上的每一个名字，我们需要判断这个名字在 它自己之前 是否已经出现过。

• 如果这个名字在前面出现过，我们就输出 "YES"。
• 如果这是这个名字第一次出现，我们就输出 "NO"。

举个栗子： 名单是 tom, lucius, ginny, harry, ginny, harry。

1. tom：第一次出现，输出 NO。
2. lucius：第一次出现，输出 NO。
3. ginny：第一次出现，输出 NO。
4. harry：第一次出现，输出 NO。
5. ginny：前面第3个就是 ginny，出现过了！输出 YES。
6. harry：前面第4个就是 harry，也出现过了！输出 YES。

是不是很简单明了呀，喵~？

---

解题方法思路

要解决这个问题，我们需要一个好用的小本本（或者说是一个记忆盒子）来记下所有已经出现过的名字，喵~

每当读到一个新名字时，我们就去翻翻我们的小本本：

1. 检查：看看这个新名字在不在小本本上？
2. 判断：
   • 如果在，说明之前见过啦，就大声回答 "YES"！
   • 如果不在，说明是新朋友哦，就回答 "NO"。
3. 记录：对于所有第一次出现的新朋友，回答完 "NO" 之后，要立刻把他们的名字记到我们的小本本上，这样下次再见到他们时，我们就能认出来啦。

这个“小本本”，在我们的 C++ 世界里，用一个叫做 std::unordered_set 的数据结构来实现最合适不过了。它查找起来超级快，就像猫咪抓蝴蝶一样敏捷，嗖的一下就能完成检查，效率非常高哦！

---

题解代码 (C++)

下面就是用 C++ 实现的香喷喷的代码啦~

#include <iostream>
#include <string>
#include <unordered_set>

int main() {
    // 这两行是加速魔法哦，让输入输出变得超级快，像小猫追激光笔一样！喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n; // 先读入总共有多少个名字

    // 这就是我们神奇的记忆小本本啦，一个叫做 unordered_set 的东西
    // 它专门存放不重复的名字！
    std::unordered_set<std::string> seen_names;

    // 循环 n 次，一个一个名字来处理哦
    for (int i = 0; i < n; ++i) {
        std::string name;
        std::cin >> name; // 读入当前这个名字

        // 用 .contains() 查一下名字在不在我们的小本本里
        // 这是 C++20 的新功能，非常方便直观！
        if (seen_names.contains(name)) {
            // 如果 .contains() 返回 true，说明在小本本里找到了！
            // 是老朋友了，喵~
            std::cout << "YES\n";
        } else {
            // 如果没找到，说明是第一次见到的新朋友！
            std::cout << "NO\n";
            // 快把新朋友的名字记到小本本上，下次就能认出来啦！
            seen_names.insert(name);
        }
    }

    return 0; // 任务完成，开心收工~
}

---

相关知识点介绍：std::unordered_set 大揭秘！

代码里那个 std::unordered_set 是不是很神奇？它可是解决这类“检查重复”问题的超级利器哦，让本猫娘给你详细介绍一下吧！

1. std::unordered_set 是什么呀？

它是一个 无序集合 容器，就像一个魔法袋子，喵~

• 独一无二：你往里面放东西，它会自动帮你去重。比如你放了两次 "ginny"，袋子里实际上只会有一个 "ginny"。
• 无序：袋子里面的东西是乱序放的，没有固定的前后顺序。它只关心 "某个东西在不在里面"，不关心 "它们是怎么排列的"。
• 飞快：它最厉害的地方就是查找、插入和删除操作都超级快！

2. 为什么它这么快捏？

因为它用了叫做 “哈希”（Hash） 的黑魔法！

简单来说，就是给每个字符串（比如 "harry"）通过一个特殊的算法算出一个独一无二的“身份证号”（哈希值）。当我们要找 "harry" 时，程序不是从头到尾一个一个地翻看袋子里的所有名字，而是直接根据 "harry" 的身份证号去一个特定的位置找。

这样一来，不管集合里有10个名字还是10万个名字，查找和插入的平均时间几乎都是一样的，我们称之为 平均 O(1) 时间复杂度。是不是超级厉害！

3. 和 std::set 有什么不同喵？

C++ 里还有一个叫 std::set 的东西，它和 std::unordered_set 很像，都是存放不重复元素的集合。最大的区别在于：

• std::set：是一个 有序集合。它里面的元素总是排好序的。因为它内部是用红黑树实现的，所以查找、插入和删除的时间复杂度是 O(log N)。
• std::unordered_set：是 无序集合，用哈希表实现，平均时间复杂度是 O(1)。

在这个题目里，我们只关心名字“有没有出现过”，根本不关心这些名字按字母顺序该怎么排。所以，我们当然选择速度更快、更直接的 std::unordered_set 啦！它是这个问题的完美选择，的说！

好啦~ 这道题的讲解就到这里啦，主人学会了吗？喵~ >w<