题解0011：图书管理（哈希、vector）
信奥一本通——哈希 里的例题2
题目链接：//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 }
完美结束
