BZOJ4650: [Noi2016]优秀的拆分

考场上没秒的话多拿5分并不划算的样子。

思想其实很简单嘛。

要统计答案，求以每个位置开始和结束的AA串数量就好了。那么枚举AA中A的长度L，每L个字符设一个关键点，这样AA一定经过相邻的两个关键点。计算出相邻关键点的最长公共前后缀，把对应的位置区间加一下。

求lcp和lcs可以用后缀数组，也可以用hash。

UPD：UOJ上有人sxbk把原来的hash卡了，稍微改了下。其实base随机就没事了，然而BZOJ上并不能调用time(0)。

#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

const int N=30005;

const int p=1e9+93;

ll f[N][2],g[N][2];

bool jud(int i1,int j1,int i2,int j2){

	return f[j1][1]-f[i1][1]*g[j1-i1][1]==f[j2][1]-f[i2][1]*g[j2-i2][1]&&0==(f[j1][0]+(p-f[i1][0])*g[j1-i1][0]+p-f[j2][0]+f[i2][0]*g[j2-i2][0])%p;

}

char z[N];

int a[N],b[N];

int main(){

	g[0][0]=1;

	g[0][1]=1;

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

		g[i][0]=2003*g[i-1][0]%p;

		g[i][1]=2011*g[i-1][1];

	}

	int q;

	scanf("%d",&q);

	while(q--){

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

		int n=strlen(z+1);

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

			f[i][0]=(z[i]+2003*f[i-1][0])%p;

			f[i][1]=z[i]+2011*f[i-1][1];

		}

		fill_n(a+1,n,0);

		fill_n(b+1,n,0);

		for(int i=1;i<=n/2;++i)

			for(int j=1;j<=n-i;j+=i)

				if(z[j]==z[j+i]){

					int l=0,r=min(i,j);

					while(l!=r){

						int m=l+r+1>>1;

						if(jud(j-m,j,j+i-m,j+i))

							l=m;

						else

							r=m-1;

					}

					int u=j-l+1;

					l=0,r=min(i-1,n-j-i);

					while(l!=r){

						int m=l+r+1>>1;

						if(jud(j,j+m,j+i,j+i+m))

							l=m;

						else

							r=m-1;

					}

					int v=j+l+1;

					if(u+i<=v){

						++a[u];

						--a[v-i+1];

						++b[u+i*2-1];

						--b[v+i];

					}

				}

		ll s=0;

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

			a[i]+=a[i-1];

			b[i]+=b[i-1];

			s+=a[i]*b[i-1];

		}

		printf("%lld\n",s);

	}

}

巴特西

BZOJ4650: [Noi2016]优秀的拆分

最新文章

热门文章