你好！我是你的信息学奥赛教练。Codeforces 4C (Registration System) 是一道非常经典的字符串处理与哈希应用入门题。在 NOI 系列竞赛（如 CSP-J/S）中，这类题目考察的是你对数据结构的选型能力和对时间复杂度的敏感度。

下面我将按照 NOI 竞赛辅导的要求，为你解析这道题目。

一、 题目描述：[C] Registration System (注册系统)

【问题描述】 你正在为学校开发一个新的系统。每当有新用户注册时，系统会收到一个请求。 如果请求的用户名在系统中不存在，则该系统会将其存入数据库，并向用户返回 OK。 如果请求的用户名已经存在，系统会根据该用户名生成一个新名称：在原用户名后面追加一个最小的正整数，使得该新名称在数据库中从未出现过。系统将存入这个新名称，并向用户返回该名称。

【输入格式】 第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示收到的请求总数。 接下来的 $n$ 行，每行包含一个由小写字母组成的字符串，长度在 $1$ 到 $32$ 之间。

【输出格式】 输出 $n$ 行。对于每个请求，如果注册成功，输出 OK；否则输出生成的唯一新名称。

【样例输入】

4
abacaba
acaba
abacaba
acaba

【样例输出】

OK
OK
abacaba1
acaba1

【数据范围】

• 对于 100% 的数据，$1 \le n \le 10^5$，字符串长度 $\le 32$，且仅包含小写字母。
• 时间限制：1.0s，内存限制：256MB。

二、 预备知识点

1. 哈希表 (Hash Table)：了解如何通过键值对快速查找元素。
2. C++ STL 容器：
   • std::string：字符串处理。
   • std::map：基于红黑树的关联容器（时间复杂度 $O(\log n)$）。
   • std::unordered_map：基于哈希表的关联容器（时间复杂度平均 $O(1)$）。
3. 字符串拼接与转化：如何将整数转化为字符串并连接。

三、 教学启发与草稿纸推理过程

1. 启发式提问

• 教练问：如果我们用数组存储已经注册的用户名，每来一个新名字就暴力遍历一遍数组，时间复杂度是多少？
• 学生答：每次查找是 $O(n)$，总共 $n$ 个名字，就是 $O(n^2)$。当 $n=10^5$ 时，一定会超时。
• 教练问：我们需要一种结构，能快速告诉我“这个名字以前出现了几次”。你觉得用什么数据结构最合适？

2. 草稿纸上的模拟（图形化思路）

请在你的草稿纸上画出以下逻辑：

步骤一：建立“名字 $\rightarrow$ 出现次数”的映射表 (Map)

关键发现：数据库里存的是原始名字。你不需要把带数字后缀的名字也存进去，因为题目规则是基于原始请求生成的。

3. 复杂度分析与优化建议

• 时间复杂度：
  • 使用 std::map<string, int>：每次操作涉及字符串比较（长度 $L$）和红黑树查找，总复杂度 $O(n \cdot L \cdot \log n)$。
  • 使用 std::unordered_map<string, int>：基于哈希表，总复杂度 $O(n \cdot L)$。
  • 在 $n=10^5, L=32$ 的情况下，两种方式均可通过，但 unordered_map 更快。
• 空间复杂度：需要存储所有不重复的字符串，最坏情况下为 $O(n \cdot L)$，约为 $3.2 \text{MB}$，远小于 $256 \text{MB}$。

4. 算法流程图 (Mermaid 语法)

graph TD
    A("开始 (Start)") --> B("读取请求总数 n")
    B --> C{"i 小于 n?"}
    C -- "否 (No)" --> D("结束 (End)")
    C -- "是 (Yes)" --> E("读取用户名 s")
    E --> F{"s 在 Map 中是否存在?"}
    F -- "不存在" --> G("输出 OK")
    G --> H("将 s 存入 Map 并设计数为 1")
    F -- "存在" --> I("获取当前计数 count")
    I --> J("生成新字符串: s + count")
    J --> K("输出新字符串")
    K --> L("将 Map 中 s 的计数加 1")
    H --> M("i 增加 1")
    L --> M
    M --> C

四、 读题关键点总结

在做 NOI 类题目时，理解题意的关键词通常隐藏在以下几个地方：

1. “是否存在” (Existence)：看到这个词，立刻反应出查找算法（二分、哈希、字典树等）。
2. “最小的正整数” (Smallest positive integer)：这通常意味着你可以使用一个计数器，从 1 开始累加。
3. “追加” (Append)：字符串连接操作，注意 $O(L)$ 的开销。
4. 数据范围 (Constraints)：
   • $10^5$：意味着算法必须优于 $O(n^2)$，通常选择 $O(n \log n)$ 或 $O(n)$。
   • 字符串长度 $32$：说明字符串处理本身不是瓶颈，但要考虑字符串作为哈希键值的开销。

教练寄语：这题是哈希应用的基础。在实际比赛中，如果你不确定哈希函数的冲突率，使用 std::map 是最稳妥的选择；如果你追求极致速度，unordered_map 或手动实现 Trie 树会更优。加油！