http://poj.org/problem?id=3274
题意 ：农夫约翰的n（1 <= N <= 100000）头奶牛，有很多相同之处，约翰已经将每一头奶牛的不同之处，归纳成了K种特性，比如1号特性代表它身上有斑点，2号特性代表它比较喜欢用passcal 写程序而不是C 。约翰使用“特性标识符”来描述奶牛的各种特性，例如：一头奶牛的特性标识符是13，将13写成二进制1101，从右向左看，就表示这头奶牛具有1，3，4这三个特性，但没有2号特性，约翰把n头奶牛排成一排，发现在有些连续区间里的奶牛，每种特性出现的次数是一样的，约翰把这样的区间成为平衡的，约翰希望你帮忙找出平衡区间的最大长度 。
思路：虽说知道这个题要用哈希，但是却不知道具体怎么用哈希，我觉得这个题真是有够麻烦的。
数组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。
样例解释：先将十进制转化成二进制（因为题目中转化成的二进制是从左往右读的）
7---->111
6---->011
7---->111
2---->010
1---->100
4---->001
2---->010
将这7行二进制逐行累加得到
111
122
233
243
343
344
354
再利用C[i][y]=sum[i][y]-sum[i][0]求C数组，即所有列都减去第一列（注意C数组有第0行，为全0）
0 0 0 -->第0行
0 0 0
0 1 1
0 1 1
0 2 1
0 1 0
0 1 1
0 2 1
显然第2行与第6行相等，均为011，且距离最远，距离为6-2=4，这就是所求。
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h> using namespace std ; const int maxx = ;
const int maxn = ;
int sum[maxx][maxn];
int head[maxx],next[maxx] ;
int K ; int hash(int c[])
{
int h = ;
for(int i = ; i < K ; i++)
h = ((h << ) + (c[i] >> ))^(c[i] << ) ;
h = h % maxx ;
h = h < ? (h+maxx) : h ;
return h ;
} int main()
{
int N ,f;
memset(head ,- ,sizeof(head)) ;
memset(sum,,sizeof(sum)) ;
int ans = ;
scanf("%d %d",&N,&K) ;
for(int i = ; i <= N ; i++)
{
scanf("%d",&f) ;
for(int j = ; j < K ; j++)
{
sum[i][j] = f & ;
f = f >> ;
}
}
for(int i = ; i <= N ; i++)
{
for(int j = ; j < K; j++)
sum[i][j] += sum[i-][j] ;
}
for(int i = ; i <= N ; i++)
{
int temp = sum[i][] ;
for(int j = ; j < K; j++)
sum[i][j] -= temp ;
int h = hash(sum[i]) ;
bool flag = ;
for(int e = head[h] ; e != - ; e = next[e])
{
if(memcmp(sum[e],sum[i],sizeof(sum[i])) == )
{
ans = max(ans,i-e ) ;
flag = ;
break ;
}
}
if(!flag)
{
next[i] = head[h] ;
head[h] = i ;
}
}
printf("%d\n",ans) ;
return ;
}