[Usaco2006 Dec]Milk Patterns

Time Limit:5000MS  Memory Limit:65536K
Total Submit:9 Accepted:6
Case Time Limit:1000MS

Description

农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天
产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。
John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的
牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。
比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时，这个长度为4。

Input

* Line 1: 两个整数 N,K。

* Lines 2..N+1: 每行一个整数表示当天的质量值。

Output

* Line 1: 一个整数：N天中最长的出现了至少K次的模式的长度

Sample Input

8 2
1
2
3
2
3
2
3
1

Sample Output

4

Source

Gold

直接上Hash。。二分判断就可以了。。代码0.7K囧。。
Code：

#include <algorithm>
#include <cstdio>
#include <map>
#define rep(i,n) for(int i=0;i<n;i++)
const int seed=1333331,maxn=20000;
using namespace std;
typedef unsigned long long ull;
ull P[maxn];
int n,k,A[maxn];
bool Check(int L)
{
ull ret=0;map<ull,int> M;
rep(i,L) ret*=seed,ret+=A[i];
M[ret]=1;
rep(i,n-L)
{
ret-=P[L-1]*A[i];ret*=seed;ret+=A[i+L];
int&x=M[ret];if(++x>=k)return true;
}
return false;
}
int main()
{
scanf("%d%d",&n,&k);rep(i,n)scanf("%d",A+i);
P[0]=1;rep(i,n-1)P[i+1]=P[i]*seed;
int l=0,r=n/k+1;
while(l+1<r)
{
int m=(l+r)/2;
if(Check(m)) l=m;
else r=m;
}
printf("%dn",l);
}