很不错的hash
优化有两个方面：1.根据题目换一个更优化的算法 2.在算法运行过程中优化
这题除了暴力好像没别的办法了吧？
但是暴力也是有策略的！
到第i只牛特征为j的总数为sum[i,j];
找到最大的区间(l,r]使得sum[r,1]-sum[l,1]=sum[r,2]-sum[l,2]…=sum[r,k]-sum[l,k]
整理就得sum[r,1]-sum[r,2]=sum[l,1]-sum[l,2] sum[r,1]-sum[r,3]=sum[r,1]-sum[r,3]……
于是做到每只牛的时候，我们就能得到一个序列。满足条件就是两个序列相等，
怎么快速判断序列：hash！得解！
type link=^node;
node=record
data:longint;
next:link;
end;
const key=;
var hash:array[..] of link;
sum:array[..] of longint;
num:array[..,..] of longint;
ans,n,k,x,j,i,s:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; function allsame(x,y:longint):boolean; //注意可能出现hash值相同但序列不同
var i:longint;
begin
allsame:=true;
for i:= to k do
if num[x,i]<>num[y,i] then exit(false);
end; procedure add(x,y:longint);
var p:link;
begin
new(p);
p^.data:=y;
p^.next:=hash[x];
hash[x]:=p;
end; procedure push(x,i:longint);
var p:link;
begin
if hash[x]=nil then add(x,i)
else begin
p:=hash[x];
while p<>nil do
begin
if allsame(p^.data,i) then
begin
ans:=max(ans,i-p^.data); //如果相同，那么当前序列就无需入hash
exit;
end;
p:=p^.next;
end;
add(x,i); //拉链法解决冲突
end;
end; begin
readln(n,k);
add(,);
for i:= to n do
begin
readln(x);
j:=;
while x<> do
begin
j:=j+;
sum[j]:=sum[j]+x mod ;
x:=x shr ;
end;
s:=;
for j:= to k do
begin
num[i,j]:=sum[]-sum[j]; //生成序列
s:=(s+sqr(num[i,j])*j mod key) mod key ; //很奇怪的hash……
end;
push(s,i); //hash值都不同那么序列一定不同
end;
writeln(ans);
end.
判断两个序列是否相同，hash是个好方法！