题目链接：
https://vjudge.net/problem/POJ-3274
题目大意：
给定多头牛的属性，每头牛的属性由一个非负数表示，该数的二进制表示不会超过K位，它的二进制表示的每一位若为1则表示该牛有对应的第i种属性，若为0则表示没有该属性。
对于给定的牛的顺序，要求输出某一段子序列的长度，这个子序列中的牛的K个属性对应相加以后全部相等。
假设n=3, k = 3
输入的3个数变成的二进制分别为(a1, a2, a3), (b1, b2, b3), (c1, c2, c3)
设sum(i)为从第1个数到第i个数的属性和的序列
若从第2个数到第3个数的序列满足条件，则说明b1+c1 = b2+c2 = b3+c3，即sum(3)-sum(2)的序列每一位都相等
推广一下，若sum(i) = (a, b, c)，sum(j) = (d, e, f)，且i到j这个子序列满足条件，则说明(d, e, f) - (a, b, c) = (x, x, x)，即(d, e, f) = (a + x, b + x, c + x)。每个序列中的数都减去序列中的最后一个数，得到(d - f, e - f, 0) = (a - c, b - c, 0)。因此只要判断两个完全转换过后的序列是否相同，就可以知道它们之间的原序列是否满足条件了。
所以解题的第一步是把原来的数转换为二进制序列，第二步是把二进制序列转换成sum序列，即逐步叠加，第三步是把每个sum序列都减去该序列的最后一个数，最后一步是把这些序列进行哈希，计算它们的最大差距。
有一点要注意，如果从第1个数到第i个数这段序列满足条件，即sum(i) - sum(0) = (x, x, x)，则说明sum(i)的各个位都是相同的，因此需要在第三步之前先做这个判断，把符合条件的序列找出来，更新一下答案。所以在hash的时候先存入hash(0)
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<map> 6 #include<set> 7 #include<cmath> 8 using namespace std; 9 const int maxn = 100000 + 10; 10 const int mod = 99991; 11 int num[maxn][32]; 12 int n, k; 13 int maxlen; 14 struct hashtable 15 { 16 int x; 17 hashtable * next; 18 hashtable(){next = 0;} 19 }; 20 hashtable * Hash[mod]; 21 22 bool Equal(int i, int j) 23 { 24 for(int c = 1; c < k; c++) 25 if(num[i][c] != num[j][c])return false; 26 return true; 27 } 28 void Hash_Insert(int i) 29 //根据关键字key找hash位置, 找到位置后存i表示第i行 30 { 31 int key = 0; 32 for(int j = 1; j < k; j++) 33 key += j * num[i][j]; 34 key = abs(key) % mod; 35 if(!Hash[key])//链表的第一个key 36 { 37 hashtable* p = new hashtable; 38 p -> x = i; 39 Hash[key] = p; 40 } 41 else//产生冲突 42 { 43 hashtable * p = Hash[key]; 44 if(Equal(p->x, i))//如果和第i行相等 45 { 46 int dist = i - (p -> x); 47 maxlen = max(maxlen, dist); 48 } 49 else 50 { 51 while(p->next)//判断p->next是否存在，之后直接判断p->next存的行数和当前行数比较 52 { 53 if(Equal(p->next->x, i)) 54 { 55 int dist = i - (p -> next -> x); 56 maxlen = max(maxlen, dist); 57 return;//不用存储i，直接返回，因为已经有和i一样的 58 } 59 p = p->next; 60 } 61 //地址冲突但是和每个冲突的都不相同 62 hashtable* temp = new hashtable; 63 temp->x = i; 64 p->next = temp; 65 } 66 } 67 return; 68 } 69 int main() 70 { 71 scanf("%d%d", &n, &k); 72 int x; 73 for(int i = 1; i <= n; i++) 74 { 75 scanf("%d", &x); 76 for(int j = 0; j < k; j++) 77 if(x & (1 << j))num[i][j] = 1; 78 for(int j = 0; j < k; j++) 79 num[i][j] += num[i - 1][j]; 80 } 81 for(int i = 1; i <= n; i++) 82 { 83 for(int j = 1; j < k; j++) 84 num[i][j] -= num[i][0]; 85 } 86 for(int i = 0; i <= n; i++)Hash_Insert(i);//从第0行开始 87 cout<<maxlen<<endl; 88 }