首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。