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

ydc的博客

 
 
 

日志

 
 

ctsc2012 cheat  

2014-03-06 00:33:09|  分类: ctsc |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
突然想起忘记补上这个了
不过也没什么好说的……我们可以预处理每个位置向前最多走多少位的串是给定串的子串,二分答案后单调队列dp即可
预处理用后缀自动机……这几天学的。估计学了这个之后不久就要退役了,朝闻道夕死可矣吧
补完了ctsc2012的传统题……一点感触都没有的说
这一两天补一点后缀自动机的入门题吧

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#define maxn 1100010
using namespace std;
struct Node
{
Node *trans[3],*parent;
int len;
}*init,*last,pool[maxn*2],*st=pool;
char str[maxn];
int n,m,match[maxn];
void extend(int idx)
{
static Node *p,*np,*nq;
p=last,np=++st,last=np,np->len=p->len+1;
for(;p&&p->trans[idx]==0;p=p->parent)
p->trans[idx]=np;
if(p==0)
np->parent=init;
else
{
Node *q=p->trans[idx];
if(q->len==p->len+1)
np->parent=q;
else
{
nq=++st,*nq=*q;
q->parent=np->parent=nq,nq->len=p->len+1;
for(;p&&p->trans[idx]==q;p=p->parent)
p->trans[idx]=nq;
}
}
}
int calc(int L,int n)
{
static int queue[maxn],dp[maxn];
fill(dp+1,dp+L,0);
int front=1,rear=0;
for(int i=L;i<=n;++i)
{
dp[i]=dp[i-1];
if(match[i]<=i-L)
{
int val=dp[i-L]-(i-L);
while(rear>=front&&dp[queue[rear]]-queue[rear]<=val)
--rear;
queue[++rear]=i-L;
while(rear>=front&&queue[front]<match[i])
++front;
if(front<=rear)
dp[i]=max(dp[i],dp[queue[front]]-queue[front]+i);
}
}
return dp[n];
}
void read()
{
init=last=++st;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;++i)
{
scanf("%s",str+1);
for(int j=1;str[j];++j)
extend(str[j]-'0');
extend(2);
}
}
int binary(int l,int r,int n)
{
while(l<r)
{
int mid=(l+r)>>1;
calc(mid,n)*10>=9*n?l=mid+1:r=mid;
}
return l-1;
}
void Query()
{
Node *p;
for(int i=1;i<=n;++i)
{
scanf("%s",str+1);
p=init;
int len=strlen(str+1),tot=0;
for(int j=1;j<=len;++j)
{
int idx=str[j]-'0';
while(p!=init&&p->trans[idx]==0)
p=p->parent,tot=p->len;
if(p->trans[idx])
++tot,p=p->trans[idx];
match[j]=j-tot;
}
printf("%d\n",binary(1,len+1,len));
}
}
int main()
{
read();
Query();
return 0;
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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