【题目描述】 农夫约翰的N头奶牛有很多相同之处。其实，约翰己经将每头奶牛的不同之处归纳成为K种特性，比如说，1号特性可以代表她身上有斑点，2号特性代表她更喜欢用Pascal而不是C来写程序等等。 约翰使用“特性标识符”来描述奶牛的各种特性：一个特性标识符就是一个二进制长度 为K的整数，每位比特可以标识一头奶牛的一个特性。比如一头奶牛的特性标识符是13,将13写成二进制：1101,从右向左看，就表示这头奶牛具冇1、3、4号特性，但没有2号特性。 约翰把N头奶牛排成了一排，发现在有些连续区间里的奶牛，每种特性出现的次数是一样的，约翰把这样的区间称为“平衡的”。作为一个喜欢研究的人，约翰希望你能帮忙找出平衡区间的最大长度。 【输入格式】 第一行两个整数N和K 接下来N行，每行一个十进制正整数ai表示第i头奶牛的特性标识符 【输出格式】 平衡区间的最大长度 【样例输入】 7 3 7 6 7 2 1 4 2 【样例输出】 4 【分析】 设sum[i,j]表示第1头到第i头奶牛属性j的出现次数，则列出方程： sum[i][0]-sum[j][0]=sum[i][1]-sum[j][1]=…..=sum[i][k-1]-sum[j][k-1] 将方程变形可得 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] 令count[i,j]=sum[i][j]-sum[i][0]，就只要求出满足count[i][]=count[j][] 中最大的i-j即可。
const inf=10007; type arr=array[0..31]of longint; rec=record data,no:longint; end; var sum,count:array[0..100001,0..30]of longint; h:array[0..inf,0..55]of rec; i,j,n,m,max,t:longint; function check(x,y:longint):boolean; var i:longint; begin for i:=1 to m do if count[x,i]<>count[y,i] then exit(false); exit(true); end; procedure insert(t:longint); var i,p:longint; begin p:=0; for i:=1 to m do p:=p+count[t,i]*i; p:=abs(p) mod inf; i:=0; while h[p,i].no=1 do begin if check(h[p,i].data,t)=true then begin if t-h[p,i].data>max then max:=t-h[p,i].data; exit; end; inc(i); end; h[p,i].no:=1; h[p,i].data:=t; end; begin max:=0; fillchar(h,sizeof(h),0); h[0,0].no:=1; readln(n,m); for i:=1 to n do begin read(t); for j:=1 to m do begin sum[i,j]:=sum[i-1,j]+t mod 2; count[i,j]:=sum[i,j]-sum[i,1]; t:=t shr 1; end; insert(i); end; write(max); end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533543.html
