pbds中hash_table小结

access_time    bookmark 笔记    comment 0 条评论   

今天做了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;
}

新评论

account_circle
称呼不能为空
email
邮箱格式不合法
link
网站格式不合法
textsms
内容不能为空

第一次提交或含有敏感词汇的评论将在审核后显示。