• 周六. 8月 20th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

2021杭电多校 4D / HDU 6988

admin

11月 28, 2021

HDU 6988 / 2021杭电多校4D

题意

给定一长度为(n)的字符串(S)

要求找出在(S)的所有互不相同的子串中,能量值排名第(k)小的子串的能量值;若不存在输出(-1)

定义一个子串的能量值为其所有字符的能量值之和,所有(26)个小写字母的能量值已给出

思路

(后缀系列知识点相关的一道好题,可惜赛时不敢往(O(nlognlogn))​的方向想)

(使用后缀数组板子时注意下标)

考虑采用后缀数组,已知一个字符串的所有后缀的所有前缀即字符串的子串集合

首先判断排名为(k)的子串是否存在,即字符串(S)是否具有(k)个以上的不同子串

利用后缀数组的(height)数组可以得出相邻排名的两后缀的最长公共前缀,则所有后缀长度总和减去(height)数组总和即不同子串数量

然后考虑二分答案(mid)(即排名为(k)的子串的能量值),尝试check寻找能量值小于等于(mid)的子串数量

  • 如果找出的子串数量(ge k),说明待寻找的答案(le mid)
  • 否则,说明答案(gt mid)

然后考虑(check),按后缀排名顺序遍历原串的所有后缀,方便去重

排名为(i)的后缀在原串中的左边界为(sa[i]),右边界即原串末尾

对于某个后缀的前缀而言,前缀的长度增长,总能量值也一定增加,所以仍然存在单调性

对后缀的前缀长度进行二分,找出最长的总能量值不超过(mid)的前缀(总能量值可以通过预处理原串的前缀和来直接求出),假设其范围为([sa[i],r])

则这一步我们能够得到,总能量值(le mid)的子串数量即(r-sa[i]+1)(即长度)

最后考虑去重,减去前一步已经算入答案的子串;再根据(height)数组获得排名为(i)与排名为(i-1)的后缀的最长公共前缀,故最终应当加入结果的答案为(r-sa[i]+1-height[i]),注意可能最长公共前缀较长,值需与(0)​取大

代码

//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
void debug(){cerr<<'
';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);}
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
ll inv(ll a){return qpow(a,mod-2);}
ll inv(ll a,ll p){return qpow(a,p-2,p);}

const int N=100050;
int xx[N],yy[N],cnt[N];
int sa[N],rk[N],height[N];
char str[N];
void getSA_DA(int n,int M){
    int i,j,p,*x=xx,*y=yy;
    for(i=0;i<M;i++)cnt[i]=0;
    for(i=0;i<n;i++)cnt[x[i]=str[i]]++;
    for(i=1;i<M;i++)cnt[i]+=cnt[i-1];
    for(i=n-1;i>=0;i--)sa[--cnt[x[i]]]=i;
    for(j=1,p=1;p<n;j<<=1,M=p){
        for(p=0,i=n-j;i<n;i++)y[p++]=i;
        for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
        for(i=0;i<M;i++)cnt[i]=0;
        for(i=0;i<n;i++)cnt[x[y[i]]]++;
        for(i=1;i<M;i++)cnt[i]+=cnt[i-1];
        for(i=n-1;i>=0;i--)sa[--cnt[x[y[i]]]]=y[i];
        for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++)
            x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j])?p-1:p++;
    }
}
void getHeight(int n){
    int i,j,k=0;
    for(i=1;i<=n;i++)rk[sa[i]]=i;
    for(i=0;i<n;height[rk[i++]]=k)
        for(k?k--:0,j=sa[rk[i]-1];str[i+k]==str[j+k];k++);
    for(i=n;i;i--)rk[i]=rk[i-1],sa[i]++;
}

int n,val[30];
ll k,sum[N];

bool ck(ll mid)
{
    ll kk=0;
    rep(i,1,n)
    {
        // 排名为i的字符串在原串中的左边界为sa[i]
        int l=sa[i],r=n;
        while(l<=r)
        {
            int m=l+r>>1;
            // 以sa[i]至m的能量总和进行判断
            if(sum[m]-sum[sa[i]-1]>mid)
                r=m-1;
            else
                l=m+1;
        }
        // 符合条件的个数为r-sa[i]+1,减去重复计数height[i]
        kk+=max(0,r-sa[i]+1-height[i]);
    }
    // 如果<=mid的个数>=k,则说明答案<=mid
    return kk>=k;
}

void solve()
{
    cin>>n>>k>>str;
    repp(i,0,26)
        cin>>val[i];
    
    // 构建后缀数组
    getSA_DA(n+1,128);
    getHeight(n);
    
    // 获取不同子串的数量
    ll tot=n-sa[1]+1;
    rep(i,2,n)
        tot+=n-sa[i]+1-height[i];
    if(k>tot)
    {
        cout<<"-1
";
        return;
    }
    
    // 预处理前缀和及二分范围
    ll l=100;
    rep(i,1,n)
    {
        l=min(l,(ll)val[str[i-1]-'a']);
        sum[i]=sum[i-1]+val[str[i-1]-'a'];
    }
    ll r=sum[n];
    
    // 二分答案
    while(l<=r)
    {
        ll m=l+r>>1;
        if(ck(m))
            r=m-1;
        else
            l=m+1;
    }
    cout<<l<<'
';
}
int main()
{
    closeSync;
    multiCase
    {
        solve();
    }
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。