「BZOJ1717」[Usaco2006 Dec] Milk Patterns 产奶的模式

2014年5月20日5,4575

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

题解

哎，还是不能无脑敲sa

参见论文例题，好像是可重叠k次重复字串

做法可以单调队列或者二分

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 20005
#define M 1000005
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,m,k,p,q,tot;
int a[N],num[N],hash[N],v[N],h[N],ht[N],sa[2][N],rank[2][N];
int find(int x)
{
    int l=1,r=tot,ans=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(hash[mid]<=x){ans=mid;l=mid+1;}
        else r=mid-1;
    }
    return ans;
}
bool jud(int x)
{
     int tmp=0;
     for(int i=1;i<=n;i++)
     {
         if(ht[i]>=x){tmp++;if(tmp==m-1)return 1;}
         else tmp=0;
     }
     return 0;
}
int getans()
{
     k=0;
     for(int i=1;i<=n;i++)
     {
         if(rank[p][i]==1)h[i]=0;
         else
         {
              int j=sa[p][rank[p][i]-1];
              while(a[i+k]==a[j+k])k++;
              h[i]=k;if(k>0)k--;
         }
     }
     for(int i=1;i<=n;i++)
         ht[rank[p][i]]=h[i];
     int l=1,r=n,ans=0;
     while(l<=r)
     {
         int mid=(l+r)>>1;
         if(jud(mid)){ans=mid;l=mid+1;}
         else r=mid-1;
     }
     printf("%d",ans);
}
void calsa(int sa[N],int rk[N],int SA[N],int RK[N])
{
     int i;
     for(i=1;i<=n;i++)v[rk[sa[i]]]=i;
     for(i=n;i>=1;i--)if(sa[i]>k)SA[v[rk[sa[i]-k]]--]=sa[i]-k;
     for(i=n-k+1;i<=n;i++)SA[v[rk[i]]--]=i;
     for(i=1;i<=n;i++)RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);
}
void work()
{
     p=0,q=1;a[0]=-1;
     for(int i=1;i<=n;i++)v[a[i]]++;
     for(int i=1;i<=n;i++)v[i]+=v[i-1];
     for(int i=1;i<=n;i++)sa[p][v[a[i]]--]=i;
     for(int i=1;i<=n;i++)
         if(a[sa[p][i]]!=a[sa[p][i-1]])
             rank[p][sa[p][i]]=rank[p][sa[p][i-1]]+1;
         else rank[p][sa[p][i]]=rank[p][sa[p][i-1]];
     k=1;
     while(k<n)
     {
         calsa(sa[p],rank[p],sa[q],rank[q]);
         p^=1;q^=1;k<<=1;
	 }
     getans();
}
int main()
{
     n=read();m=read();
     for(int i=1;i<=n;i++)
         a[i]=num[i]=read();
     sort(num+1,num+n+1);
     hash[++tot]=num[1];
     for(int i=2;i<=n;i++)
         if(num[i]!=num[i-1])
             hash[++tot]=num[i];
     for(int i=1;i<=n;i++)a[i]=find(a[i]);
     work();
     return 0;
}

100

101

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 20005

#define M 1000005

using namespace std;

inline int read()

{

int x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

int n,m,k,p,q,tot;

int a[N],num[N],hash[N],v[N],h[N],ht[N],sa[2][N],rank[2][N];

int find(int x)

{

int l=1,r=tot,ans=0;

while(l<=r)

{

int mid=(l+r)>>1;

if(hash[mid]<=x){ans=mid;l=mid+1;}

else r=mid-1;

}

return ans;

}

bool jud(int x)

{

int tmp=0;

for(int i=1;i<=n;i++)

{

if(ht[i]>=x){tmp++;if(tmp==m-1)return 1;}

else tmp=0;

}

return 0;

}

int getans()

{

k=0;

for(int i=1;i<=n;i++)

{

if(rank[p][i]==1)h[i]=0;

else

{

int j=sa[p][rank[p][i]-1];

while(a[i+k]==a[j+k])k++;

h[i]=k;if(k>0)k--;

}

for(int i=1;i<=n;i++)

ht[rank[p][i]]=h[i];

int l=1,r=n,ans=0;

while(l<=r)

{

int mid=(l+r)>>1;

if(jud(mid)){ans=mid;l=mid+1;}

else r=mid-1;

}

printf("%d",ans);

}

void calsa(int sa[N],int rk[N],int SA[N],int RK[N])

{

int i;

for(i=1;i<=n;i++)v[rk[sa[i]]]=i;

for(i=n;i>=1;i--)if(sa[i]>k)SA[v[rk[sa[i]-k]]--]=sa[i]-k;

for(i=n-k+1;i<=n;i++)SA[v[rk[i]]--]=i;

for(i=1;i<=n;i++)RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);

}

void work()

{

p=0,q=1;a[0]=-1;

for(int i=1;i<=n;i++)v[a[i]]++;

for(int i=1;i<=n;i++)v[i]+=v[i-1];

for(int i=1;i<=n;i++)sa[p][v[a[i]]--]=i;

for(int i=1;i<=n;i++)

if(a[sa[p][i]]!=a[sa[p][i-1]])

rank[p][sa[p][i]]=rank[p][sa[p][i-1]]+1;

else rank[p][sa[p][i]]=rank[p][sa[p][i-1]];

k=1;

while(k<n)

{

calsa(sa[p],rank[p],sa[q],rank[q]);

p^=1;q^=1;k<<=1;

}

getans();

}

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)

a[i]=num[i]=read();

sort(num+1,num+n+1);

hash[++tot]=num[1];

for(int i=2;i<=n;i++)

if(num[i]!=num[i-1])

hash[++tot]=num[i];

for(int i=1;i<=n;i++)a[i]=find(a[i]);

work();

return 0;

}

« 「BZOJ1031」[JSOI2007] 字符加密Cipher 「BZOJ1196」[HNOI2006] 公路修建问题 »

Leo

黄学长这道题最后二分判断的时候，直接用h[i]>=x不就行了么？为什么要先处理一个ht数组啊？

2014pku计算概论入学测试 - 递推与动规 - KMP - 后缀数组 - 最大流 - hzwer.com

[…] 【bzoj1717】[Usaco2006 Dec]Milk Patterns 产奶的模式 […]

SkyDec

额…SYC刚刚说他是用SA过掉的

hzwer

本来就是用sa啊

SkyDec

好吧我傻掉了

hzwer.com _ Home | http://hzwer.com

「BZOJ1717」[Usaco2006 Dec] Milk Patterns 产奶的模式

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论