题解0011：图书管理（哈希、vector）

信奥一本通——哈希里的例题2

题目链接：http://ybt.ssoier.cn:8088/problem_show.php?pid=1456

题目描述：两个命令，一个是进一本名字为s的图书，一个是找现有的图书里有没有名字为s的图书，如果有输出 “噎死” “yes”，没有输出 “no” 。

这道题基础思路是用哈希，将书名的字符串转换成相应的哈希值，再进行查找。

但是

书名的长度最长200，这么大的字符串哈希值看着都腿软。

那怎么办呢？

在c++中有一种数据结构叫vector，是一个动态2维数组，可以将一维的数向下扩充成2维（甚至三维）。

那么，我们就可以在哈希的基础上，用vector进行进一步判断了。

将某串的哈希值模上个质数，然后将原串存在相应 vector [哈希值] 的地方

就像这样：

v[we/*相应哈希值*/].push_back(a);

下面完整代码：

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int b=31;//工具质数

 4 int we,q;

 5 string a,c;

 6 vector<string> v[30000];//必须是string类型的

 7 int main(){

 8     int n;

 9     cin>>n;

10     for(int i=0;i<n;i++){

11         cin>>c;

12         if(c=="add"){

13             getline(cin,a);//因为有空格，所以用这个

14             we=1;

15             for(int j=0;j<a.size();j++){

16                 we=(we*b+(long long)a[j])%23333;//求哈希值

17             }

18             v[we].push_back(a);//将字符串存进去

19         }

20         if(c=="find"){

21             getline(cin,a);

22             we=1;

23             for(int j=0;j<a.size();j++){

24                 we=(we*b+(long long)a[j])%23333;

25             }//同上

26             q=0;

27             for(int j=0;j<(int)v[we].size();j++){

28                 if(v[we][j]==a){//判断字符串是不是相等

29                     cout<<"yes"<<endl;

30                     q=1;

31                     break;//这里可是坑坏了，如果不写break它会打出很多"yes"，要不然就在上面查重

32                 }

33             }

34             if(q==0){//变量控制

35                 cout<<"no"<<endl;

36             }

37         }

38     }

39 }

完美结束

巴特西

题解0011：图书管理（哈希、vector）

最新文章

热门文章