0x14 hash

被虐爆了 cry 我的hash是真的菜啊。。。

poj3349 肝了一个上午心态崩了。。。一上午fail了42次我的天，一开始搞了个排序复杂度多了个log，而且是那种可能不同值相等的hash，把12种情况枚举，TLE了，然后就用了那种栈循环的hash，又T又W，期间大力搞大质数想要各个不同的雪花hash值不同，然后改成链表，最后一怒之下把最小表示法删了换暴力就A了。。想了想是因为我以为它的角度不会重复然后就偷了一波懒。。。这道题告诉我，假如重复还是得管的。。。hash应该作为一个筛选的工具。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

int next[],last[];

int len,hash[][],key[];

int c[];

bool check(int k)

{

    for(int i=;i<=;i++)

    {

        bool bk=true;

        for(int j=;j<=;j++)

            if(hash[k][j]!=c[(i+j-)%+]){bk=false;break;}

        if(bk==true)return true;

    }

    for(int i=;i<=;i++)

    {

        bool bk=true;

        for(int j=;j<=;j++)

            if(hash[k][j]!=c[(i+(-j+)-)%+]){bk=false;break;}

        if(bk==true)return true;

    }

    return false;

}

bool calc()

{

    int d=;

    for(int i=;i<=;i++)d+=c[i];

    int x=d%;

    for(int k=last[x];k;k=next[k])

        if(key[k]==d&&check(k)==true)return true;

    key[++len]=d;

    for(int i=;i<=;i++)hash[len][i]=c[i];

    next[len]=last[x];

    last[x]=len;

    return false;

}

int main()

{

    int n;

    scanf("%d",&n);len=;memset(last,,sizeof(last));

    memset(key,,sizeof(key));

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=;j++)scanf("%d",&c[j]);

        if(calc()==true){printf("Twin snowflakes found.\n");return ;}

    }

    printf("No two snowflakes are alike.\n");

    return ;

}

poj3349

兔子与兔子这个还是简单一点的，加深了对于mod之后的运算的满足的理解吧。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

int s[],Bin[];

char ss[];

int main()

{

    scanf("%s",ss+);int len=strlen(ss+);

    s[]=;Bin[]=;

    for(int i=;i<=len;i++)

        Bin[i]=Bin[i-]*, s[i]=s[i-]+Bin[i]*(ss[i]-'a');

    int Q,l,r;

    scanf("%d",&Q);

    while(Q--)

    {

        scanf("%d%d",&l,&r);

        int d1=(s[r]-s[l-])*Bin[len-r];

        scanf("%d%d",&l,&r);

        int d2=(s[r]-s[l-])*Bin[len-r];

        if(d1==d2)printf("Yes\n");

        else printf("No\n");

    }

    return ;

}

兔子和兔子

poj3974 马拉车原问题多个log的hash做法。。就是对于每个点二分回文的长度，然后判断是否匹配

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

int len;

int Bin[],zh[],fh[];

bool check(int i,int mid)

{

    int l1=i-mid+,r1=i;

    int l2=i,r2=i+mid-;

    int d1=(zh[r1]-zh[l1-])*Bin[len-r1];

    int d2=(fh[l2]-fh[r2+])*Bin[l2-];

    return d1==d2;

}

bool check2(int i,int mid)

{

    int l1=i-mid+,r1=i;

    int l2=i+,r2=(i+)+mid-;

    int d1=(zh[r1]-zh[l1-])*Bin[len-r1];

    int d2=(fh[l2]-fh[r2+])*Bin[l2-];

    return d1==d2;

}

char ss[];

int main()

{

    int T_T=;

    while(scanf("%s",ss+)!=EOF)

    {

        len=strlen(ss+);

        if(ss[]=='E'&&ss[]=='N'&&ss[]=='D'&&len==)break;

        printf("Case %d: ",++T_T);

        Bin[]=;zh[]=;fh[len+]=;

        for(int i=;i<=len;i++)

            Bin[i]=Bin[i-]*, zh[i]=zh[i-]+Bin[i]*(ss[i]-'a'+);

        for(int i=len;i>=;i--)

            fh[i]=fh[i+]+Bin[len-i+]*(ss[i]-'a'+);

        int mmax=;

        for(int i=;i<=len;i++)

        {

            int l=,r=min(i,len-i+),ans=;

            while(l<=r)

            {

                int mid=(l+r)/;

                if(check(i,mid)==true)

                {

                    ans=mid;

                    l=mid+;

                }

                else r=mid-;

            }

            mmax=max(mmax,ans*-);

            if(i!=len)

            {

                l=,r=min(i,len-(i+)+),ans=;

                while(l<=r)

                {

                    int mid=(l+r)/;

                    if(check2(i,mid)==true)

                    {

                        ans=mid;

                        l=mid+;

                    }

                    else r=mid-;

                }

                mmax=max(mmax,ans*);

            }

        }

        printf("%d\n",mmax);

    }

    return ;

}

poj3974

后缀数组后缀数组原问题多个log的hash做法，做到这题感觉hash写得很顺啊，调都没调就过了，具体做法是这样的，对于sa，我归并排序下标（其实就是对应后缀），然后用二分+hash搞出要比较大小的后缀的前缀，比较它们前缀的后一位就知道那个后缀较小了。height同理二分+hash可得

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

int len;char ss[];

int ha[],Bin[];

bool check(int l1,int l2,int L)

{

    int r1=l1+L-,r2=l2+L-;

    int d1=(ha[r1]-ha[l1-])*Bin[len-r1];

    int d2=(ha[r2]-ha[l2-])*Bin[len-r2];

    return d1==d2;

}

bool bijiao(int x,int y)

{

    int l=,r=len-max(x,y)+,ans=;

    while(l<=r)

    {

        int mid=(l+r)/;

        if(check(x,y,mid)==true)

        {

            ans=mid;

            l=mid+;

        }

        else r=mid-;

    }

    return ss[x+ans]<ss[y+ans];

}

int id[],tt[];

void mergesort(int l,int r)

{

    if(l==r)return ;

    int mid=(l+r)/;

    mergesort(l,mid);mergesort(mid+,r);

    int i=l,j=mid+,p=l;

    while(i<=mid&&j<=r)

    {

        if(bijiao(id[i],id[j])==true)

            tt[p++]=id[i++];

        else

            tt[p++]=id[j++];

    }

    while(i<=mid)tt[p++]=id[i++];

    while(j<=r)  tt[p++]=id[j++];

    for(int i=l;i<=r;i++)id[i]=tt[i];

}

int main()

{

    scanf("%s",ss+),len=strlen(ss+);

    Bin[]=;

    for(int i=;i<=len;i++)

        Bin[i]=Bin[i-]*, ha[i]=ha[i-]+Bin[i]*(ss[i]-'a'+);

    for(int i=;i<=len;i++)id[i]=i;

    mergesort(,len);

    for(int i=;i<len;i++)printf("%d ",id[i]-);

    printf("%d\n",id[len]-);

    printf("");

    for(int i=;i<=len;i++)

    {

        int l=,r=len-max(id[i-],id[i])+,ans=;

        while(l<=r)

        {

            int mid=(l+r)/;

            if(check(id[i-],id[i],mid)==true)

            {

                ans=mid;

                l=mid+;

            }

            else r=mid-;

        }

        printf(" %d",ans);

    }

    printf("\n");

    return ;

}

后缀数组

总结一下，hash的用途在判定相等而不支持大小比较，好像很适配于二分把问题转成判定性问题以后？

补基础的伪老年选手yzh好菜啊，一天才一章。。

巴特西

0x14 hash

最新文章

热门文章