[文章目录]
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。
二分+哈希水过
#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
int n,m,w[21000];
struct node {ull ha1,ha2;};
bool operator<(const node &x,const node &y)
{
return x.ha1==y.ha1?x.ha2<y.ha2:x.ha1<y.ha1;
}
multiset<node>s;
multiset<node>::iterator it,fro;
ull pow(ull x,int y)
{
ull re=1;
while(y)
{
if(y&1) re=re*x;
x=x*x; y>>=1;
}
return re;
}
int check(int x)
{
ull has1=0,has2=0; s.clear();
for(int i=1;i<=x;++i)
has1=has1*233+w[i],has2=has2*2333+w[i];
ull po1=pow(233,x-1),po2=pow(2333,x-1);
s.insert((node){has1,has2});
for(int i=x+1;i<=n;++i)
{
has1-=w[i-x]*po1; has2-=w[i-x]*po2;
has1=has1*233+w[i]; has2=has2*2333+w[i];
s.insert((node){has1,has2});
}
fro=it=s.begin(); int re=0,cnt=0;
while(it!=s.end())
{
if(it->ha1==fro->ha1&&it->ha2==fro->ha2) cnt++;
else re=max(re,cnt),cnt=1;
fro=it; it++;
}
return max(re,cnt);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",w+i);
int l=1,r=n+1,mid;
while(l<r)
{
mid=l+r>>1;
if(check(mid)>=m) l=mid+1;
else r=mid;
}
printf("%d",l-1);
return 0;
}