Problem

https://acm.hdu.edu.cn/showproblem.php?pid=6988
每个字符有代价，字符串代价为字符代价之和。求本质不同的第 k 大代价子串的代价。

Solution

二分这个代价，找有多少个子串小于这个代价。
于是用 SA 来维护一个 height，并同时二分这个后缀的小于这个代价的最长前缀，对 height 取 min 减去重复子串就行了。

所以什么是 height 呢，我就去复习了一下。

起到一个复习的作用。板子蒯的我自己的。

Code

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N=1e5+10;
struct SA {
    int x[N], y[N], sa[N], c[N]; // 第一关键字（rank） 第二关键字排序结果 后缀（第一关键字）排序结果 桶
    char s[N];
    int n, m; // length

    void getsa() {
        for(int i=0; i<=n; i++)
            x[i]=y[i]=sa[i]=0;
        for(int i=0; i<=m; i++)
            c[i]=0;
        for(int i=1;i<=n;i++) c[x[i]=s[i]]++; // 初始化第一关键字
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=1;i<=n;i++) sa[c[x[i]]--]=i; // 初始化第一次sa
        int num;
        for(int k=1;k<=n;k<<=1) {
            num=0;
            /* 求第二关键字rank（非常规方法） */
            for(int i=n-k+1;i<=n;i++) y[++num]=i; // [n-k+1, n]没有第二关键字，因此对第二关键词排名第一
            for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
            // 直接从小到大作为第二关键字枚举sa得到从小到大的第二关键字位置
            // 如果位置合法，插入第一关键字
            /* 求第一关键字rank(新sa) */
            fill(c+1, c+1+m, 0);
            for(int i=1;i<=n;i++) c[x[i]]++;
            for(int i=2;i<=m;i++) c[i]+=c[i-1];
            for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i], y[i]=0;
            swap(x, y); // 把x数组拷到y中去
            x[sa[1]]=1; // 更新第一关键字
            num=1;
            for(int i=2;i<=n;i++)
                x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]?num:++num);
            if(num==n) break;
            m=num; // 更新字符集大小
        }
        
    }

    int rank[N]; // 排名
    int height[N]; // height
    void gheight() {
        for(int i=1;i<=n;i++) rank[sa[i]]=i;
        int k=0;
        for(int i=1;i<=n;i++) {
            if(rank[i]==1) continue;
            if(k) k--;
            int j=sa[rank[i]-1];
            while(j+k<=n && i+k<=n && s[j+k]==s[i+k]) k++;
            height[rank[i]]=k;
        }
    }
    void build(char *os, int on) {
        memcpy(s+1, os, on);
        n=on, m='z';
        getsa();
        gheight();
    }
} sa;

int w[N];
ll n, k;
bool check(ll lim) {
    int nsuf;
    int l, r, mid, ans;
    ll cnt=0;
    for(int i=1; i<=n; i++) {
        nsuf=sa.sa[i];
        l=nsuf, r=n, ans=l-1;
        while(l<=r) {
            mid=(l+r)>>1;
            if(w[mid]-w[nsuf-1]<=lim) ans=mid, l=mid+1;
            else r=mid-1;
        }
        cnt+=ans-nsuf+1-min(ans-nsuf+1, sa.height[i]);
    }
    return cnt>=k;
}

void solve() {
    scanf("%lld%lld", &n, &k);
    char str[N];
    scanf("%s", str);
    sa.build(str, n);
    int val[500]={0};
    for(int i='a'; i<='z'; i++)
        scanf("%d", val+i);
    for(int i=1; i<=n; i++)
        w[i]=val[str[i-1]]+w[i-1];
    ll l=0, r=1e7+10, mid, ans=-1;
    while(l<=r) {
        mid=(l+r)>>1;
        if(check(mid)) ans=mid, r=mid-1;
        else l=mid+1;
    }
    printf("%lld\n", ans);
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        solve();
    }

    return 0;
}

本文链接：https://pst.iorinn.moe/archives/hdu-6988.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆