星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

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

posted on 2017-08-23 15:54:29 | under 题解 |

pb_ds大法好

这里提供一个正儿八经的不用手写的哈希表——pb_ds库里的hash_table。

因为map内部排了序,所以会慢一些,而hash_table就和手写的几乎差不多了。

当然在我的代码中,把getline换掉应该会更快一些。

使用pb_ds库的hash_table需要包含两个头文件,其实我觉得pb_ds库最难的就是背头文件了

上代码。

#include<cstdio>
#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define f(i,a,b) for(register int i=int(a);i<=int(b);++i)
using namespace std;
__gnu_pbds::cc_hash_table<string,int>ht;//或者gp_hash_table,貌似慢一点 
int main()
{
    int n,sum=0;
    string s,instead;
    scanf("%d",&n);getline(cin,instead);
    f(i,1,n)
    {
        getline(cin,s);
        if(!ht[s])ht[s]=1,++sum;
    }
    printf("%d\n",sum);
}