📝 题目大意

给定 $N$ 个字符串，按顺序处理每个字符串 $S_i$：若 $S_i$ 在之前从未出现过，直接输出 $S_i$；若出现过 $X$ 次，则输出 $S_i(X)$ 的格式。$X$ 是 $S_i$ 在 $S_1 \dots S_{i-1}$ 中的出现次数。

💡 解题思路

1. 题目分析：$N \le 2 \times 10^5$，每个字符串长度 $\le 10$。直接对每个 $S_i$ 扫描前面所有 $S_j$ 是 $O(N^2)$ 的，会超时。需要一种能快速查询"某个字符串之前出现过几次"的数据结构。

2. 算法推导：

   • 使用哈希表 unordered_map<string, int> cnt，以字符串为键，记录该字符串在当前时刻的已出现次数（不包括当前这一轮）。
   • 对于每个 $S_i$：
     • 查询 cnt[S_i]：若为 $0$，说明是首次出现，直接输出 $S_i$。
     • 若 $>0$，说明之前已出现过 $cnt[S_i]$ 次，输出 $S_i(cnt[S_i])$。
     • 无论如何，输出后将 cnt[S_i] 加 $1$，表示该字符串又多出现了一次。
   • 关键点：cnt[s] 在输出时反映的是之前的出现次数，与题目要求 $X$ 的定义完全一致。输出后 ++ 保证了下次出现时 $X$ 正确。

3. 边界与细节：

   • 字符串仅由小写字母组成，可直接用 unordered_map 或 map。unordered_map 平均 $O(1)$ 查询，更优。
   • 注意计数更新的时机：必须先输出再 ++，否则会导致 $X$ 多算 $1$。
   • 输出格式：$X$ 用括号括起来，如 newfile(1)，不要遗漏括号。

⏱️ 复杂度分析

• 时间复杂度：$O(N)$，每个字符串的哈希表插入和查询均为期望 $O(1)$。
• 空间复杂度：$O(N)$，最坏情况下所有字符串互不相同，哈希表存储 $N$ 个键值对。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin >> N;
    unordered_map<string, int> cnt; // 记录每个字符串已经出现的次数（不含当前）
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        // 查询之前出现过几次
        if (cnt[s] == 0) {          // 首次出现，直接输出原字符串
            cout << s << endl;
        } else {                    // 非首次出现，输出 s(X) 格式
            cout << s << "(" << cnt[s] << ")" << endl;
        }
        cnt[s]++;                   // 更新出现次数，供后续使用
    }
    return 0;
}