pbds中hash_table小结

今天做了P1738 洛谷的文件夹。这道题本身挺水，其实map就行了，但我菜所以还用了pbds里的hash_table，这篇文章主要是记录一下hash_table的用法。

hash_table食用方法

先引入头文件：

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>

然后是pbds的命名空间：

using namespace __gnu_pbds;

定义hash_table：

gp_hash_table<string,int> mp;

使用的时候像php数组一样用就行了：

map["akioi"]=1

相关题目

洛谷1738 洛谷的文件夹

将每一个文件夹的名字转换成数值，然后连边判断即可。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

struct Edge{
    int next,to;
} edge[200005];
int n,cnt,mp_cnt,ans,head[200005];
string s;
gp_hash_table<string,int> mp;

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>s;
        int len=s.length(),stat=1,last=0;
        for (int j=1;j<=len;j++)
        {
            if (s[j]!='/' && j!=len) continue;
            string now=s.substr(stat,j-stat);
            if (!mp[now]) mp[now]=++mp_cnt;
            bool have=0;
            for (int k=head[last];k;k=edge[k].next)
            {
                int y=edge[k].to;
                if (y==mp[now])
                {
                    have=1;
                    break;
                }
            }
            if (!have)
            {
                add(last,mp[now]);
                ans++;
            }
            last=mp[now];
        }
        printf("%d\n",ans);
    }
    return 0;
}