首页 > 其他 > 详细

【loj#2133 && luoguP2178】[NOI2015]品酒大会

时间:2019-12-06 22:58:01      阅读:122      评论:0      收藏:0      [点我收藏+]

??题目传送门:loj#2133 luoguP2178

??简要题意:给定一个字符串\(s\),每个后缀都有权值,对于每个长度\(len\),求出所有最长公共前缀\(\geq len\)的后缀对的总数和每个这样的后缀对,两后缀权值乘积的最大值。

??我们可以先把后缀数组求出来,把最长公共前缀长度转化为height数组的区间\(\min\),考虑固定\(len\),容易发现合法的后缀对的取值范围被height数组上小于\(len\)的位置划分成了若干区间,同时当\(len\)变小的时候,相邻区间会发生合并。

??于是倒序枚举\(len\),用并查集辅助合并合法区间,同时统计贡献就可以解决问题了。

my code

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 0x3f3f3f3f
#define maxn 300010
inline ll read()
{
    ll x=0; char c=getchar(),f=1;
    for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
    for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
    return x*f;
}
inline void write(ll x)
{
    static char buf[20];
    int len=0;
    if(x<0)putchar('-'),x=-x;
    for(;x;x/=10)buf[len++]=x%10+'0';
    if(!len)putchar('0');
    else while(len)putchar(buf[--len]);
}
inline void writesp(ll x){write(x); putchar(' ');}
inline void writeln(ll x){write(x); putchar('\n');}
int sa[maxn],rk[maxn],lcp[maxn];
int a[maxn],fa[maxn],l[maxn],r[maxn],mx1[maxn],mx2[maxn],mn1[maxn],mn2[maxn],id[maxn];
ll cnt[maxn],mx[maxn];
char s[maxn];
int n;
ll tot,cur;
void getsa(char* s,int n)
{
    int cnt=256;
    static int tsa[maxn],trk[maxn],sum[maxn];
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++)
        trk[i]=s[i]+1,++sum[trk[i]];
    for(int i=1;i<=cnt;i++)
        sum[i]+=sum[i-1];
    for(int i=n;i;i--)
        sa[sum[trk[i]]--]=i;
    cnt=1; rk[sa[1]]=1;
    for(int i=2;i<=n;i++){
        if(trk[sa[i]]!=trk[sa[i-1]])++cnt;
        rk[sa[i]]=cnt;
    }
    for(int len=1;cnt<n;len<<=1){
        int tot=0;
        for(int i=n-len+1;i<=n;i++)
            tsa[++tot]=i;
        for(int i=1;i<=n;i++)
            if(sa[i]>len)tsa[++tot]=sa[i]-len;
        memset(sum,0,sizeof(sum));
        memcpy(trk,rk,sizeof(rk));
        for(int i=1;i<=n;i++)
            ++sum[trk[tsa[i]]];
        for(int i=1;i<=cnt;i++)
            sum[i]+=sum[i-1];
        for(int i=n;i;i--)
            sa[sum[trk[tsa[i]]]--]=tsa[i];
        cnt=1; rk[sa[1]]=1;
        for(int i=2;i<=n;i++){
            if(trk[sa[i]]!=trk[sa[i-1]]||trk[sa[i]+len]!=trk[sa[i-1]+len])++cnt;
            rk[sa[i]]=cnt;
        }
    }
    for(int i=1;i<=n;i++)
        if(rk[i]>1){
            lcp[rk[i]]=std::max(lcp[rk[i-1]]-1,0);
            while(s[i+lcp[rk[i]]]==s[sa[rk[i]-1]+lcp[rk[i]]])++lcp[rk[i]];
        }
}
bool cmp(int x,int y){return lcp[x]>lcp[y];}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void modify(int now)
{
    int p1=find(now-1),p2=find(now);
    fa[p1]=p2;
    tot-=(ll)(r[p1]-l[p1]+1)*(r[p1]-l[p1])/2+(ll)(r[p2]-l[p2]+1)*(r[p2]-l[p2])/2;
    l[p2]=l[p1];
    if(mx1[p1]>mx1[p2]){
        int t1=mx1[p1],t2=std::max(mx1[p2],mx2[p1]);
        mx1[p2]=t1; mx2[p2]=t2;
    }
    else{
        int t1=mx1[p2],t2=std::max(mx1[p1],mx2[p2]);
        mx1[p2]=t1; mx2[p2]=t2;
    }
    if(mn1[p1]<mn1[p2]){
        int t1=mn1[p1],t2=std::min(mn1[p2],mn2[p1]);
        mn1[p2]=t1; mn2[p2]=t2;
    }
    else{
        int t1=mn1[p2],t2=std::min(mn1[p1],mn2[p2]);
        mn2[p2]=t1; mn2[p2]=t2;
    }
    tot+=(ll)(r[p2]-l[p2]+1)*(r[p2]-l[p2])/2;
    cur=std::max(cur,std::max((ll)mx1[p2]*mx2[p2],(ll)mn1[p2]*mn2[p2]));
}
int main()
{
    n=read();
    scanf("%s",s+1);
    getsa(s,n);
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=2;i<=n;i++)
        id[i]=i;
    std::sort(id+2,id+n+1,cmp);
    tot=0; cur=-1ll<<60;
    for(int i=1;i<=n;i++){
        fa[i]=i;
        l[i]=r[i]=i;
        mx1[i]=a[sa[i]]; mx2[i]=-inf;
        mn1[i]=a[sa[i]]; mn2[i]=inf;
    }
    int now=2;
    for(int i=n-1;i>=0;i--){
        while(now<=n&&lcp[id[now]]>=i)modify(id[now++]);
        cnt[i]=tot; mx[i]=cur;
    }
    for(int i=0;i<n;i++)
        if(cnt[i])writesp(cnt[i]),writeln(mx[i]);
        else puts("0 0");
    return 0;
}

【loj#2133 && luoguP2178】[NOI2015]品酒大会

原文:https://www.cnblogs.com/quzhizhou/p/11997922.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!