BZOJ4199：[NOI2015]品酒大会—

一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。

在大会的晚餐上，调酒师 Rainbow 调制了 n 杯鸡尾酒。这 n 杯鸡尾酒排成一行，其中第 n 杯酒 (1 ≤ i ≤ n) 被贴上了一个标签si，每个标签都是 26 个小写英文字母之一。设 str(l, r)表示第 l 杯酒到第 r 杯酒的 r − l + 1 个标签顺次连接构成的字符串。若 str(p, po) = str(q, qo)，其中 1 ≤ p ≤ po ≤ n, 1 ≤ q ≤ qo ≤ n, p ≠ q, po − p + 1 = qo − q + 1 = r ，则称第 p 杯酒与第 q 杯酒是“ r 相似” 的。当然两杯“ r 相似”(r > 1)的酒同时也是“ 1 相似”、“ 2 相似”、……、“ (r − 1) 相似”的。特别地，对于任意的 1 ≤ p , q ≤ n ， p ≠ q ，第 p 杯酒和第 q 杯酒都是“ 0 相似”的。

在品尝环节上，品酒师 Freda 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了“首席品酒家”的称号，其中第 i 杯酒 (1 ≤ i ≤ n) 的美味度为 ai 。现在 Rainbow 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 p 杯酒与第 q 杯酒调兑在一起，将得到一杯美味度为 ap*aq 的酒。现在请各位品酒师分别对于 r = 0,1,2, ⋯ , n − 1 ，统计出有多少种方法可以选出 2 杯“ r 相似”的酒，并回答选择 2 杯“ r 相似”的酒调兑可以得到的美味度的最大值。

参考：https://blog.csdn.net/alxpcun/article/details/50482493

题意很绕，看了半个小时没看懂求助题解得到了一个言简意赅的题意：

后缀都有价值，找到两个后缀，他们的公共前缀长为r则称他们"r"相似，求对于所有r取值有多少个"r"相似以及两个后缀价值积最大。

暴力：枚举r，用height数组分块，对于大小为n的块显然是有n*(n-1)/2对合法解，同时维护块的最大次大值和最小次小值来更新答案即可。

（因为价值有负数，所以不仅要考虑最大值的乘积，还要考虑最小值的乘积。）

正解：我们知道height小值会影响height大值的影响，换言之大值不会影响小值。

所以我们对height数组排序，从后往前枚举r，每次继承前一个r的所有答案开始更新。

用并查集维护一下当前height的后缀之间的关系，这样在整个并查集里面都是两两为"r"相似的对。

#include<cstdio>

#include<cmath>

#include<iostream>

#include<vector>

#include<cstring>

#include<algorithm>

#include<cctype>

using namespace std;

typedef long long ll;

const int N=3e5+;

const ll INF=1e18;

char s[N];

int n,m,rk[N],sa[N],w[N],fa[N],height[N];

ll a[N],ans[N][],size[N],maxn[N],minn[N];

struct node{

    int h,x,y;

}g[N];

inline bool cmp(node wa,node wb){

    return wa.h>wb.h;

}

inline bool pan(int *x,int i,int j,int k){

    int ti=i+k<n?x[i+k]:-;

    int tj=j+k<n?x[j+k]:-;

    return ti==tj&&x[i]==x[j];

}

void SA_init(){

    int *x=rk,*y=height,r=;

    for(int i=;i<r;i++)w[i]=;

    for(int i=;i<n;i++)w[s[i]]++;

    for(int i=;i<r;i++)w[i]+=w[i-];

    for(int i=n-;i>=;i--)sa[--w[s[i]]]=i;

    r=;x[sa[]]=;

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

    x[sa[i]]=s[sa[i]]==s[sa[i-]]?r-:r++;

    for(int k=;r<n;k<<=){

    int yn=;

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

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

        if(sa[i]>=k)y[yn++]=sa[i]-k;

    for(int i=;i<r;i++)w[i]=;

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

    for(int i=;i<r;i++)w[i]+=w[i-];

    for(int i=n-;i>=;i--)sa[--w[x[y[i]]]]=y[i];

    swap(x,y);r=;x[sa[]]=;

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

        x[sa[i]]=pan(y,sa[i],sa[i-],k)?r-:r++;

    }

}

void height_init(){

    int i,j,k=;

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

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

    if(k)k--;

    int j=sa[rk[i]-];

    while(s[i+k]==s[j+k])k++;

    height[rk[i]]=k;

    }

}

int find(int x){

    if(x==fa[x])return x;

    return fa[x]=find(fa[x]);

}

void unionn(int x,int y){

    if(size[x]>size[y])swap(x,y);

    fa[x]=y,size[y]+=size[x];

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

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

}

void solve(){

    for(int i=;i<=n;i++)g[i-]=(node){height[i],i,i-};

    sort(g+,g+n,cmp);

    for(int i=g[].h,j=;i>=;i--){

    ans[i][]=ans[i+][];ans[i][]=ans[i+][];

    for(;j<n&&g[j].h==i;j++){

        int x=find(g[j].x),y=find(g[j].y);

        if(x==y)continue;

        ans[i][]=max(ans[i][],maxn[x]*maxn[y]);

        ans[i][]=max(ans[i][],minn[x]*minn[y]);

        ans[i][]+=size[x]*size[y];

        unionn(x,y);

    }

    }

}

int main(){

    scanf("%d%s",&n,s);

    for(int i=;i<=n;i++)ans[i][]=-INF;

    s[n++]=;

    SA_init();

    n--;

    height_init();

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

    scanf("%lld",&a[i]);

    maxn[rk[i-]]=a[i],minn[rk[i-]]=a[i];

    fa[i]=i;size[i]=;

    }

    solve();

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

    printf("%lld %lld\n",ans[i][],ans[i][]?ans[i][]:);

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

BZOJ4199：[NOI2015]品酒大会——题解

最新文章

热门文章