[题目来源]：POJ3274
[关键字]：hash
[题目大意]：用一个十进制整数的二进制代表每个奶牛的特征（右往左数第i为为1是有0没有），给出一个奶牛序列找到一个最长的连续满足：此序列中所有奶牛的各个特征和相等。
//============================================================================================================
[分析]：以样例为例：
111
110
111
010
001
100
010
累加后
111
221
332
342
343
443
453
到此还比较好想接着，都减去最右边的数
000
110<=i
110
120
010
110<=j
120
到此可以看出规律，现求出以上序列，只要查找两个序列相的且使j-i最大，就是答案——hash查找BKDRHash。
[代码]：
View Code 1 program Project1; 2 type 3 arr = array[0..30] of longint; 4 rec = record 5 dat: arr; 6 num: longint; 7 end; 8 var 9 n, m, ans: longint; 10 a, c: array[0..100010] of arr; 11 num: array[0..15988] of longint; 12 h: array[0..15988,0..10] of rec; 13 14 function hash(a: arr):longint; 15 var 16 seek, i: longint; 17 begin 18 seek := 131; 19 hash := 0; 20 for i := 1 to m do 21 hash := (hash*seek+a[i]) and $FFFFFFFF; 22 hash := hash and $7FFFFFFF; 23 hash := hash mod 15988; 24 if hash < 0 then hash := hash+15988; 25 end; 26 27 function change_two(x: longint):arr; 28 var 29 temp, i: longint; 30 b: arr; 31 begin 32 temp := 0; 33 while x <> 0 do 34 begin 35 inc(temp); 36 b[temp] := x mod 2; 37 x := x div 2; 38 end; 39 for i := temp+1 to m do b[i] := 0; 40 for i := 1 to m div 2 do 41 begin 42 temp := b[i]; 43 b[i] := b[m-i+1]; 44 b[m-i+1] := temp; 45 end; 46 exit(b); 47 end; 48 49 function cleck(a, b: arr):boolean; 50 var 51 i: longint; 52 begin 53 for i := 1 to m do 54 if a[i] <> b[i] then exit(false); 55 exit(true); 56 end; 57 58 procedure init; 59 var 60 i, j, k, p, r: longint; 61 begin 62 readln(n,m); 63 ans := 0; 64 for i := 1 to m do 65 c[0][i] := 0; 66 k := hash(c[0]); 67 p := 0; 68 for j := 1 to num[k] do 69 if cleck(c[0],h[k,j].dat) then 70 if 0-h[k,j].num > p then p := 0-h[k,j].num; 71 if (p <> 0) and (p > ans) then ans := p; 72 if p = 0 then 73 begin 74 inc(num[k]); 75 h[k,num[k]].dat := c[0]; 76 h[k,num[k]].num :=0; 77 end; 78 for i := 1 to n do 79 begin 80 readln(r); 81 a[i] := change_two(r); 82 {for j := 1 to m do 83 write(a[i][j]); 84 writeln;} 85 for j := 1 to m do 86 begin 87 c[i][j] := c[i-1][j]+a[i][j]-a[i][m]; 88 //write(c[i][j]); 89 end; 90 k := hash(c[i]); 91 p := 0; 92 for j := 1 to num[k] do 93 if cleck(c[i],h[k,j].dat) then 94 if i-h[k,j].num > p then p := i-h[k,j].num; 95 if (p <> 0) and (p > ans) then ans := p; 96 if p = 0 then 97 begin 98 inc(num[k]); 99 h[k,num[k]].dat := c[i];100 h[k,num[k]].num := i;101 end;102 end;103 writeln(ans);104 //readln;105 //readln;106 end;107 108 begin109 init;110 end.转载于:https://www.cnblogs.com/procedure2012/archive/2011/10/19/2217832.html
相关资源：垃圾分类数据集及代码