首页 > 代码库 > BZOJ2806: [Ctsc2012]Cheat

BZOJ2806: [Ctsc2012]Cheat

传送门

写CTSC的题真是爽啊..

首先把所有库里的串连起来建一颗SAM。然后对于每个串都在SAM上跑一遍,记录下每个位置的最大匹配长度。

然后二分出L,用DP验证。

如果设$f[i]$表示第$i$个点所能匹配的最长的长度,那么很容易得到一个方程:$f[i]=max\{ f[j]+i-j\}$,限制条件为$i-Max[i] \leq j \leq i-L$。

这个方程是$O(N^2)$的 ,太暴力了,我们可以发现,$i-L$是递增的,所以考虑用单调队列优化。

每次加入一个点前,检查一下队尾,因为$f[i]=(f[best]-best)+i$,所以每次比较一下$best$点,不够优的话弹出。

然后检查一下队首,不合法同样弹出。

好了,终于做完了。

//BZOJ 2806//by Cydiater//2017.1.21#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <string>#include <ctime>#include <queue>#include <map>#include <iomanip>#include <algorithm>#include <bitset>#include <set>#include <vector>using namespace std;#define ll long long#define up(i,j,n)	for(int i=j;i<=n;i++)#define down(i,j,n)	for(int i=j;i>=n;i--)#define cmax(a,b)	a=max(a,b)#define cmin(a,b)	a=min(a,b)const int MAXN=1e6+5;const int oo=0x3f3f3f3f;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int N,M,Max[MAXN],q[MAXN],head,tail,len,f[MAXN];char s[MAXN];struct SAM{	int son[MAXN][3],step[MAXN],pre[MAXN],now,cnt;	SAM(){now=cnt=1;}	void Extend(int nxt){		int p=now,np=++cnt;now=np;		step[np]=step[p]+1;		for(;!son[p][nxt]&&p;p=pre[p])son[p][nxt]=np;		if(!p)pre[np]=1;		else{			int q=son[p][nxt],nq;			if(step[q]==step[p]+1)pre[np]=q;			else{				step[(nq=++cnt)]=step[p]+1;				memcpy(son[nq],son[q],sizeof(son[q]));				pre[nq]=pre[q];				pre[np]=pre[q]=nq;				for(;son[p][nxt]==q;p=pre[p])son[p][nxt]=nq;			}		}	}	void Go(){		now=1;int maxx=0;		memset(Max,0,sizeof(Max));		up(i,1,len){			int nxt=s[i]-‘0‘;			for(;!son[now][nxt]&&now;now=pre[now],maxx=step[now]);			if(!now){				now=1;maxx=0;				continue;			}			now=son[now][nxt];maxx++;			cmax(Max[i],maxx);		}	}}sam;namespace solution{	void Prepare(){		N=read();M=read();		up(i,1,M){			scanf("%s",s+1);			int len=strlen(s+1);			up(j,1,len)sam.Extend(s[j]-‘0‘);			sam.Extend(2);//cut		}	}	bool check(int L){		head=1;tail=0;f[0]=0;		up(i,1,len){			int pos=i-L;			f[i]=f[i-1];			if(pos<0)continue;			while(head<=tail&&q[tail]-f[q[tail]]>pos-f[pos])tail--;			q[++tail]=pos;			while(head<=tail&&q[head]<i-Max[i])head++;			if(head<=tail)cmax(f[i],f[q[head]]+i-q[head]);		}		return f[len]*10>=len*9;	}	void Solve(){		while(N--){			scanf("%s",s+1);len=strlen(s+1);			sam.Go();			int leftt=0,rightt=len,mid;			while(leftt+1<rightt){				int mid=(leftt+rightt)>>1;				if(check(mid))	leftt=mid;				else 		rightt=mid;			}			if(check(rightt))	printf("%d\n",rightt);			else 			printf("%d\n",leftt);		}	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	Prepare();	Solve();	return 0;}

 

BZOJ2806: [Ctsc2012]Cheat