set 的 count 时间复杂度貌似是大于 $\log n$ 的,而且极限数据下你的算法可以被卡成 $O(n^2 \log n)$ 的样子(所有询问都一样)。改成 map 映射好一些,可以通过。
by DitaMirika @ 2021-08-14 11:12:51
@[Most_Ima](/user/236862) 谢谢,但是map我没学过..
by AmaZingFantasy @ 2021-08-14 11:17:44
还是回头再说吧
by AmaZingFantasy @ 2021-08-14 11:18:17
@[安湛丰](/user/378220) 中间暴力改成二分可以过
by DitaMirika @ 2021-08-14 11:23:54
@[安湛丰](/user/378220) 还有你的hecheng写的是错的
by DitaMirika @ 2021-08-14 11:24:10
@[Most_Ima](/user/236862) hecheng问题已改正,感谢指教。
by AmaZingFantasy @ 2021-08-14 11:29:08
@[安湛丰](/user/378220) A掉了
加上二分,复杂度多一个 $\log$,但是不会被极限数据卡了(学完map你会发现这题简单多了)
```cpp
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
typedef long long l;
set<string>s;
string hecheng(string st,l shu){
string h="";
while(shu > 0){
h+=shu%10+48;
shu/=10;
}
reverse(h.begin(), h.end());//注意要加
return st+h;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
l n;
cin>>n;
for(l i=0;i<n;i++){
string st;
cin>>st;
int x=0;
if(s.count(st)==0){
cout<<"OK\n";
s.insert(st);
}else{
x=n;
int l=1,r=n;
while(l<=r){
int mid=(l+r)/2;
if(s.count(hecheng(st,mid)) == 0)x=min(x,mid),r=mid-1;
else l=mid+1;
}
string k=hecheng(st,x);
cout<<k<<"\n";
s.insert(k);
}
}
return 0;
}
```
by DitaMirika @ 2021-08-14 11:30:43
@[Most_Ima](/user/236862) `count` 显然是 $O(\log n)$ 的
by cyffff @ 2021-08-14 11:36:59
@[cyffff](/user/365127) 但是我听说过是 $O(\log n+ size)$ 的/jk
by DitaMirika @ 2021-08-14 11:39:04