BZOJ 2806 cheat

首先这个题目显然是要二分转换成判断可行性的

之后我们考虑DP

设f(i)表示 1->i 熟悉的子串的长度的最大值

那么对于i这个点，要么不在熟悉的子串中，要么在熟悉的子串中

所以得到

f(i)=max(f(i-1),f(j)+i-j);

其中i-j是划分的熟悉的子串的长度，要满足以下条件：

1、i-j>=k (k为二分出来的值）

2、[j+1,i]这段串是给定标准文章库的一个子串

我们又知道若[j+1,i]是一个满足条件的子串，那么[j+2,i]也一定满足条件

假设我们已知最小的p满足[p+1,i]是一个满足条件的子串，定义L=i-p

那么条件2转化为 i-j<=L

求特定区间的最大值，且左右端点是单调的，我们是可以用单调队列的

那么现在问题就是求解最小的p使得[p+1,i]满足条件

即求解给定串S的一个前缀的最长满足条件的后缀，这时可以用后缀自动机做的

每次只需要在上次的基础上顺着parent树向上寻找匹配就可以了

注意：当寻找到SAM上的一个可匹配的节点时，当前的L并不一定是这个合法节点的len值+1

因为SAM上的节点的len值为其可以取得的长度的最大值，它有可能比上一次的L要大

所以我的代码对这种情况进行了一下处理QAQ

#include<cstdio>

#include<cstring>

#include<iostream>

#include<cstdlib>

#include<algorithm>

using namespace std;

const int maxn=1100010;

int n,m,cnt,la,len;

char s[maxn];

struct Node{

	int next[3];//0 1 2

	int len,link;

}st[maxn<<1];

int Q[maxn],h,t;

int f[maxn];

void init(){

	cnt=la=0;

	st[0].link=-1;

}

void add(int c){

	int cur=++cnt;

	st[cur].len=st[la].len+1;

	int p;

	for(p=la;p!=-1&&st[p].next[c]==0;p=st[p].link)st[p].next[c]=cur;

	if(p==-1)st[cur].link=0;

	else{

		int q=st[p].next[c];

		if(st[q].len==st[p].len+1)st[cur].link=q;

		else{

			int clone=++cnt;

			st[clone]=st[q];

			st[clone].len=st[p].len+1;

			for(;p!=-1&&st[p].next[c]==q;p=st[p].link)st[p].next[c]=clone;

			st[q].link=st[cur].link=clone;

		}

	}la=cur;

}

bool check(int k){

	h=1;t=0;f[0]=0;

	int p=0,L=0;

	for(int i=1;i<=len;++i){

		if(i>=k){

			while(h<=t&&f[Q[t]]-Q[t]<f[i-k]-(i-k))t--;

			Q[++t]=i-k;

		}

		int now=s[i]-'0';

		int cur=p;

		for(;p!=-1&&st[p].next[now]==0;p=st[p].link);

		f[i]=f[i-1];

		if(p==-1){p=0;L=0;continue;}

		if(p==cur)L++;

		else L=st[p].len+1;

		p=st[p].next[now];

		while(h<=t&&i-Q[h]>L)h++;

		if(h<=t)f[i]=max(f[i],f[Q[h]]-Q[h]+i);

	}return len*9<=f[len]*10;

}

int main(){

	scanf("%d%d",&n,&m);init();

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

		scanf("%s",s+1);len=strlen(s+1);

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

		add(2);

	}

	while(n--){

		scanf("%s",s+1);len=strlen(s+1);

		int L=0,R=len;

		while(L<R){

			int mid=L+((R-L+1)>>1);

			if(check(mid))L=mid;

			else R=mid-1;

		}printf("%d\n",L);

	}return 0;

}

巴特西

BZOJ 2806 cheat

最新文章

热门文章