注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2806][Ctsc2012]Cheat  

2015-04-23 21:26:47|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2806: [Ctsc2012]Cheat

Time Limit: 20 Sec  Memory Limit: 256 MB
Submit: 591  Solved: 334
[Submit][Status][Discuss]

Description

Input

第一行两个整数N,M表示待检查的作文数量,和小强的标准作文库
的行数
接下来M行的01串,表示标准作文库
接下来N行的01串,表示N篇作文

Output

N行,每行一个整数,表示这篇作文的Lo 值。

Sample Input

1 2 10110 000001110 1011001100

Sample Output

4

HINT

输入文件不超过1100000字节

注意:题目有改动,可识别的长度不小于90%即可,而不是大于90%

Solution

后缀自动机第一题 
网络上blog都有详细介绍,但是花了一个早上才大致弄明白构造方式。
对于每个01串先全部拼成一起建后缀自动机,用目标串匹配后缀自动机,处理出第i位往前最多能匹配的长度为d[i],
然后二分答案L,考虑dp:f[i]=f[j]+i-j (i-d[i]<=j<=i-L),1~i最多能匹配的字母数,能用单调队列维护。
注意先查询后删除,因为二者不同步,应该要在做i的时候插入i-L(被这个坑了好久)

Code

/**************************************************************
    Problem: 2806
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1008 ms
    Memory:68388 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#define N 1<<21
int n,m,tot=1,las=1,S=1,ch[N][3],fail[N],len[N],d[N],i,j,now,dep,l,r,mid,q[N],f[N];char s[N];
void add(char c){
    int p=las,np=++tot;
    for(len[np]=len[p]+1;p&&!ch[p][c];p=fail[p])ch[p][c]=np;
    if(las=np,!p)fail[np]=S;
    else if(len[p]+1==len[ch[p][c]])fail[np]=ch[p][c];
    else{
        int q=ch[p][c],r=++tot,j;
        for(len[r]=len[p]+1,fail[r]=fail[q],j=0;j<3;j++)ch[r][j]=ch[q][j];
        for(fail[q]=fail[np]=r;p&&ch[p][c]==q;p=fail[p])ch[p][c]=r;
    }
}
#define cmax(a,b) (a<b?a=b:1)
int check(int L){
    int l=1,r=0,i;
    for(i=1;i<=n;i++){
        if(i>=L){
            while(l<=r&&f[q[r]]-q[r]<f[i-L]-i+L)r--;
            q[++r]=i-L;
        }
        while(l<=r&&q[l]<i-d[i])l++;f[i]=f[i-1];
        if(l<=r)cmax(f[i],f[q[l]]+i-q[l]);
    }
    return f[n]*10>=n*9;
}
int main(){
    for(scanf("%d%d\n",&n,&m);m--;add(2))
    for(gets(s+1),i=1;s[i];i++)add(s[i]-'0');
    for(m=n;m--;printf("%d\n",l)){
        for(now=S,dep=0,gets(s+1),n=1;s[n];d[n++]=dep){
            for(s[n]-='0';now>1&&!ch[now][s[n]];dep=len[now=fail[now]]);
            if(ch[now][s[n]])now=ch[now][s[n]],++dep;
        }
        for(l=0,r=--n;l<r;check(mid=l+r+1>>1)?l=mid:r=mid-1);
    }
}

  评论这张
 
阅读(182)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018