题解：P17872 [FJCPC 2026] 限号出行

· · 题解

题目传送门

思路

先把字符转为数字。

接着可以用 dp 判断可行性。

设 f_{i,j} 表示只选后缀 [i,n] 的字母并且车牌首字母为 j 的满足条件的最长车牌长度。

那么我们只需检查满足 1 \le j \le 26 的 j 中，f_{1,j} 的最大值是否至少为 k 即可。

转移的话，首先显然 f_{n,t_{n-1}}=1，然后 i 从 n-1 到 1，每次有三种情况，第一种是以当前字符为新的字符串，也就是 f_{i,t_{i-1}}=1，第二种是当前字符不选，也就是所有的 1 \le j \le 26 的 j 执行 f_{i,j}=\max(f_{i,j},f_{i+1,j})，第三种是选当前字符，也就是对所有的 满足 1 \le k \le 26 且不违反限制的 k 执行 f_{i,t_{i-1}}=\max(f_{i,t_{i-1}},f_{i+1,k}+1)。

然后定义两个变量 now 和 cnt，分别表示当前车牌最后一个字符在原串的位置及目前选了多少位。当 cnt < k 时用一个 j 遍历 1 到 26，看 k-cnt \le f_{now+1,j} 和 j 与 t_{now} 是否违反限制，如果可以这一位选 j，将 now 置为 [now+1,n] 第一个为 j 的位置，这个可以预处理，再将 cnt 加 1，然后退出 j 这个循环。

限制的话用个桶记录就行了，注意清空。

字典序的话由于 j 顺序枚举，所以一定能保证。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,inf=1e18;
int T,n,m,k,f[N][27];
int mp[127][127],fl,cnt;
int now,pos[N][27];
string s,a;
int t[N];
char x,y;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>k>>a;
        for(int i=0;i<n;i++)  t[i]=a[i]-'a'+1;//转数字
        for(int i=1;i<=26;i++)
        {
            for(int j=1;j<=26;j++)  mp[i][j]=0;//清空桶
        }
        for(int i=0;i<=n;i++)
        {
            for(int j=1;j<=26;j++)  
            {
                pos[i][j]=inf;//清空预处理数组
                f[i][j]=0;//清空dp结果
            }
        }
        pos[n-1][t[n-1]]=n;
        for(int i=n-2;i>=0;i--)
        {
            for(int j=1;j<=26;j++)  pos[i][j]=pos[i+1][j];
            pos[i][t[i]]=i+1;
        }//预处理
        for(int i=1;i<=m;i++)
        {
            cin>>x>>y;
            mp[x-'a'+1][y-'a'+1]=1;//标记
        }
        f[n][t[n-1]]=1;//初始化
        for(int i=n-1;i>=1;i--)
        {
            f[i][t[i-1]]=1;
            for(int j=1;j<=26;j++)   f[i][j]=max(f[i+1][j],f[i][j]);
            for(int k1=1;k1<=26;k1++)  if(!mp[t[i-1]][k1])  f[i][t[i-1]]=max(f[i][t[i-1]],f[i+1][k1]+1);
        }//转移
        fl=0;
        for(int i=1;i<=26;i++)  
        {
            if(f[1][i]>=k)  fl=1;
        }
        if(!fl)
        {
            cout<<"-1\n";
            continue;
        }//判可行性
        now=0;
        s="A";//一开始塞一个特殊字符
        cnt=0;
        while(cnt<k)
        {
            for(int j=1;j<=26;j++)
            {
                if(f[now+1][j]>=k-cnt&&!mp[s[cnt]-'a'+1][j])  
                {
                    s+=char(j-1+'a');
                    cnt++;
                    now=pos[now][j];
                    break;
                }
            }
        }
        s.erase(0,1);//最后再删掉特殊字符
        cout<<s<<'\n';//模拟选的过程
    }
    return 0;
}