【BZOJ4199】【NOI2015】品酒大会（后缀数组）

时间：2022-04-20 16:30:12

【BZOJ4199】【NOI2015】品酒大会

题面

BZOJ

Uoj

洛谷

题解

考虑最裸的暴力

枚举每次的长度

以及两个开始的位置

检查以下是否满足条件，如果可以直接更新答案

复杂度\(O(n^3)\)

\(15～20\)分

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define MAX 320000

inline int read()

{

    int x=0,t=1;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n;

char s[MAX];

int lg[MAX],v[MAX];

struct SA

{

	int p[20][MAX],a[MAX];

	int x[MAX],y[MAX],t[MAX];

	int SA[MAX],height[MAX],rk[MAX];

	bool cmp(int i,int j,int k){return y[i]==y[j]&&y[i+k]==y[j+k];}

	void init()

		{

			memset(SA,0,sizeof(SA));

			memset(height,0,sizeof(height));

			memset(rk,0,sizeof(rk));

			memset(x,0,sizeof(x));

			memset(y,0,sizeof(y));

			memset(t,0,sizeof(t));

			memset(a,0,sizeof(a));

		}

	void GetSA()

		{

			int m=50;

			for(int i=1;i<=n;++i)t[x[i]=a[i]]++;

			for(int i=1;i<=m;++i)t[i]+=t[i-1];

			for(int i=n;i>=1;--i)SA[t[x[i]]--]=i;

			for(int k=1;k<=n;k<<=1)

			{

				int p=0;

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

				for(int i=1;i<=n;++i)if(SA[i]>k)y[++p]=SA[i]-k;

				for(int i=0;i<=m;++i)t[i]=0;

				for(int i=1;i<=n;++i)t[x[y[i]]]++;

				for(int i=1;i<=m;++i)t[i]+=t[i-1];

				for(int i=n;i>=1;--i)SA[t[x[y[i]]]--]=y[i];

				swap(x,y);

				x[SA[1]]=p=1;

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

					x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;

				if(p>=n)break;

				m=p;

			}

			for(int i=1;i<=n;++i)rk[SA[i]]=i;

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

			{

				if(j)--j;

				while(a[i+j]==a[SA[rk[i]-1]+j])++j;

				height[rk[i]]=j;

			}

		}

	void Pre()

		{

			memset(p,63,sizeof(p));

			for(int i=1;i<=n;++i)p[0][i]=height[i];

			for(int j=1;j<20;++j)

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

					p[j][i]=min(p[j-1][i],p[j-1][i+(1<<(j-1))]);

		}

	int Query(int i,int j)

		{

			return min(p[lg[j-i+1]][i],p[lg[j-i+1]][j-(1<<lg[j-i+1])+1]);

		}

	int lcp(int i,int j)

		{

			int l=min(rk[i],rk[j])+1,r=max(rk[i],rk[j]);

			return Query(l,r);

		}

}SA;

int main()

{

	n=read();

	for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;

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

	for(int i=1;i<=n;++i)SA.a[i]=s[i]-96;

	SA.GetSA();SA.Pre();

	for(int i=1;i<=n;++i)v[i]=read();

	for(int len=0;len<n;++len)

	{

		ll ans1=0,ans2=-1e18;

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

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

			{

				if(SA.lcp(i,j)>=len)

					ans1++,ans2=max(ans2,1ll*v[i]*v[j]);

			}

		if(ans1)printf("%lld %lld\n",ans1,ans2);

		else

		{

			for(int j=len;j<n;++j)puts("0 0");

			break;

		}

	}

	return 0;

}

继续考虑，

观察到如果两杯酒是\(k\)相似的

那么，他们一定是\(j(j<=k)\)相似的

随意只需要枚举两杯酒

检查他们是多少相似

然后做一个前缀和就好了

复杂度\(O(n^2)\)

\(40\)分

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define MAX 320000

inline int read()

{

    int x=0,t=1;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n;

char s[MAX];

int lg[MAX],v[MAX];

ll ans1[MAX],ans2[MAX];

struct SA

{

	int p[20][MAX],a[MAX];

	int x[MAX],y[MAX],t[MAX];

	int SA[MAX],height[MAX],rk[MAX];

	bool cmp(int i,int j,int k){return y[i]==y[j]&&y[i+k]==y[j+k];}

	void init()

		{

			memset(SA,0,sizeof(SA));

			memset(height,0,sizeof(height));

			memset(rk,0,sizeof(rk));

			memset(x,0,sizeof(x));

			memset(y,0,sizeof(y));

			memset(t,0,sizeof(t));

			memset(a,0,sizeof(a));

		}

	void GetSA()

		{

			int m=50;

			for(int i=1;i<=n;++i)t[x[i]=a[i]]++;

			for(int i=1;i<=m;++i)t[i]+=t[i-1];

			for(int i=n;i>=1;--i)SA[t[x[i]]--]=i;

			for(int k=1;k<=n;k<<=1)

			{

				int p=0;

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

				for(int i=1;i<=n;++i)if(SA[i]>k)y[++p]=SA[i]-k;

				for(int i=0;i<=m;++i)t[i]=0;

				for(int i=1;i<=n;++i)t[x[y[i]]]++;

				for(int i=1;i<=m;++i)t[i]+=t[i-1];

				for(int i=n;i>=1;--i)SA[t[x[y[i]]]--]=y[i];

				swap(x,y);

				x[SA[1]]=p=1;

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

					x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;

				if(p>=n)break;

				m=p;

			}

			for(int i=1;i<=n;++i)rk[SA[i]]=i;

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

			{

				if(j)--j;

				while(a[i+j]==a[SA[rk[i]-1]+j])++j;

				height[rk[i]]=j;

			}

		}

	void Pre()

		{

			memset(p,63,sizeof(p));

			for(int i=1;i<=n;++i)p[0][i]=height[i];

			for(int j=1;j<20;++j)

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

					p[j][i]=min(p[j-1][i],p[j-1][i+(1<<(j-1))]);

		}

	int Query(int i,int j)

		{

			return min(p[lg[j-i+1]][i],p[lg[j-i+1]][j-(1<<lg[j-i+1])+1]);

		}

	int lcp(int i,int j)

		{

			int l=min(rk[i],rk[j])+1,r=max(rk[i],rk[j]);

			return Query(l,r);

		}

}SA;

int main()

{

	n=read();

	for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;

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

	for(int i=1;i<=n;++i)SA.a[i]=s[i]-96;

	SA.GetSA();SA.Pre();

	for(int i=1;i<=n;++i)v[i]=read();

	memset(ans2,-63,sizeof(ans2));

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

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

		{

			int len=SA.lcp(i,j);

			ans1[0]++;ans1[len+1]--;

			ans2[len]=max(ans2[len],1ll*v[i]*v[j]);

		}

	for(int i=1;i<=n;++i)ans1[i]+=ans1[i-1];

	for(int i=n;i>=0;--i)ans2[i]=max(ans2[i],ans2[i+1]);

	for(int i=0;i<n;++i)printf("%lld %lld\n",ans1[i],!ans1[i]?0:ans2[i]);

	return 0;

}

如果我们求出\(height\)数组之后

枚举一个长度\(len\)，按照\(height\)分类

如果一段连续的\(height\)都不小于了\(len\)

证明这一段都会产生贡献

所以记录这一段产生的贡献，

至于最大值，就在这一段里面记录最大，次大，最小，次小值

拼起来算一下

因为\(height\)最大值可以很小

所以这样可以过\(50\)分

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define MAX 320000

inline int read()

{

    int x=0,t=1;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n;

char s[MAX];

int lg[MAX],v[MAX];

ll ans1[MAX],ans2[MAX];

struct SA

{

	int p[20][MAX],a[MAX];

	int x[MAX],y[MAX],t[MAX];

	int SA[MAX],height[MAX],rk[MAX];

	bool cmp(int i,int j,int k){return y[i]==y[j]&&y[i+k]==y[j+k];}

	void init()

		{

			memset(SA,0,sizeof(SA));

			memset(height,0,sizeof(height));

			memset(rk,0,sizeof(rk));

			memset(x,0,sizeof(x));

			memset(y,0,sizeof(y));

			memset(t,0,sizeof(t));

			memset(a,0,sizeof(a));

		}

	void GetSA()

		{

			int m=50;

			for(int i=1;i<=n;++i)t[x[i]=a[i]]++;

			for(int i=1;i<=m;++i)t[i]+=t[i-1];

			for(int i=n;i>=1;--i)SA[t[x[i]]--]=i;

			for(int k=1;k<=n;k<<=1)

			{

				int p=0;

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

				for(int i=1;i<=n;++i)if(SA[i]>k)y[++p]=SA[i]-k;

				for(int i=0;i<=m;++i)t[i]=0;

				for(int i=1;i<=n;++i)t[x[y[i]]]++;

				for(int i=1;i<=m;++i)t[i]+=t[i-1];

				for(int i=n;i>=1;--i)SA[t[x[y[i]]]--]=y[i];

				swap(x,y);

				x[SA[1]]=p=1;

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

					x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;

				if(p>=n)break;

				m=p;

			}

			for(int i=1;i<=n;++i)rk[SA[i]]=i;

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

			{

				if(j)--j;

				while(a[i+j]==a[SA[rk[i]-1]+j])++j;

				height[rk[i]]=j;

			}

		}

	void Pre()

		{

			memset(p,63,sizeof(p));

			for(int i=1;i<=n;++i)p[0][i]=height[i];

			for(int j=1;j<20;++j)

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

					p[j][i]=min(p[j-1][i],p[j-1][i+(1<<(j-1))]);

		}

	int Query(int i,int j)

		{

			return min(p[lg[j-i+1]][i],p[lg[j-i+1]][j-(1<<lg[j-i+1])+1]);

		}

	int lcp(int i,int j)

		{

			int l=min(rk[i],rk[j])+1,r=max(rk[i],rk[j]);

			return Query(l,r);

		}

}SA;

bool cmp(int a,int b){return SA.height[a]>SA.height[b];}

int id[MAX];

void update(int x,int &zd,int &cd,int &zx,int &cx)

{

	if(x>zd)cd=zd,zd=x;

	else if(x>cd)cd=x;

	if(x<zx)cx=zx,zx=x;

	else if(x<cx)cx=x;

}

ll check_max(int zd,int cd,int zx,int cx)

{

	ll ret=-1e18;

	if(zd!=-2e9&&cd!=-2e9)ret=max(ret,1ll*zd*cd);

	if(zx!=+2e9&&cx!=+2e9)ret=max(ret,1ll*zx*cx);

	return ret;

}

int main()

{

	n=read();

	for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;

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

	for(int i=1;i<=n;++i)SA.a[i]=s[i]-96;

	SA.GetSA();SA.Pre();

	for(int i=1;i<=n;++i)v[i]=read(),id[i]=i;;

	memset(ans2,-63,sizeof(ans2));

	sort(&id[1],&id[n+1],cmp);

	for(int len=0;len<=n;++len)

	{

		int zd,zx,cd,cx,cnt=0;

		zd=cd=-2e9;zx=cx=2e9;

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

		{

			if(SA.height[i]<len)

			{

				ans2[len]=max(ans2[len],check_max(zd,cd,zx,cx));

				zd=cd=-2e9;zx=cx=2e9;

				cnt=0;

			}

			else

			{

				update(v[SA.SA[i]],zd,cd,zx,cx);

				if(!cnt)update(v[SA.SA[i-1]],zd,cd,zx,cx);

				ans1[len]+=cnt;

				if(!cnt)ans1[len]++,cnt++;

				cnt++;

			}

		}

		ans2[len]=max(ans2[len],check_max(zd,cd,zx,cx));

		if(!ans1[len])break;

	}

	for(int i=n;i>=0;--i)ans2[i]=max(ans2[i],ans2[i+1]);

	for(int i=0;i<n;++i)printf("%lld %lld\n",ans1[i],!ans1[i]?0:ans2[i]);

	return 0;

}

想想上面的东西怎么优化？

我们每次从小往大枚举

如果有一段连续的\(height\)都大于了\(len\)

那么，我们在\(0..len-1\)的时候也都会被枚举一遍

所以，我们考虑从大到小枚举

如果有一段连续的区间，那我们可以直接把他们缩成一个区间

同时记录这个区间的大小，以及最大，最小值

这样的话，每次的枚举可以把一段区间变成一个点

考虑这个思路，也不可能每次扫一边所有的值

所以直接把\(height\)从大到小排序

每次处理一个\(height\)就合并两个集合

并且计算产生的贡献

最后求一个后缀和就好

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define MAX 320000

inline int read()

{

    int x=0,t=1;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n,v[MAX];

char s[MAX];

ll ans1[MAX],ans2[MAX];

struct SA

{

	int a[MAX];

	int x[MAX],y[MAX],t[MAX];

	int SA[MAX],height[MAX],rk[MAX];

	bool cmp(int i,int j,int k){return y[i]==y[j]&&y[i+k]==y[j+k];}

	void GetSA()

		{

			int m=50;

			for(int i=1;i<=n;++i)t[x[i]=a[i]]++;

			for(int i=1;i<=m;++i)t[i]+=t[i-1];

			for(int i=n;i>=1;--i)SA[t[x[i]]--]=i;

			for(int k=1;k<=n;k<<=1)

			{

				int p=0;

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

				for(int i=1;i<=n;++i)if(SA[i]>k)y[++p]=SA[i]-k;

				for(int i=0;i<=m;++i)t[i]=0;

				for(int i=1;i<=n;++i)t[x[y[i]]]++;

				for(int i=1;i<=m;++i)t[i]+=t[i-1];

				for(int i=n;i>=1;--i)SA[t[x[y[i]]]--]=y[i];

				swap(x,y);

				x[SA[1]]=p=1;

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

					x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;

				if(p>=n)break;

				m=p;

			}

			for(int i=1;i<=n;++i)rk[SA[i]]=i;

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

			{

				if(j)--j;

				while(a[i+j]==a[SA[rk[i]-1]+j])++j;

				height[rk[i]]=j;

			}

		}

}SA;

bool cmp(int a,int b){return SA.height[a]>SA.height[b];}

int id[MAX];

int f[MAX],mm[MAX],mi[MAX],size[MAX];

ll ans[MAX];

int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}

void Merge(int x,int y,int len)

{

	x=getf(x);y=getf(y);

	f[y]=x;

	ans1[len]+=1ll*size[x]*size[y];

	size[x]+=size[y];

	ans[x]=max(ans[x],ans[y]);

	ans[x]=max(ans[x],max(1ll*mm[x]*mm[y],1ll*mi[x]*mi[y]));

	ans[x]=max(ans[x],max(1ll*mm[x]*mi[y],1ll*mi[x]*mm[y]));

	mm[x]=max(mm[x],mm[y]);

	mi[x]=min(mi[x],mi[y]);

	ans2[len]=max(ans2[len],ans[x]);

}

int main()

{

	n=read();

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

	for(int i=1;i<=n;++i)SA.a[i]=s[i]-96;

	SA.GetSA();

	for(int i=1;i<=n;++i)v[i]=read(),id[i]=i;;

	for(int i=1;i<=n;++i)f[i]=i,size[i]=1,mm[i]=mi[i]=v[i],ans[i]=-1e18;

	memset(ans2,-63,sizeof(ans2));

	sort(&id[2],&id[n+1],cmp);

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

		Merge(SA.SA[id[i]],SA.SA[id[i]-1],SA.height[id[i]]);

	for(int i=n;i>=0;--i)ans1[i]+=ans1[i+1];

	for(int i=n;i>=0;--i)ans2[i]=max(ans2[i],ans2[i+1]);

	for(int i=0;i<n;++i)printf("%lld %lld\n",ans1[i],!ans1[i]?0:ans2[i]);

	return 0;

}

相关文章