题意
有$n$个长度为$32$的只包含小写字母的字符串，问每个字符串读入时它之前有没有出现过？
输出$n$行，每行输出$Yes$或$No$。
时间限制：$6s$
空间限制：$2M$
思路
出题人好心地帮我们把$2M$标红了…
考虑使用$map$，虽然$map$的准确性高，但是不仅常数大（但出题人好心地给了$6s$）空间上也会$MLE$。
考虑使用$hash$，虽然$hash$的空间消耗小（小？？？），但是准确性很低，在大数据时准确率几乎为$0$。
考虑使用布隆过滤器（Bloom Filter）。（什么鬼？？？我不会：百度百科
因为我太菜了又不想学，于是就做了一个玄学方法。
首先把输入数据分为$10$组，每组划分的依据是$hash$第一次过后的$hash$值。
然后$hash$数组就可以减少$10$了，O(∩_∩)O~~
接着对于每一组再一次$hash$，并且把这第二次的$hash$值作为$hash$邻接表的$son$值（即$hash$匹配值，原为字符串）
然后都是$hash$的操作啦~~~
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 |
#include<algorithm> #include<bitset> #include<complex> #include<deque> #include<exception> #include<fstream> #include<functional> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<iterator> #include<limits> #include<list> #include<locale> #include<map> #include<memory> #include<new> #include<numeric> #include<ostream> #include<queue> #include<set> #include<sstream> #include<stack> #include<stdexcept> #include<streambuf> #include<string> #include<typeinfo> #include<utility> #include<valarray> #include<vector> #include<cctype> #include<cerrno> #include<cfloat> #include<ciso646> #include<climits> #include<clocale> #include<cmath> #include<csetjmp> #include<csignal> #include<cstdarg> #include<cstddef> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> using namespace std; #define N 100001 #define re register #define S 8192 char buf[S],*L,*R; #define pc putchar inline int gc(){return (L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++);} class Quick_Input_Output{ public: inline int read(){ int res=0,f=1;char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();} while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc(); return res*f; } inline void write(int x){ if(x<0) pc('-'),x=-x; if(x<10) pc(x+'0'); else write(x/10),pc(x%10+'0'); } // #undef gc #undef pc }I; #define File freopen("xvii.in","r",stdin);freopen("xvii.out","w",stdout); #define ReFile fclose(stdin);freopen("xvii.in","r",stdin); bitset<480001> ans; class Hash{ private: int fir[N],nxt[65000],son[65000],tot; public: inline int get(string str,int base,int Md){//hash re int s=0; for(int i=0;i<32;i++) s=((long long)s*base+str[i]-'a')%Md; return s; } inline void clean(){//清空 memset(fir,0,sizeof(fir));tot=0; } inline void add(int x,int y){//邻接表 ++tot; nxt[tot]=fir[x]; fir[x]=tot; son[tot]=y; } inline void Work(int i,int V1,int V2){//先搜索，没有则加入，有则标记答案 for(int to,j=fir[V1];j;j=nxt[j]){ to=son[j]; if(to==V2){ ans.set(i); break; } } if(ans.test(i)==0) add(V1,V2); } }H; string str; int n,V1,V2; char c; signed main(){ File ans.reset(); srand(time(NULL)); re int L,R,i,j; for(L=0;L<1000000;L+=100000){//分成10个区间 H.clean(); R=L+100000-1; n=I.read(); for(i=1;i<=n;i++){ c=gc();str=""; while(c<'a'&&c>'z') c=gc(); for(j=0;j<32;j++){ str+=c;c=gc(); } V1=H.get(str,233,1000000);//第一次hash V2=H.get(str,114514,1000000009);//第二次hash if(V1<L||V1>R) continue ;//是否在区间内 V1-=L;//减去边界值，防止越界 H.Work(i,V1,V2);//计算答案 } ReFile //再次打开文件（即下一个区间 } for(i=1;i<=n;i++) puts(ans.test(i)==0?"No":"Yes");//三位运算符 return 0; } |
