BZOJ 2806 【CTSC2012】 Cheat

题目链接：Cheat

　　话说这道题很久以前某人就给我们考过，直到现在，我终于把这个坑填上了……

　　这道题要我们把一个串\(S\)划分成若干块，每块长度不小于\(L_0\)，使得能够在文章库中完全匹配的块的长度和占总长度的\(90\%\)以上。首先，答案显然是可以二分的。于是，我们就可以二分一个答案\(ans\),考虑如何\(check\)。

　　很显然的一个想法就是\(dp\)。如果我们知道这个串的第\(i\)位往前最多能够走\(x_i\)位，使得\(S_{i-x_i}\)到\(S_i\)组成的串能够在文章库中匹配，那么我们就可以写出\(dp\)方程了：\begin{aligned} f_i=&\max \{ f_j+i-j \}(i-x_i \le j \le i-ans) \\ = &i+\max \{ f_i-j \}\ (i-x_i \le j \le i-ans) \end{aligned}

　　当然，\(f_i=\max(f_i,f_{i-1})\)

　　然后，我们就可以发现\(i-x_i\)是单调的(话说我刚开始还没有看出来)，然后由于\(i-ans\)显然也是单调的，所以我们就可以弄个单调队列维护区间最大值即可。最后再判断一下总的匹配长度是否大于等于总长度的\(90\%\)即可。

　　下面贴代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

#define maxn 2200010

using namespace std;

typedef long long llg;

int n,m,tot,last,f[maxn>>1],L,pi[maxn>>1];

int son[maxn][2],fa[maxn],len[maxn],d[maxn>>1],ld,rd;

char s[maxn>>1];

void add(int p,int x){

	int np=++tot; len[np]=len[p]+1,fa[np]=p; last=np;

	for(;p && !son[p][x];p=fa[p]) son[p][x]=np;

	if(!p) fa[np]=1;

	else{

		int q=son[p][x];

		if(len[q]==len[p]+1) fa[np]=q;

		else{

			int nq=++tot;

			memcpy(son[nq],son[q],sizeof(son[q]));

			fa[nq]=fa[q]; fa[q]=fa[np]=nq; len[nq]=len[p]+1;

			for(;son[p][x]==q;p=fa[p]) son[p][x]=nq;

		}

	}

}

bool check(int x){

	ld=rd=0;

	for(int i=1;i<=L;i++){f[i]=f[i-1];

		if(i>=x){

			while(ld<rd && f[d[rd-1]]-d[rd-1]<=f[i-x]-i+x) rd--;

			d[rd++]=i-x;

		}

		while(ld<rd && d[ld]<i-pi[i]) ld++;

		if(ld<rd) f[i]=max(f[i],f[d[ld]]-d[ld]+i);

	}

	return f[L]*10>=9*L;

}

int main(){

	File("a");

	scanf("%d %d",&n,&m); tot=1;

	for(int i=1,l;i<=m;i++){

		scanf("%s",s+1);

		last=1; l=strlen(s+1);

		for(int j=1;j<=l;j++) add(last,s[j]-'0');

	}

	for(int i=1,l,r,mid;i<=n;i++){

		scanf("%s",s+1);

		l=0; L=r=strlen(s+1);

		for(int j=1,p=1,le=0;j<=L;j++){

			while(p!=1 && !son[p][s[j]-'0']) p=fa[p],le=len[p];

			if(son[p][s[j]-'0']) p=son[p][s[j]-'0'],le++; pi[j]=le;

		}

		while(l!=r){

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

			if(check(mid)) l=mid;

			else r=mid-1;

		}

		printf("%d\n",l);

	}

	return 0;

}

巴特西

BZOJ 2806 【CTSC2012】 Cheat

最新文章

热门文章