BZOJ2806_Cheat

Ctsc2012的题目。做完感觉自己瞬间变高富帅了。

不过回想其实也觉得不难，想到用单调队列就很简单了，还有二分= =。呵

对于给出的一篇文章，如果你们将它分成若干段，并在所有长度不小于L的片段在字典中间出现的总长度和不小于原文的90%，那么这篇文章就可以被认为是熟悉的。这里要注意理解一下题意，如果你要算对于L这个长度熟悉。那么小于L的片段就不要去判断了，它肯定不熟悉。

这样我们就可以二分了，每次二分一个长度，看看能否使文章熟悉就好，最终输出答案。

怎么判断当前这个二分的答案能否使得文章熟悉呢？

其实这个问题，就是求把文章分段后的最大的匹配长度。这样由于存在策略最优的问题，而且显然可以递推，就是DP了。

如何DP呢？f[i]表示前面i个字符的最大匹配长度。对于当前我们考虑的状态，我们只要考虑它为某一段尾部最后一个字符就可以了。

同时后缀自动机可以在线秒算当前位置的最大匹配长度，假设i位置的最大匹配长度为len。

首先，f[i]=f[i-1]，因为i个位置的匹配长度肯定不会小于前一个位置的匹配长度。

其次，如果当前位置的匹配长度小于当前枚举的这个L值的话，当前状态也是不予考虑的。因为即使当做尾部最后一个字符也不算数。

再其次，当前状态的决策区间只可能是[i-len,i-L]。因为小于i-len的位置是不能匹配的。

再其次，每次进入一个点，我们都进行队尾的优化，可以优化么？可以。根据前面总共有多少个位置匹配不上来优化，如果一个前面的位置，落下的无法匹配的字符比后面一个位置的空字符还要多，那么它肯定不会在后面的决策总使用，直接从队尾拿出来就好了。

再其次，队首的优化就是判断队首的点时候在决策区间内，如果在的话，当前状态就一定是最优的了。也就是f[j]+i-j。因为在决策区间里的位置，后面的i-j的长度都是可以完美当做一段去匹配的。

再其次，没有了，直接判断是否满足90%的条件即可。

怒赞，ctsc题目果然做起来感觉不一样。

召唤代码君：

#include <iostream>

#include <cstdio>

#include <cstring>

#define maxn 2502000

using namespace std;

int next[maxn][3],pre[maxn],step[maxn];

int p,q,np,nq,cur,len,L;

int f[maxn];

int N,last,n,m;

int Q[maxn],bot,top;

char s[maxn];

void insert(int x)

{

	np=++N,p=last,step[np]=step[p]+1,last=np;

	for (; p!=-1 && next[p][x]==0; p=pre[p]) next[p][x]=np;

	if (p==-1) return;

	q=next[p][x];

	if (step[q]==step[p]+1) { pre[np]=q; return; }

	nq=++N,step[nq]=step[p]+1,pre[nq]=pre[q];

	for (int i=0; i<3; i++) next[nq][i]=next[q][i];

	pre[np]=pre[q]=nq;

	for (; p!=-1 && next[p][x]==q; p=pre[p]) next[p][x]=nq;

}

bool check(int limit)

{

	bot=1,top=0,f[0]=cur=len=0;

	for (int i=1; s[i]; i++)

	{

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

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

		for (; cur!=-1 && next[cur][k]==0; cur=pre[cur]) ;

		if (cur==-1) { cur=len=0; }

		len=min(len,step[cur])+1;//当前状态的最大匹配长度

		cur=next[cur][k];

		p=i-limit;

		if (p>=0)

		{

			while (bot<=top && Q[top]-f[Q[top]]>p-f[p]) top--;

			Q[++top]=p;

		}

		while (bot<=top && Q[bot]<i-len) bot++;

		if (bot<=top) f[i]=max(f[i],f[Q[bot]]+i-Q[bot]);

	}

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

}

int main()

{

	pre[0]=-1;

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

	while (m--)

	{

		scanf("%s",s);

		for (int i=0; s[i]; i++) insert(s[i]-'0');

		insert(2);

	}

	while (n--)

	{

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

		L=strlen(s+1);

		int l=0,r=L,mid;

		while (l<r)

		{

			mid=(l+r+1)/2;

			if (check(mid)) l=mid;

				else r=mid-1;

		}

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

	}

	return 0;

}

巴特西

BZOJ2806_Cheat

最新文章

热门文章