BZOJ-1717: [Usaco2006 Dec]Milk Patterns 产奶的模式

[文章目录]

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;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注