bzoj 2806: [Ctsc2012]Cheat

发布时间:2017-7-9 7:16:06编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"bzoj 2806: [Ctsc2012]Cheat ",主要涉及到bzoj 2806: [Ctsc2012]Cheat 方面的内容,对于bzoj 2806: [Ctsc2012]Cheat 感兴趣的同学可以参考一下。

传送门

  好久没刷bzoj惹……

  题意不说可以嘛。

  首先二分答案。

  SAM的事情搞完以后就是dp辣。

  我们已经对于每个位置i,找到了最小的一个k,使得[k,i]这个子串在模版串中出现过。那么我们需要做的是把f[i]给min上f[k]到f[i-x],直接搞是$n^2logn$的,套个数据结构也是两个log的。然而如果一个位置j不在合法的区间中,那么以后也不会进入,那么直接用一个单调队列维护就好了。

#include<cstdio>#include<cstring>#include<algorithm>#define MN 1200000using namespace std;int read_p,read_ca,read_f;inline int read(){    read_p=0;read_ca=getchar();read_f=1;    while(read_ca<'0'||read_ca>'9') read_f=read_ca=='-'?-1:read_f,read_ca=getchar();    while(read_ca>='0'&&read_ca<='9') read_p=read_p*10+read_ca-48,read_ca=getchar();    return read_p*read_f;}struct na{int l,f,t[2];na(){t[0]=t[1]=0;f=-1;}}t[MN<<1];int n,m,la,num=0,mi[MN],st[MN];char s[MN];inline void add(int x){    int p=++num;t[p].l=t[la].l+1;    while (la!=-1&&!t[la].t[x]) t[la].t[x]=p,la=t[la].f;    if (la==-1) t[p].f=0;else{        int o=t[la].t[x];        if (t[o].l==t[la].l+1) t[p].f=o;else{            int np=++num;            t[np]=t[o];            t[np].l=t[la].l+1;            t[o].f=t[p].f=np;            while (la!=-1&&t[la].t[x]==o) t[la].t[x]=np,la=t[la].f;        }    }    la=p;}inline bool ju(int x){    mi[0]=0;    int i,p,l,L=1,R=0;    for (i=1;s[i-1];i++) mi[i]=1e9;    for (i=0,p=0,l=0;s[i];i++){        while (p&&!t[p].t[s[i]-'0']) p=t[p].f,l=t[p].l;        if (t[p].t[s[i]-'0']) p=t[p].t[s[i]-'0'],l++;        if (i+1>=x){            while(L<=R&&mi[i+1-x]<=mi[st[R]]) R--;            st[++R]=i+1-x;        }        while (L<=R&&st[L]<=i-l) L++;        if (L<=R) if (mi[i+1]>mi[st[L]]) mi[i+1]=mi[st[L]];        if (mi[i+1]>mi[i]+1) mi[i+1]=mi[i]+1;    }    return mi[i]*10<=i;}int main(){    n=read();m=read();    for (int i=1;i<=m;i++){        la=0;scanf("%s",s);        for (int j=0;s[j];j++) add(s[j]-'0');    }    for (int i=1;i<=n;i++){        scanf("%s",s);        int l=1,r=strlen(s),mid;        while(l<r) if (ju(mid=l+r+1>>1)) l=mid;else r=mid-1;        printf("%d\n",l);    }}
View Code


上一篇:Cadence之双击(DSN/brd)文件打开变新建文件的解决方法
下一篇:关于angularJS绑定数据时自动转义html标签

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款