You've successfully subscribed to ムえのBLOG
Great! Next, complete checkout for full access to ムえのBLOG
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.

题解 P3370 【【模板】字符串哈希】

. 1 min read

pb_ds 大法好

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

对比起stl是真心快

pbds hash table官网pbds hash table

pbds提供两种算法cc_hash_tablegp_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;
}



本站总访问量 正在加载今日诗词....