第一篇博客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)脑残错误：
1for(int i=1;i<=n;i++) 2 71 { 3 73 for(int j=1;j<=k;j++) 4 74 { 75 num[i][j]-=num[i][1];//天真地以为这样就减去第一列了，当j=1执行后，num[i][1]已经 等于0了。。。还傻fufu调了半天（逃。。。。） 77 } 78 } 5 6 1 #include<iostream> 7 2 #include<cstdio> 8 3 #include<cstring> 9 4 #include<cstring> 10 5 #include<algorithm> 11 6 using namespace std; 12 7 const int mod=1000007; 13 8 const int maxn=1000009; 14 9 int n,k,cnt; 15 10 int num[1000100][31],head[1000100]; 16 11 struct node 17 12 { 18 13 int num[31]; 19 14 int next; 20 15 int p; 21 16 }edge[maxn]; 22 17 void ins(int *num,int h,int p) 23 18 { 24 19 for(int i=1;i<=30;i++) 25 20 edge[cnt].num[i]=num[i]; 26 21 edge[cnt].p=p; 27 22 edge[cnt].next=head[h]; 28 23 head[h]=cnt++; 29 24 } 30 25 bool cmp(int *num1,int *num2) 31 26 { 32 27 for(int i=1;i<=k;i++) 33 28 if(num1[i]!=num2[i]) return 0; 34 29 return 1; 35 30 } 36 31 int search(int *num,int h) 37 32 { 38 33 int flag=0,ans=0; 39 34 for(int i=head[h];i!=-1;i=edge[i].next) 40 35 { 41 36 if(cmp(num,edge[i].num)) 42 37 { 43 38 ans=edge[i].p; //这里，不要马上返回 44 39 } 45 40 //return edge[i].p; 46 41 } 47 42 return ans; 48 43 } 49 44 int main() 50 45 { 51 46 int flag=0; 52 47 memset(head,-1,sizeof(head)); 53 48 scanf("%d%d",&n,&k); 54 49 for(int i=1;i<=n;i++) 55 50 { 56 51 int x; 57 52 scanf("%d",&x); 58 53 for(int j=1;j<=k;j++) 59 54 { 60 55 num[i][j]=x%2; 61 56 x/=2; 62 57 } 63 58 } 64 59 for(int i=2;i<=n;i++) 65 60 { 66 61 for(int j=1;j<=k;j++) 67 62 num[i][j]+=num[i-1][j]; 68 63 } 69 64 /*for(int i=1;i<=n;i++) 70 65 { 71 66 for(int j=1;j<=k;j++)cout<<num[i][j]; 72 67 cout<<endl; 73 68 }*/ 74 69 int ans=0; 75 70 for(int i=1;i<=n;i++) 76 71 { 77 72 int t=num[i][k]; 78 73 for(int j=1;j<=k;j++) 79 74 { 80 75 num[i][j]-=t; 81 76 //if(num[i][j]<0) num[i][j]=-num[i][j]; 82 77 } 83 78 } 84 79 /*for(int i=1;i<=n;i++) 85 80 { 86 81 87 82 for(int j=1;j<=k;j++) 88 83 cout<<num[i][j]; 89 84 cout<<endl; 90 85 }*/ 91 86 for(int i=1;i<=n;i++) 92 87 { 93 88 int base=0; 94 89 for(int j=1;j<=k;j++) 95 90 { 96 91 base+=num[i][j]; 97 92 base*=10; 98 93 base%=mod; 99 94 //cout<<base<<endl; 100 95 } 101 96 if(base<0) base=-base; 102 97 int tmp=search(num[i],base); 103 98 if(tmp>0) 104 99 { 105100 int t=abs(tmp-i); 106101 if(t>ans) 107102 { 108103 //cout<<tmp<<" "<<i<<endl; 109104 ans=t; 110105 } 111106 } 112107 if(base==0) 113108 { 114109 ans=max(i,ans); 115110 } 116111 ins(num[i],base,i); 117112 } 118113 printf("%d\n",ans); 119114 return 0; 120115 }