P76056 不重复用户名 — 题解

专题： STL
适用题目： 新生 OJ 本地题包中的 P76056，不要直接用于外站同名题。

解题思路

用 map<string,int> 记录每个原始用户名已经出现几次：首次输出 OK，之后附加此前出现次数。

复杂度

时间 $O(n\log n\cdot L)$，空间 $O(nL)$。

易错点

不要拿新生成的用户名当作下次查重的原始键。

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    map<string,int>seen;
    while(n--){
        string s;
        cin>>s;
        int &c=seen[s];
        if(c==0)cout<<"OK"<<nl;
        else cout<<s<<c<<nl;
        c++;
    }
    return 0;
}

为什么只提供 C++： 本题专题要求使用 STL 容器或算法，C 语言没有 STL；C 可以用手写数据结构解决，但不属于本专题的教学目标。

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。