[NOI2015]品酒大会

本文主要是介绍[NOI2015]品酒大会，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
先对这个字符串求一下SA
考虑SA数组中第i位,暴力计算贡献就是向后枚举，然后计算枚举到的位与第i位之间height的最小值,然后对r==min(height)的贡献就是这一对数并且可以用他们的权值之积可以更新最大值
考虑height较大的是不会对height较小的有贡献，就可以从height大的到height小的依次计算
可以保证height较大的形成的集合通过当前height连在一起height最小值为当前height(已经排过序了)
可以用并查集维护
时间复杂度O(nlogn)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=300000+20;
typedef long long ll;
ll rnk[maxn],tp[maxn],sa[maxn],c[maxn];
ll height[maxn];
int fa[maxn];
char A[maxn];
ll maxx[maxn];
ll minn[maxn];
ll num[maxn];
ll ans1[maxn];
ll ans2[maxn];
int n;
ll v[maxn];
int tmp[maxn];
inline bool cmp(ll *a,int i,int j){int O1=sa[i]+j<=n?a[sa[i]+j]:-1;int O2=sa[i-1]+j<=n?a[sa[i-1]+j]:-1;return O1==O2&&a[sa[i]]==a[sa[i-1]];
}
inline void get_sa(){int m=256;ll *x=rnk,*y=tp;for(int i=1;i<=n;i++)x[i]=A[i],y[i]=A[i];for(int i=0;i<=m;i++)c[i]=0;for(int i=1;i<=n;i++)c[x[i]]++;for(int i=1;i<=m;i++)c[i]+=c[i-1];for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;for(int j=1;j<=n;j<<=1){ll p=0;for(int i=n-j+1;i<=n;i++)y[++p]=i;for(int i=1;i<=n;i++)if(sa[i]>j)y[++p]=sa[i]-j;for(int i=0;i<=m;i++)c[i]=0;for(int i=1;i<=n;i++)c[x[y[i]]]++;for(int i=1;i<=m;i++)c[i]+=c[i-1];for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i];p=1;swap(x,y);x[sa[1]]=1;for(int i=2;i<=n;i++)x[sa[i]]=cmp(y,i,j)?p:++p;m=p;if(m>=n){//printf("%d\n",j);break;}}
}
inline bool comp(int x,int y){return height[x]>height[y];
}
inline void get_height(){for(int i=1;i<=n;i++)  rnk[sa[i]]=i;  int h=0;  for(int i=1;i<=n;i++){  --h=h<0?0:h;  int u=sa[rnk[i]-1];  while(A[u+h]==A[i+h])  h++;  height[rnk[i]]=h;  }  
}
inline int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[fa[fa[x]]]);
}
inline void calc(int x){int l=find(x-1),r=find(x);ans1[height[x]]+=num[l]*num[r];ans2[height[x]]=max(ans2[height[x]],max(maxx[l]*maxx[r],minn[l]*minn[r]));fa[l]=r;maxx[r]=max(maxx[r],maxx[l]);minn[r]=min(minn[r],minn[l]);num[r]+=num[l];
}
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);scanf("%d",&n);for(int i=0;i<n;i++)ans2[i]=-(1LL<<61);scanf("%s",A+1);for(int i=1;i<=n;i++)scanf("%lld",&v[i]);get_sa();get_height();for(int i=1;i<=n;i++){fa[i]=tmp[i]=i;maxx[i]=v[sa[i]];num[i]=1;minn[i]=v[sa[i]];}sort(tmp+1,tmp+n+1,comp);for(int i=1;i<=n;i++)calc(tmp[i]);for(int i=n-2;i>=0;i--){ans1[i]+=ans1[i+1];ans2[i]=max(ans2[i],ans2[i+1]);}for(int i=0;i<n;i++){if(!ans1[i])ans2[i]=0;printf("%lld %lld\n",ans1[i],ans2[i]);}
return 0;
}

这篇关于[NOI2015]品酒大会的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---