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 = 100003 ; const int maxn = 32 ; int sum[maxx][maxn]; int head[maxx],next[maxx] ; int K ; int hash(int c[]) { int h = 0 ; for(int i = 0 ; i < K ; i++) h = ((h << 2) + (c[i] >> 4))^(c[i] << 10) ; h = h % maxx ; h = h < 0 ? (h+maxx) : h ; return h ; } int main() { int N ,f; memset(head ,-1 ,sizeof(head)) ; memset(sum,0,sizeof(sum)) ; int ans = 0 ; scanf("%d %d",&N,&K) ; for(int i = 1 ; i <= N ; i++) { scanf("%d",&f) ; for(int j = 0 ; j < K ; j++) { sum[i][j] = f & 1 ; f = f >> 1 ; } } for(int i = 2 ; i <= N ; i++) { for(int j = 0 ; j < K; j++) sum[i][j] += sum[i-1][j] ; } for(int i = 0 ; i <= N ; i++) { int temp = sum[i][0] ; for(int j = 0 ; j < K; j++) sum[i][j] -= temp ; int h = hash(sum[i]) ; bool flag = 0 ; for(int e = head[h] ; e != -1 ; e = next[e]) { if(memcmp(sum[e],sum[i],sizeof(sum[i])) == 0) { ans = max(ans,i-e ) ; flag = 1 ; break ; } } if(!flag) { next[i] = head[h] ; head[h] = i ; } } printf("%d ",ans) ; return 0 ; }