题意
图书管理是一件十分繁杂的工作, 在一个图书馆中每天都会有许多新书加入. 为了更方便的管理图书 (以便于帮助想要借书的客人快速查找他们是否有他们所需要的书), 我们需要设计一个图书查找系统.
该系统需要支持 2 种操作:
add(s) 表示新加入一本书名为 s 的图书.
find(s) 表示查询是否存在一本书名为 s 的图书.
分析
参照 https://www.cnblogs.com/jklover/p/10185164.html 的题解.
将每个字符串通过计算 hash 转化为整数, 开一个桶记录是否出现过即可.
代码
这程序连样例都过不了还能 A 题?
- #include<bits/stdc++.h>
- #define rg register
- #define il inline
- #define co const
- template<class T>il T read()
- {
- rg T data=0;
- rg int w=1;
- rg char ch=getchar();
- while(!isdigit(ch))
- {
- if(ch=='-')
- w=-1;
- ch=getchar();
- }
- while(isdigit(ch))
- {
- data=data*10+ch-'0';
- ch=getchar();
- }
- return data*w;
- }
- template<class T>il T read(rg T&x)
- {
- return x=read<T>();
- }
- typedef long long ll;
- co int Base=233;
- co int P1=19260817,P2=999983;
- bool Hashmap1[P1+1],Hashmap2[P2+10];
- char buf[300];
- int main()
- {
- // freopen(".in","r",stdin);
- // freopen(".out","w",stdout);
- int n;
- read(n);
- while(n--)
- {
- char op[5];
- scanf("%s",op);
- if(op[0]=='a')
- {
- scanf("%s",buf);
- int len=strlen(buf),hash1=0,hash2=0;
- for(int i=0;i<len;++i)
- hash1=((ll)hash1*Base+buf[i])%P1,hash2=((ll)hash2*Base+buf[i])%P2;
- Hashmap1[hash1]=true;
- Hashmap2[hash2]=true;
- }
- else
- {
- scanf("%s",buf);
- int len=strlen(buf),hash1=0,hash2=0;
- for(int i=0;i<len;++i)
- hash1=((ll)hash1*Base+buf[i])%P1,hash2=((ll)hash2*Base+buf[i])%P2;
- puts(Hashmap1[hash1]&&Hashmap2[hash2]?"yes":"no");
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2935735.html