三校集训Part2 NBCX Day2 XVII 题解

题意

有$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

#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<LV1>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;
}