pb_ds 大法好

看到没有人用pbds就来普及一篇

对比起stl是真心快

pbds hash table官网pbds hash table

pbds提供两种算法cc_hash_table和gp_hash_table

cc_hash_table是拉链法

gp_hash_table是查探法

gp的结果是：用时: 641ms / 内存: 19628KB

cc的结果是：用时: 611ms / 内存: 11404KB

pbds的hash是支持find和operator的

不过使用时要注意命名空间，string是std的

typedef basic_string<char> string;

所以一定要当心

直接上代码：

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define pbds __gnu_pbds
using namespace std;

pbds::gp_hash_table<string,int> h;
/*
cc的定义是
pbds::cc_hash_table<string,int> h;
*/
int main()
{
    int n,ans;
    cin>>n;
    ans=n;
    for (int i=1;i<=n;i++){
        string a;
        cin>>a;
        h[a]++;
        if (h[a]>1){ans--;h[a]=1;}
    }
    cout<<ans<<endl;
    return 0;
}