题解：P12454 [INOI Team Selection 2021] String

· · 题解

首先拜谢@Purslane，他把这道题推了出来，并写题解教会了我怎么写这道题。但是我并没有看懂他出的题解，只看懂了他的代码，应该是我太菜了吧。

注意到，字符串的总长度非常小，这启示我们实际上可以直接把所有字符串拼起来考虑。考虑选的过程，显然只有两种情况，一个是在当前串中选的后面再选一个，一个是从下一个串开始选。看起来是很可以贪心的样子。

但是贪心是有问题的，比如说有一个串为 \text{abcab}，那么我们并不能在不知道后面选哪些串的情况下确定是选第一个位置开始的一段前缀还是第四个位置开始的一段子串。

这时 Purslane 就提供了一个思路，实际上可以 dp。这里是一个还算经典的套路，由于字典序问题，每一位基本是独立的，所以不妨设 f_{i,j} 表示已经有了答案串的前 i 个位置，且所有字符串拼接在一起成的大字符串考虑到了第 j 位。但是这样的话，在 dp 数组中存的信息是不好确定的，因为实际上只知道这一位，而不能保证前面的位置是没有意义的。所有可以考虑多加一维 f_{i,j,0/1}，其中第三维表示当前 dp 表示的字符串是否达到了一个假设存在的答案字符串的上界（具体可以参考数位 dp 中控制数是否达到上界的位置），这样数组存的信息就可以是能否达到。那么由于字典序具有类似贪心的性质，所以只需要保证这一位尽可能的小即可。

考虑实现，假设当前要考虑答案串的第 i 位，那么这一位可以由上一位的信息转移。而由于我们加了一位控制，所以实际上答案就具有单调性了，从某一个字符开始，所有大于这个字符的都是可行的。所有就可以二分考虑这一位填什么字符。然后通过 dp 转移。这里的 dp 转移比较简单，可以预处理做到 O(n) 的。而同时不是所有的 (i,j) 都是可行的，得考虑后面至少、至多还能填多少个字符以保证不会假。这样每一次都可以二分确定每一位的答案，直接输出即可。

注意边界条件，可以认为没有字符的时候是顶到上界的，不然第一个字符的转移会出问题。

/*胡金梁*/
#include<bits/stdc++.h>
using namespace std;
#define __MY_TEST__ 0
inline int read()
{
    int f=1,re=0;
    char ch=getchar();
    while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar();}
    while( isdigit(ch)) re=(re<<3)+(re<<1)+(ch^'0'),ch=getchar();
    return re*f;
}
int n,k,tot,f[4005][4005][2],bg[4005],tmp[4005][2];
char ans;
string str[4005];
void solve(int num)
{
    memset(f[num],0,sizeof f[num]);
    memset(tmp,0,sizeof tmp);
    for(int i=1;i<=n;i++) for(int j=bg[i];j<bg[i+1];j++) tmp[i][0]|=f[num-1][j][0],tmp[i][1]|=f[num-1][j][1];
    if(f[num-1][0][1]) tmp[0][1]=1;
    for(int i=1;i<=n;i++) for(int j=bg[i];j<bg[i+1];j++)
    {
        f[num][j][0]|=tmp[i-1][0];
        if(str[i][j-bg[i]]<=ans)
        {
            f[num][j][str[i][j-bg[i]]==ans]|=tmp[i-1][1];
        }
        if(j!=bg[i])
        {
            f[num][j][0]|=f[num-1][j-1][0];
            if(str[i][j-bg[i]]<=ans)
            {
                f[num][j][str[i][j-bg[i]]==ans]|=f[num-1][j-1][1];
            }
        }
    }
}
signed main()
{
#if __MY_TEST__
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    n=read(),k=read();
    for(int i=1;i<=n;i++) cin>>str[i],tot+=str[i].size();
    bg[1]=f[0][0][1]=1;
    for(int i=1;i<=n;i++) bg[i+1]=bg[i]+str[i].size();
    for(int num=1;num<=k;num++)
    {
        int l='a',r='z',Ans;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            ans=mid;
            solve(num);
            bool fg=0;
            for(int i=max(1,n+num-k);i<=n;i++) for(int j=bg[i];j<=min(bg[i+1]-1,num+tot-k);j++) 
            {
                fg|=(f[num][j][0]||f[num][j][1]);
            }
            if(fg) Ans=mid,r=mid-1;
            else l=mid+1;
        }
        ans=Ans;
        solve(num);
        cout<<ans;
    }
}