2021杭电多校第四场题解

A

签到

每一项判断系数是否为0即可，因为均为发散函数，代码略

B

签到

这题注意到n<=2000就没了

每次枚举起点，扫一下，记录每种颜色出现的次数，代码略

D

SA板子题。

一个子字符串消耗必定比原字符串消耗要少，故可处理前缀，通过所有后缀自然也可得所有前缀。处理并遍历后缀数组，对于每个后缀，其越长的前缀能耗越大，于是可以二分找到能耗小于等于要check的值的前缀的个数，再减去重复部分即可，而height数组对应的值为重复统计的部分。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+7;
int n,val[27],s[N],a[N],b[N],c[N],sa[N],rk[N],height[N];
ll k;
char str[N];
void SA()
{
    int *x=a,*y=b,m=127;
    for(int i=0;i<=m;++i)c[i]=0;
    for(int i=1;i<=n;++i)++c[x[i]=str[i]];
    for(int i=1;i<=m;++i)c[i]+=c[i-1];
    for(int i=n;i;--i)sa[c[x[i]]--]=i;
    for(int k=1;k<=n;k<<=1)
    {
        int p=0;
        for(int i=n-k+1;i<=n;++i)y[++p]=i;
        for(int i=1;i<=n;++i)if(sa[i]>k)y[++p]=sa[i]-k;
        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;--i)sa[c[x[y[i]]]--]=y[i];
        swap(x,y),x[sa[1]]=p=1;
        for(int i=2;i<=n;++i)
        if(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k])x[sa[i]]=p;
        else x[sa[i]]=++p;
        m=p;
        if(m>=n)break;
    }
    for(int i=1;i<=n;++i)rk[sa[i]]=i;
    for(int i=1,j,k=0;i<=n;++i)
    if(rk[i]!=1)
    {
        if(k)--k;
        j=sa[rk[i]-1];
        while(str[i+k]==str[j+k]&&i+k<=n&&j+k<=n)++k;
        height[rk[i]]=k;
    }
}
ll check(int x)
{
    int t=1,tmp;ll ret=0;
    for(int i=1;i<=n;++i)
    {
        while(t<=n&&s[t]-s[i-1]<=x)++t;
        ret+=t-i-height[rk[i]]>0?t-i-height[rk[i]]:0;
    }
    return ret;
}
int main()
{
    int T;scanf("%d", &T);
    while(T--)
    {
        scanf("%d%lld",&n,&k);
        scanf("%s",str+1);
        for(int i=0;i<26;++i)scanf("%d",&val[i]);
        for(int i=1;i<=n;++i)s[i]=s[i-1]+val[str[i]-'a'];
        SA();
        int l=0,r=1e8,mid,ans=1e8;
        while(l<=r)
        {
            mid=l+r>>1;
            if(check(mid)<k)l=mid+1;else ans=mid,r=mid-1;
        }
        printf("%d
",ans==1e8?-1:ans);
    }
}

持续更新中……