数据结构之哈希（poj3274）

迈不过友情╰ 2022-08-25 12:53 118阅读 0赞

寒假集训的时候学习了一下哈希，但是一直没有练习，这几天找了几道哈希的题目，发现忘的差不多了。

做了几道题之后发现哈希真的是一个很高效的数据结构，体验到了数据结构的强大。

构建哈希表示为了能够更高效率的查找，还记得小学的时候查字典吗？其实哈希就相当于那样一个东西，他把数据按照一定的哈希函数生成一个键值，然后把所有键值相同的存在一个相同的数组中，然后查找的时候首先找它的键值，找到键值之后只用在键值相同的这个数组中查找就行了。

原理就是这样，要想真正了解哈希表，还要几道题目练习，首先哈希表可以用二维结构体存储，因为你不知道每一个键值后面有多少个元素，所以用二维结构体存储的话后面一维的大小不好确定，而且有些题目对内存的要求比较严格，每个都开那么大的话会浪费很多的内存，所以一般都会用一个数组链表。但是链表又不好写。

那么vector就能解决这个问题，因为vector是一个动态的存储结构，下面来看一道题目。

![0_13120337780RMP.gif][]

数组sum\[i\]\[j\]表示从第1到第i头cow属性j的出现次数。

所以题目要求等价为:

求满足

sum\[i\]\[0\]-sum\[j\]\[0\]=sum\[i\]\[1\]-sum\[j\]\[1\]=.....=sum\[i\]\[k-1\]-sum\[j\]\[k-1\] (j<i)

中最大的i-j

将上式变换可得到

sum\[i\]\[1\]-sum\[i\]\[0\] = sum\[j\]\[1\]-sum\[j\]\[0\]

sum\[i\]\[2\]-sum\[i\]\[0\] = sum\[j\]\[2\]-sum\[j\]\[0\]

......

sum\[i\]\[k-1\]-sum\[i\]\[0\] = sum\[j\]\[k-1\]-sum\[j\]\[0\]

令C\[i\]\[y\]=sum\[i\]\[y\]-sum\[i\]\[0\] (0<y<k)

初始条件C\[0\]\[0~k-1\]=0

所以只需求满足C\[i\]\[\]==C\[j\]\[\] 中最大的i-j，其中0<=j<i<=n。

C\[i\]\[\]==C\[j\]\[\] 即二维数组C\[\]\[\]第i行与第j行对应列的值相等，

那么原题就转化为**求C数组中 相等且相隔最远的两行的距离i-j**。

这里的这个转化是很重要的，没办法转化的话就别想哈希了。题目坑点比较多。wa了好多次之后才ac。

ac代码：

#include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <vector>
    using namespace std;
    const int N = 15000;
    const int Mod = 14997;
    struct Node
    {
        int a[35];
        int count;
    };
    
    vector<Node> hash[N];
    
    bool solve(Node x,Node y,int k)
    {
        for(int i=0;i<k;i++)
        {
            if(x.a[i]!=y.a[i])
                return false;
        }
        return true;
    }
    int main()
    {
        int n,k;
        while(~scanf("%d%d",&n,&k))
        {
            int cmp[35]={0};
            int max=0;
            for(int i=0;i<n;i++)
            {
                int x;
                scanf("%d",&x);
                for(int j=0;j<k;j++)
                {
                    cmp[j]+=x%2;
                    x/=2;
                }
                Node ans;
                int sum=0,flag=1;
                ans.a[0]=0;
                for(int j=1;j<k;j++)
                {
                    ans.a[j]=cmp[j]-cmp[0];
                    if(ans.a[j]!=ans.a[j-1])
                        flag=0;
                    sum=(sum+(ans.a[j]*(j+7)))%Mod;
                }
                if(flag)
                {
                    if((i+1)>max)
                        max=i+1;
                }
                sum=(sum+15000)%Mod;
                ans.count=i;
                hash[sum].push_back(ans);
            }
            if(n==1)
            {
                int ok=1;
                for(int i=1;i<k;i++)
                {
                    if(cmp[i]!=cmp[i-1])
                        ok=0;
                }
                if(ok)
                    printf("1\n");
                else
                    printf("0\n");
                hash[0].clear();
                continue;
            }
            if(max>1)  //剪枝
            {
                printf("%d\n",max);
                continue;
            }
            for(int i=0;i<15000;i++)
            {
                if(hash[i].size()>1)
                {
                    for(int j=0;j<hash[i].size()-1;j++)
                    {
                        for(int f=j+1;f<hash[i].size();f++)
                        {
                            if(solve(hash[i][j],hash[i][f],k))
                            {
                                int zhi=fabs(hash[i][j].count-hash[i][f].count);
                                if(zhi>max)
                                    max=zhi;
                            }
                        }
                    }
                }
                hash[i].clear();
            }
            printf("%d\n",max);
        }
        return 0;
    }

[0_13120337780RMP.gif]: /images/20220824/e8aa27bd86be47129390309be99ef952.png