hash_map

　　点开一道第是自己oj的第440大关，想a了，一直想却无果，学长一句点醒，开始写hash。

hash_map

关于这道题呢很无语了，两天卡在这上面，而且有些dalao不到20min就a了。我太菜了。

所以要深入讨论这道题啊，这时oj上的hash最后一题了，仔细总结！

首先我们发现求出前缀和后有一个n^2暴力枚举的做法可这道题n<=100000，很明显这是要我们搞出来一个nlog(n)的做法才行。

考虑优化，首先我们差分一下就很明显的发现我们可以在没次枚举到当前情况的时候和上一次的情况联系起来。

如果当前差分结果和上次（不知道是哪次）出现的结果一致，那么，就可以更新答案了。

不懂的话可以自己做一个关于样例的前缀和差分数组，一看就出来了。

那么当前情况拿什么来保存。数字太大了我们可以hash一下。（或者map

这就有了我82分代码：

//#include<bits/stdc++.h>

#include<iomanip>

#include<utility>

#include<cctype>

#include<vector>

#include<deque>

#include<map>

#include<stack>

#include<queue>

#include<bitset>

#include<set>

#include<cstdlib>

#include<algorithm>

#include<iostream>

#include<cstdio>

#include<ctime>

#include<cmath>

#include<cstring>

#include<string>

#define INF 2147483646

#define mod 100007

using namespace std;

inline long long read()

{

    long long x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void put(long long x)

{

    x<?x=-x,putchar('-'):;

    long long num=;char ch[];

    while(x)ch[++num]=x%+'',x/=;

    num==?putchar(''):;

    while(num)putchar(ch[num--]);

    putchar('\n');return;

}

const long long MAXN=;

long long a[MAXN];

long long lin[MAXN],nex[MAXN],ver[MAXN],e[MAXN],len=;

long long n,k,ans=;

long long b[MAXN][];

void hash(long long h,long long x,long long y)

{

    ver[++len]=h;

    nex[len]=lin[x];

    lin[x]=len;

    e[len]=y;

}

long long find(long long xx)

{

    long long x=xx%mod;

    if(lin[x]==)return -;

    for(long long i=lin[x];i;i=nex[i])if(e[i]==xx)return ver[i];

    return -;

}

void transform(long long h,long long x)

{

    long long u=,minn=MAXN;

    for(long long u=;u<=k;u++)

    {

        if(x&)b[h][u]=b[h-][u]+;

        else b[h][u]=b[h-][u];

        minn=min(b[h][u],minn);

        x=x>>;

    }

    for(long long i=;i<=k;i++)

        b[h][i]-=minn;

    long long cnt=;

    for(long long i=,t=;i<=k;i++,t=t*)cnt+=b[h][i]*t;

    long long w=find(cnt);

    if(w==-)hash(h,cnt%mod,cnt);

    else ans=max(ans,h-w);

    //cout<<cnt<<endl;

    return;

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();k=read();

    hash(,,);

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

    {

        a[i]=read();

        transform(i,a[i]);

    }

    put(ans);

    return ;

}

很棒的代码对不对，但是只有82分，经过2h的打表发现就算采用挂链法也会导致明明不同的元素访问到。如 0（12）1这三个二进制数=25 而5(0)5=25;不一样但是hash后值是一样的。

则么办hash之后更加精细的判断即可。这样复杂度会很高。

//#include<bits/stdc++.h>

#include<iomanip>

#include<utility>

#include<cctype>

#include<vector>

#include<deque>

#include<map>

#include<stack>

#include<queue>

#include<bitset>

#include<set>

#include<cstdlib>

#include<algorithm>

#include<iostream>

#include<cstdio>

#include<ctime>

#include<cmath>

#include<cstring>

#include<string>

using namespace std;

inline long long read()

{

    long long x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void put(long long x)

{

    x<?x=-x,putchar('-'):;

    long long num=;char ch[];

    while(x)ch[++num]=x%+'',x/=;

    num==?putchar(''):;

    while(num)putchar(ch[num--]);

    putchar('\n');return;

}

const long long MAXN=;

const long long INF=;

const long long mod=;

vector<long long>q[MAXN];

long long a[MAXN];

long long lin[MAXN],nex[MAXN],ver[MAXN],e[MAXN],len=;

long long n,k,ans=;

long long b[MAXN][];

void hash(long long h,long long x,long long y,long long c[])

{

    ver[++len]=h;

    nex[len]=lin[x];

    lin[x]=len;

    e[len]=y;

    for(long long i=;i<=k;++i)q[len].push_back(c[i]);

}

long long find(long long xx,long long c[])

{

    long long x=xx%mod;

    if(lin[x]==)return -;

    for(long long i=lin[x];i;i=nex[i])

    {

        if(e[i]==xx)

        {

            bool flag=;

            for(long long j=;j<=k;++j)if(c[j]!=q[i][j-]){flag=;break;}

            if(flag==)return ver[i];

        }

    }

    return -;

}

void transform(long long h,long long x)

{

    long long u=,minn=INF;

    for(long long u=;u<=k;++u)

    {

        if(x&)b[h][u]=b[h-][u]+;

        else b[h][u]=b[h-][u];

        minn=min(b[h][u],minn);

        x=x>>;

    }

    for(long long i=;i<=k;++i)b[h][i]-=minn;

    long long cnt=;

    for(long long i=,t=;i<=k;++i,t=t<<)cnt+=b[h][i]*t;

    long long w=find(cnt,b[h]);

    if(w==-)hash(h,cnt%mod,cnt,b[h]);

    else ans=max(ans,h-w);

    return;

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();k=read();

    hash(,,,b[]);

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

    {

        a[i]=read();

        transform(i,a[i]);

    }

    put(ans);

    return ;

}

这个代码绝对很完美了，但是洛谷是可以通过的但是呢，oj上会超时的。

那么这个hash过于复杂，则么办呢。

我们可以使用map。映射直接映射到map上就会省很多的操作。

//#include<bits/stdc++.h>

#include<iomanip>

#include<utility>

#include<cctype>

#include<vector>

#include<deque>

#include<map>

#include<stack>

#include<queue>

#include<bitset>

#include<set>

#include<cstdlib>

#include<algorithm>

#include<iostream>

#include<cstdio>

#include<ctime>

#include<cmath>

#include<cstring>

#include<string>

#define INF 2147483646

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

  return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline int read()

{

    int x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

inline void put(int x)

{

    x<?x=-x,putchar('-'):;

    int num=;char ch[];

    while(x)ch[++num]=x%+'',x/=;

    num==?putchar(''):;

    while(num)putchar(ch[num--]);

    putchar('\n');return;

}

const int MAXN=;

int n,k,ans=;

int a[MAXN];

struct wy//闻道玉门犹被遮应将性命逐轻车

{

    int h;

    int c[];

}t[MAXN];

map<string,int>f;

string w;

int main()

{

    //freopen("1.in","r",stdin);

    n=read();k=read();

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

    {

        w="";int flag=;

        a[i]=read();int minn=INF;

        t[i].h=i;int x=a[i];

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

        {

            t[i].c[j]+=t[i-].c[j];

            if(x&)t[i].c[j]+=;

            x=x>>;minn=min(minn,t[i].c[j]);

        }

        for(int j=;j<=k;j++){t[i].c[j]-=minn,w+=t[i].c[j]+'';if(t[i].c[j]!=)flag=;}

        int sum=f[w];

        if(flag==)ans=max(ans,i);

        if(sum)ans=max(ans,i-sum);

        else f[w]=i;

    }

    put(ans);

    return ;

}

这下复杂度再次大大下降。然后oj也是可以顺利通过的，但是这里学长有一个使用了结构替友元函数的。

学习更多的东西，所以这里有一个友元函数的代码：

//#include<bits/stdc++.h>

#include<iomanip>

#include<utility>

#include<cctype>

#include<vector>

#include<deque>

#include<map>

#include<stack>

#include<queue>

#include<bitset>

#include<set>

#include<cstdlib>

#include<algorithm>

#include<iostream>

#include<cstdio>

#include<ctime>

#include<cmath>

#include<cstring>

#include<string>

#define INF 2147483646

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

  return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline int read()

{

    int x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

inline void put(int x)

{

    x<?x=-x,putchar('-'):;

    int num=;char ch[];

    while(x)ch[++num]=x%+'',x/=;

    num==?putchar(''):;

    while(num)putchar(ch[num--]);

    putchar('\n');return;

}

const int MAXN=;

int n,k,ans=;

int a[MAXN];

struct wy//闻道玉门犹被遮应将性命逐轻车

{

    int h;

    int c[];

    friend bool operator <(wy x,wy y)

    {

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

            if(x.c[i]!=y.c[i])return x.c[i]<y.c[i];

        return ;

    }

}t[MAXN];

map<wy,int>f;

int main()

{

    //freopen("1.in","r",stdin);

    n=read();k=read();

    f[t[]]=;

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

    {

        a[i]=read();int minn=INF;

        t[i].h=i;int x=a[i];

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

        {

            t[i].c[j]+=t[i-].c[j];

            if(x&)t[i].c[j]+=;

            x=x>>;minn=min(minn,t[i].c[j]);

        }

        for(int j=;j<=k;j++)t[i].c[j]-=minn;

        int sum=f[t[i]];

        if(sum)ans=max(ans,i+-sum);

        else f[t[i]]=i+;

    }

    put(ans);

    return ;

}

这个代码和刚刚的差不多，但是是对结构体的升华操作要学！

提交到poj上第一个AC代码 TLE 第二个 TLE 第三个 TLE 全部都阵亡了，不服，教学长的代码，然后A了。这wy大佬是真的强啊。

经过调查不管如何进行读入、输出、卡常的优化都是TLE，然后感觉是map第一个关键字的原因的问题，因为学长的是小hash和map的结合体。

所以这道题可以考虑抄一波学长的代码他的第一个关键字是long long 类型的，所以应该要快（我也真找不出什么原因了。

而且他的hash是好hash 比我的第一个hash好上不少。完全不带重复的所以这个代码也应该是可以优化我的代码的。

所以他的代码经过我的翻译如下：

//#include<bits/stdc++.h>

#include<iomanip>

#include<utility>

#include<cctype>

#include<vector>

#include<deque>

#include<map>

#include<stack>

#include<queue>

#include<bitset>

#include<set>

#include<cstdlib>

#include<algorithm>

#include<iostream>

#include<cstdio>

#include<ctime>

#include<cmath>

#include<cstring>

#include<string>

#define ll long long

#define INF 2147483646

using namespace std;

char buf[<<],*fs,*ft;

inline char getc()

{

  return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline int read()

{

    int x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return x*f;

}

inline void put(int x)

{

    x<?x=-x,putchar('-'):;

    int num=;char ch[];

    while(x)ch[++num]=x%+'',x/=;

    num==?putchar(''):;

    while(num)putchar(ch[num--]);

    putchar('\n');return;

}

const int MAXN=,maxn=;

int n,k,ans=;

int a[MAXN][];

map<ll,int>f;

int find(int x)

{

    ll sum=;

    for(int i=;i<=k;i++)sum=sum*maxn+1ll*a[x][i];

    if(f[sum]==&&sum!=)f[sum]=x;

    return f[sum];

}

int main()

{

    freopen("1.in","r",stdin);

    n=read();k=read();

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

    {

        int t=,x=read();

        int minn=INF;

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

        {

            a[i][j]=x&;a[i][j]+=a[i-][j];

            x=x>>;

            minn=min(minn,a[i][j]);

        }

        for(int j=;j<=k;j++)a[i][j]-=minn;

        ans=max(ans,i-find(i));

    }

    put(ans);

    return ;

}

很妙的hash和map的嵌套~！

刚好的map接数字较大的集合，这样就实现了快速查找。

不用map可就接不上了。总结：所以必须要用map来进行精度较高但是比结构图或者string快的东西。累了一天，了。

明天加油！ヾ（◍°∇°◍）ﾉﾞ

相关文章