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

huangzixi071018 · 2026-11-12 21:48:18 · 题解

做法：

将题目变成从 n 个字符中选择 k 个。本题要求字典序最小，考虑贪心的一位一位取。考虑当前位是否能取某个字符，则需要保证选完这个字符之后是可以选够 k 个字符。这个东西是可以用一个动态规划预处理的，处理出每一位最多能够选多少个字符。贪心的过程中需要维护每种字符第一次出现的位置是哪个，这也很好做，就可以顺利通过了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
bool v[26][26];
int p[26],c[N];
char a[N];
vector<int>e[26];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,m,k;
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++){
            cin>>a[i];      
        }
        for(int i=0;i<26;i++){
            for(int j=0;j<26;j++){
                v[i][j]=0;
            }
            p[i]=0;
            e[i].clear();
        }
        for(int i=1;i<=m;i++){
            char x,y;
            cin>>x>>y;
            v[x-'a'][y-'a']=1;
        }
        for(int i=n;i>=1;i--){
            c[i]=1;
            int h=a[i]-'a';
            for(int j=0;j<26;j++){
                if(v[h][j])continue;
                if(p[j]){
                    c[i]=max(c[i],c[p[j]]+1);
                }
            }
            p[h]=i;
            e[h].push_back(i);
        }
        string ans;
        bool flag=1;
        int lst=-1;
        while(1){
            int g=-1;
            for(int i=0;i<26;i++){
                if(lst!=-1&&v[lst][i])continue;
                if(c[p[i]]>=k){
                    g=p[i];
                    lst=i;
                    ans.push_back('a'+i);
                    break;
                }
            }
            if(g==-1){
                flag=0;
                break;
            }
            for(int i=0;i<26;i++){
                while(!e[i].empty()&&e[i].back()<=g){
                    e[i].pop_back();
                }
                if(e[i].empty()){
                    p[i]=0;
                }else{
                    p[i]=e[i].back();
                }
            }
            k--;
            if(k==0)break;
        }   
        if(!flag){
            cout<<"-1\n";
        }else{
            cout<<ans<<"\n";
        }
    }
    return 0;
}