题解：CF128B String

Ag2WO4 · 2024-08-16 00:57:22 · 题解

不错的贪心。

由于是取字典序第 n 大的，先确定第一个字母（如果以某个字母开头的子串少于 n 个肯定不是，第一个大于等于的肯定是），再确定第二个字母，以此类推，直到确定 n 落在某个子串的字典序区间。

Python 代码

s=list(map(lambda i:ord(i)-97,input()));l=len(s);m=int(input());t='';u=range(l)#t 记录子串的已确定部分
while m:
    a=[0]*26;b=[[]for i in range(26)];c=[0]*26;d=0;e=1
    for k in u:
        a[s[k]]+=l-k;c[s[k]]+=1#a 为以剩余子串中为已确定部分 + 该字母 + 任意后缀的所有子串数，c 为剩余子串中为已确定部分 + 该字母的子串数
        if~k+l:b[s[k]].append(k+1)#记录下一层的搜索位置
    for k in range(26):
        if c[k]+d>=m:t+=chr(97+k);m=e=0;break#如果 n 落在子串字典序区间，结束
        if a[k]+d>=m:t+=chr(97+k);m-=d+c[k];u=b[k];e=0;break#以后的子串都不是，开始下一层筛选
        d+=a[k]
    if e:print('No such line.');exit()#如果都没落到就是 n 太大不存在
print(t)

C/C++ 代码

#include<stdio.h>
char a[100001],t[100001],x;
int b[26][100001],c[27],e[100001],f[27],l,i,m,o,q,n;
long long d[27];
int main()
{
    while(x-10)
    {
        x=getchar();
        a[l++]=x-97;
    }
    --l;
    scanf("%d",&m);
    for(i=0;i<l;i++)e[i]=i;
    q=l;
    while(m)
    {
        for(o=0;o<26;o++)
        {
            i=0;
            while(b[o][i])b[o][i++]=0;
        }
        o=0;
        x=1;
        for(i=0;i<26;i++)
        {
            c[i]=0;
            d[i]=0;
            f[i]=0;
        }
        while(q--)
        {
            d[a[e[q]]]+=l-e[q];
            ++c[a[e[q]]];
            if(~e[q]+l)b[a[e[q]]][f[a[e[q]]]++]=e[q]+1;
        }
        for(i=0;i<26;++i)
        {
            if(c[i]+o>=m)
            {
                t[n++]=i+97;
                m=x=0;
                break;
            }
            if(d[i]+o>=m)
            {
                t[n++]=i+97;
                m-=o+c[i];
                q=x=0;
                while(e[q])e[q++]=0;
                q=0;
                while(b[i][q])
                {
                    e[q]=b[i][q];
                    ++q;
                }
                break;
            }
            o+=d[i];
        }
        if(x)
        {
            puts("No such line.");
            return 0;
        }
    }
    q=0;
    while(t[q])putchar(t[q++]);
}