POJ3274(哈希)

codeoosacm 2018-10-16 原文

第一篇博客emmm

根据kuangbin dalao的poj刷题指南做的

一道不是很简单的哈希题目

题意是求特征之和相同的第i头牛到第j头牛的max(j-i)

一开始是没有思路的，苦思冥想半天

然后（看了题解以后）手推公式：

num[i][1]+…+num[j][1]=num[i][2]+….+num[j][2]=num[i][k]+…+num[j][k];

①num[i][1]+…+num[j][1]=num[i][k]+…+num[j][k];

②sum[i][k]=sum[i-1][k]+num[i][k];

①，②=>sum[j][k]-sum[i][k]=sum[j][0]-sum[i][0];

=>sum[j][k]-sum[j][0]=sum[i][k]-sum[i][0];

所以对于sum矩阵，每个元素减去第一列

然后求sum矩阵相同的行的最大距离即可

二进制转化成k进制作为哈希值。

自己踩的坑如下：

(1)mod余数越界，调了好久

(2)矩阵每列元素减去第一列元素会导致最后的hash值可能是负的，要用abs把它变成正数

(3)search的时候不要找到就直接返回j值，要找到最后一个满足cmp的j值，因为前向星是倒着存的，而我们要的是最靠前的j值，越靠前，对于当前i值来说，距离越大,所以最晚出现的值是符合条件的

(4)脑残错误：

for(int i=1;i<=n;i++)
 71     {
 73         for(int j=1;j<=k;j++)
 74         {
 75             num[i][j]-=num[i][1];//天真地以为这样就减去第一列了，当j=1执行后，num[i][1]已经 等于0了。。。还傻fufu调了半天（逃。。。。）
 77         }
 78     }

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstring>
  5 #include<algorithm>
  6 using namespace std;
  7 const int mod=1000007;
  8 const int maxn=1000009;
  9 int n,k,cnt;
 10 int num[1000100][31],head[1000100];
 11 struct node
 12 {
 13     int num[31];
 14     int next;
 15     int p;
 16 }edge[maxn];
 17 void ins(int *num,int h,int p)
 18 {
 19     for(int i=1;i<=30;i++)
 20         edge[cnt].num[i]=num[i];
 21     edge[cnt].p=p;
 22     edge[cnt].next=head[h];
 23     head[h]=cnt++;
 24 }
 25 bool cmp(int *num1,int *num2)
 26 {
 27     for(int i=1;i<=k;i++)
 28     if(num1[i]!=num2[i]) return 0;
 29     return 1;
 30 }
 31 int search(int *num,int h)
 32 {
 33     int flag=0,ans=0;
 34     for(int i=head[h];i!=-1;i=edge[i].next)
 35     {
 36         if(cmp(num,edge[i].num))
 37         {
 38             ans=edge[i].p;　　　　　　　　　　　　//这里，不要马上返回
 39         }
 40             //return edge[i].p;
 41     }
 42     return ans;
 43 }
 44 int main()
 45 {
 46     int flag=0;
 47     memset(head,-1,sizeof(head));
 48     scanf("%d%d",&n,&k);
 49     for(int i=1;i<=n;i++)
 50     {
 51         int x;
 52         scanf("%d",&x);
 53         for(int j=1;j<=k;j++)
 54         {
 55             num[i][j]=x%2;
 56             x/=2;
 57         }
 58     }
 59     for(int i=2;i<=n;i++)
 60     {
 61         for(int j=1;j<=k;j++)
 62             num[i][j]+=num[i-1][j];
 63     }
 64     /*for(int i=1;i<=n;i++)
 65     {
 66         for(int j=1;j<=k;j++)cout<<num[i][j];
 67         cout<<endl;
 68     }*/
 69     int ans=0;
 70     for(int i=1;i<=n;i++)
 71     {
 72         int t=num[i][k];
 73         for(int j=1;j<=k;j++)
 74         {
 75             num[i][j]-=t;
 76             //if(num[i][j]<0) num[i][j]=-num[i][j];
 77         }
 78     }
 79     /*for(int i=1;i<=n;i++)
 80     {
 81 
 82         for(int j=1;j<=k;j++)
 83             cout<<num[i][j];
 84         cout<<endl;
 85     }*/
 86     for(int i=1;i<=n;i++)
 87     {
 88         int base=0;
 89         for(int j=1;j<=k;j++)
 90         {
 91             base+=num[i][j];
 92             base*=10;
 93             base%=mod;
 94             //cout<<base<<endl;
 95         }
 96         if(base<0) base=-base;
 97         int tmp=search(num[i],base);
 98         if(tmp>0)
 99         {
100             int t=abs(tmp-i);
101             if(t>ans)
102             {
103                 //cout<<tmp<<" "<<i<<endl;
104                 ans=t;
105             }
106         }
107         if(base==0)
108         {
109             ans=max(i,ans);
110         }
111         ins(num[i],base,i);
112     }
113     printf("%d\n",ans);
114     return 0;
115 }