三校集训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<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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇