洛谷 P2178 [NOI2015]品酒大会 解题报告

时间：2023-03-09 04:34:41
洛谷 P2178 [NOI2015]品酒大会 解题报告

P2178 [NOI2015]品酒大会

题目描述

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

在大会的晚餐上，调酒师 Rainbow 调制了 \(n\) 杯鸡尾酒。这 \(n\) 杯鸡尾酒排成一行，其中第 \(n\) 杯酒 \((1 ≤ i ≤ n)\) 被贴上了一个标签\(s_i\)，每个标签都是 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\)) 的 美味度为 \(a_i\) 。现在 Rainbow 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 \(p\) 杯酒与第 \(q\) 杯酒调兑在一起，将得到一杯美味度为 \(a_p*a_q\) 的 酒。现在请各位品酒师分别对于 \(r = 0,1,2, ⋯ , n − 1\) ，统计出有多少种方法可以 选出 \(2\) 杯“ \(r\) 相似”的酒，并回答选择 \(2\) 杯“ \(r\) 相似”的酒调兑可以得到的美味度的最大值。

输入输出格式

输入格式：

第 \(1\) 行包含 \(1\) 个正整数 \(n\) ，表示鸡尾酒的杯数。

第 \(2\) 行包含一个长度为 \(n\) 的字符串 \(S\)，其中第 \(i\) 个字符表示第 \(i\) 杯酒的标签。

第 \(3\) 行包含 \(n\) 个整数，相邻整数之间用单个空格隔开，其中第 \(i\) 个整数表示第 \(i\) 杯酒的美味度 \(a_i\) 。

输出格式：

包括 \(n\) 行。第 \(i\) 行输出 \(2\) 个整数，中间用单个空格隔开。第 \(1\) 个整 数表示选出两杯“ \((i − 1)\) 相似”的酒的方案数，第 \(2\) 个整数表示选出两杯 “ \((i − 1)\) 相似”的酒调兑可以得到的最大美味度。若不存在两杯“ \((i − 1)\) 相似” 的酒，这两个数均为 \(0\) 。

说明

没什么思维，但是窝写了巨久无比，代码能力还是太差了...

思路：

SA求出height，然后单调栈求出每个height可以向左or向右延伸的长度，然后对于每个height对应的左右区间，随便更新一下就好了。

Code:

#include <cstdio>

#include <cstring>

#include <algorithm>

#define ll long long

using std::min;

using std::max;

const int N=3e5+10;

int tax[N],sec[N],Rank[N],sa[N],hei[N],m;

ll ans[N],sum[N];

int mx[N],mi[N],n,tot,sta[N],p[N],L[N],R[N];

char s[N];

void Rsort()

{

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

    for(int i=1;i<=n;i++) ++tax[Rank[i]];

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

    for(int i=n;i;i--) sa[tax[Rank[sec[i]]]--]=sec[i];

}

bool cmp(int x,int y,int l){return sec[x]==sec[y]&&sec[x+l]==sec[y+l];}

void SuffixSort()

{

    for(int i=1;i<=n;i++) Rank[i]=s[i]-'a'+1,sec[i]=i;

    m=26;Rsort();

    for(int p=0,w=1;p<n;w<<=1,m=p)

    {

        p=0;for(int i=n-w+1;i<=n;i++) sec[++p]=i;

        for(int i=1;i<=n;i++) if(sa[i]>w) sec[++p]=sa[i]-w;

        Rsort(),std::swap(Rank,sec);

        Rank[sa[1]]=p=1;

        for(int i=2;i<=n;i++) Rank[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;

    }

    for(int k=0,j,i=1;i<=n;hei[Rank[i]]=k,i++)

        for(k=k?k-1:k,j=sa[Rank[i]-1];s[i+k]==s[j+k];k++);

}

struct node

{

    int l,r;

    node(){}

    node(int l,int r){this->l=l,this->r=r;}

    ll friend operator +(node a,node b)

    {

        return max(max(1ll*a.l*b.l,1ll*a.r*b.r),max(1ll*a.l*b.r,1ll*a.r*b.l));

    }

}beel[N],beer[N];

int main()

{

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

    SuffixSort();

    for(int i=1;i<=n;i++) scanf("%d",p+i);

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

    {

        int nmi=p[sa[i-1]],nmx=nmi;

        while(tot&&hei[sta[tot]]>=hei[i])

        {

            nmi=min(nmi,mi[tot]);

            nmx=max(nmx,mx[tot]);

            --tot;

        }

        L[i]=tot?sta[tot]:1;

        sta[++tot]=i,mi[tot]=nmi,mx[tot]=nmx;

        beel[i]=node(mi[tot],mx[tot]);

    }

    tot=0;

    for(int i=n;i>1;i--)

    {

        int nmi=p[sa[i]],nmx=nmi;

        while(tot&&hei[sta[tot]]>hei[i])

        {

            nmi=min(nmi,mi[tot]);

            nmx=max(nmx,mx[tot]);

            --tot;

        }

        R[i]=tot?sta[tot]:n+1;

        sta[++tot]=i,mi[tot]=nmi,mx[tot]=nmx;

        beer[i]=node(mi[tot],mx[tot]);

    }

    memset(ans,-0x3f,sizeof(ans));

    for(int i=2;i<=n;i++) sum[hei[i]]+=1ll*(i-L[i])*(R[i]-i),ans[hei[i]]=max(ans[hei[i]],beel[i]+beer[i]);

    for(int i=n-2;~i;i--) sum[i]+=sum[i+1],ans[i]=max(ans[i],ans[i+1]);

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

    return 0;

}

2019.1.11