●BZOJ 2119 股市的预测

题链：

http://www.lydsy.com/JudgeOnline/problem.php?id=2119

题解：

这个题很好的。

首先把序列转化为差分序列，
问题转化为找到合法的子序列，使得去除最中间的 M长度，剩下的头尾完全相同。
枚举重现的长度 len，
然后在序列中每len个长度打一个标记，不难发现，如题所述的A部分一定只包含一个标记点。
然后枚举每个被标记的点 i，得到对应的 j=i+len+M，
然后求出 i和 j 向前向后可匹配的最大长度 L,R
那么对答案的贡献即为 max(0,(min(L-1,len-1)+min(R-1,len-1)+1)-len+1)

要记得离散化。要建两个后缀数组（正逆向）。可以不用long long。

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 50050

#define filein(x) freopen(#x".in","r",stdin);

#define fileout(x) freopen(#x".out","w",stdout);

using namespace std;

int ta[MAXN],tb[MAXN],cc[MAXN],log2[MAXN];

struct SAY{

	int sa[MAXN],rak[MAXN],hei[MAXN],stm[MAXN][18],*x,*y,h;

	void build(int N,int M,int *a){

		x=ta; y=tb; h=0; a[N]=-1;

		for(int i=0;i<M;i++) cc[i]=0;

		for(int i=0;i<N;i++) cc[x[i]=a[i]]++;

		for(int i=1;i<M;i++) cc[i]+=cc[i-1];

		for(int i=N-1;i>=0;i--) sa[--cc[x[i]]]=i;

		for(int k=1,p;p=0,k<N;k<<=1){

			for(int i=N-k;i<N;i++) y[p++]=i;

			for(int i=0;i<N;i++) if(sa[i]>=k) y[p++]=sa[i]-k;

			for(int i=0;i<M;i++) cc[i]=0;

			for(int i=0;i<N;i++) cc[x[y[i]]]++;

			for(int i=1;i<M;i++) cc[i]+=cc[i-1];

			for(int i=N-1;i>=0;i--) sa[--cc[x[y[i]]]]=y[i];

			swap(x,y); y[N]=-1; x[sa[0]]=0; M=1;

			for(int i=1;i<N;i++)

				x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?M-1:M++;

			if(M>=N) break;

		}

		for(int i=0;i<N;i++) rak[sa[i]]=i;

		for(int i=0,j;i<N;i++){

			if(h) h--;

			if(rak[i]){

				j=sa[rak[i]-1];

				while(a[i+h]==a[j+h]) h++;

			}

			stm[rak[i]][0]=hei[rak[i]]=h;

		}

		for(int k=1;k<=log2[N];k++)

			for(int i=(1<<k)-1;i<N;i++)

				stm[i][k]=min(stm[i-(1<<(k-1))][k-1],stm[i][k-1]);

	}

	int query(int l,int r){

		static int k;

		l=rak[l]; r=rak[r];

		if(l>r) swap(l,r); l++;

		k=log2[r-l+1];

		return min(stm[l+(1<<k)-1][k],stm[r][k]);

	}

}suf1,suf2;

int A[MAXN],B[MAXN],tmp[MAXN];

int N,ANS,cnt,D;

int main()

{

	scanf("%d%d",&N,&D);

	log2[1]=0; for(int i=2;i<=50000;i++) log2[i]=log2[i>>1]+1;

	for(int i=0;i<N;i++) scanf("%d",&A[i]);

	for(int i=0;i<N-1;i++) A[i]=A[i+1]-A[i],tmp[i]=A[i]; N--;

	sort(tmp,tmp+N); cnt=unique(tmp,tmp+N)-tmp;

	for(int i=0;i<N;i++) A[i]=lower_bound(tmp,tmp+cnt,A[i])-tmp;

	suf1.build(N,N+10,A);

	for(int i=0;i<N;i++) B[N-1-i]=A[i];

	suf2.build(N,N+10,B);

	for(int len=1,L,R;len<N/2;len++)

		for(int i=0,j;i<N;i+=len){

			j=i+len+D; if(j>=N) break;

			L=suf1.query(i,j);

			R=suf2.query(N-1-i,N-1-j);

			ANS+=max(0,min(L-1,len-1)+min(R-1,len-1)+1-len+1);

		}

	printf("%d",ANS);

	return 0;

}

巴特西

●BZOJ 2119 股市的预测

最新文章

热门文章