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

39xiemy · 2026-11-13 16:10:24 · 题解

题意

给定一个长度为 n 的字符串 t，你需要找到 t 的一个长度为 k 的字典序最小的子序列，使得其满足 m 条限制关系，每条限制形如字符 x_i 后面不能紧跟字符 y_i。

思路

标签：贪心，动态规划。

首先因为要求提取的子序列的字典序最小，容易想到从前往后按字符贪心。假设上一个字符的位置为 f，遍历所有可能的字符种类 j，那么我们就需要找到 f 以后的第一次出现字符 j 的位置。通过预处理即可实现。

找到一个新的字符 x 后，我们需要快速判断选择 x 后，对于剩下的字符，是否还能找到一个合法解。因为是要求合法解，那么我们希望我们所选择的字符数越多越好，这需要使用 DP。

记 dp_i 表示对于以 i 开头的字符串 t 的后缀，强制选择了第 i 个字符后，最多能选出多长的满足条件的子序列。由于限制只和开头的字符相关，那么同样枚举第 i 个位置以后第一次出现的字符种类 j，如果位置 i 的字符和字符 j 不产生冲突，那么就可以进行转移。取所有可能转移的最大值即可，注意 dp_i 初值为 1。详细的 DP 转移式请见代码。

那么把每个位置上的 DP 值预处理出来，就可以快速判断一个选择是否合法，结合上述贪心即可。时间复杂度 O(n\lvert\Sigma\rvert)，其中 \lvert\Sigma\rvert 指字符集大小，在本题中为 26。

代码

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+3,K=26;char c1,c2;
int T,n,m,k,to[N][K],dp[N],x,f;
string s,ans;bool bj[K][K],ok;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;while(T--){
        cin>>n>>m>>k>>s,s=' '+s,dp[n+1]=0;
        for(int i=1;i<=m;++i) cin>>c1>>c2,bj[c1-'a'][c2-'a']=1;
        for(int j=0;j<K;++j) to[n+1][j]=n+1;
        for(int i=n;i>=1;--i){
            dp[i]=1,x=s[i]-'a';
            for(int j=0;j<K;++j){
                to[i][j]=to[i+1][j];
                if(!bj[x][j]) dp[i]=max(dp[i],dp[to[i][j]]+1);
            }to[i][x]=i;
        }x=1;for(int i=1;i<=k;++i){
            ok=0;for(int j=0;j<K;++j){
                if(x!=1&&bj[f][j]) continue;
                if(dp[to[x][j]]>=k-i+1){
                    ans+='a'+j,f=j,ok=1;
                    x=to[x][j]+1;break;
                }
            }if(!ok) break;
        }if(!ok)cout<<"-1\n";else cout<<ans<<'\n';
        memset(bj,0,sizeof(bj)),ans="";
    }return 0;
}