BZOJ#1717:[Usaco2006 Dec]Milk Patterns 产奶的…

2018-06-17 21:31:14来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

 

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。


 

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

 

题解:


 

   看到网上基本上都是用的二分,所以我打算来一篇单调队列的做法!
 

题意:
     题目要求满足重复k次,并且是最长的串的长度;
 

分析:
     首先我们要知道不相邻的两个串的LCP是等于它们之间的height值的最小值(LCP定义);其次我们可以发现这样一个性质,假设:
   A
   B
   C
   D
      E
   price:以每个串为开头,长度为k的队列的值;
  
(根据SA数组从小到大排列的height数组)且此时k=2,如果参与答案中的最后一个串为E,那么答案就是D到E之间的
 
height值的最小值;再假设最后一个串为B,那么答案为A到B之间的height值的最小值;到这里你有没有一点点头绪呢?^_^ 我
 
们的答案就是在以每个串为头(或者尾),以k为身长的一个队列中,再根据上面的性质,每个price是它队身中height值的最小
 
值;我们只要找出最小的price就是我们的答案了! 可能你会问不是要求至少吗?其实你可以想想,我们在已经满足了k的条件
 
后,如果我们再继续增加队身的长度,如果进来的一个height比当前的price大,那么的对我们的price没有影响(因为上面的性
 
质);如果来一个height比当前price小,那么会我们的price变小,这不符合我们的需要,所以证明;所以我们只需要O(n)的进
 
行单调队列维护最小值,求得一个最小的price即可!
 

注意:
    因为数据可能很大,所以需要离散化一下!
 

代码:
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int len,m,ki;
int str[20010];
int rank[20010],buc[20010],SA[20010],y[20010];
int belong[1000010],cnt;
void suffix()
{
    m=len;
    for(int i=0;i<m;i++) buc[i]=0;
    for(int i=0;i<len;i++) buc[rank[i]=belong[str[i]]]++;
    for(int i=1;i<m;i++) buc[i]+=buc[i-1];
    for(int i=len-1;i>=0;i--) SA[--buc[rank[i]]]=i;
    for(int k=1;k<len;k<<=1)
    {
        int p=0;
        for(int i=len-1;i>=len-k;i--) y[p++]=i;
        for(int i=0;i<len;i++) if(SA[i]>=k) y[p++]=SA[i]-k;
        for(int i=0;i<m;i++) buc[i]=0;
        for(int i=0;i<len;i++) buc[rank[y[i]]]++;
        for(int i=1;i<m;i++) buc[i]+=buc[i-1];
        for(int i=len-1;i>=0;i--) SA[--buc[rank[y[i]]]]=y[i];
        swap(rank,y);p=1;
        rank[SA[0]]=0;
        for(int i=1;i<len;i++)
        {
            if(y[SA[i-1]]==y[SA[i]]&&y[SA[i-1]+k]==y[SA[i]+k])
            rank[SA[i]]=p-1;
            else rank[SA[i]]=p++;
        }
        if(p>=len) break;
        m=p;
    }
}
int height[20010];
struct node
{
    int place,price;
}t[20010];

int main()
{
    freopen("a.in","r",stdin);
    scanf("%d%d",&len,&ki);
    int imax=0;
    for(int i=0;i<len;i++) 
    {
        scanf("%d",&str[i]);
        belong[str[i]]++;
        imax=max(str[i],imax);
    }
    for(int i=0;i<=imax;i++) if(belong[i]) belong[i]=cnt++;
    suffix();
    int x=0;
    for(int i=0;i<len;i++) rank[SA[i]]=i;
    for(int i=0;i<len;i++)
    {
        if(rank[i]==0) continue;
        if(x) x--;
        int j=SA[rank[i]-1];
        while(str[i+x]==str[j+x]&&x+i<len&&x+j<len) x++;
        height[rank[i]]=x;
    }
    int ans=0;
    int now=len-1;
    int l=0,r=-1;
    while(now>=0)
    {    
        while(t[l].place-now>=ki-1) l++;
        while(t[r].price>=height[now]&&r>=l) r--;
        t[++r].price=height[now];t[r].place=now; 
        if(len-now+1>=ki) 
        {    
            if(t[l].price>ans) ans=t[l].price;
        }
        now--;        
    }
    printf("%d\n",ans);
    return 0;
}

 

未经博主同意,不得私自转载!

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++11 实现信号量Semaphore类

下一篇:Qt---Xml文件解析