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

kevinZ99 · 2026-11-13 09:49:27 · 题解

:::success[和队友的聊天记录] 特别难绷，就放上来了。

看到字典序最小肯定尽量贪心一个字母后面尽量小的可以选的位置，但是如果你每一次选一个你可选的最小的作为下一个，可能选不到 k 就燃尽了。

所以我们考虑倒着预处理一个 f 表示从 t_{i} 开头，的能选出来的最长合法子序列。

这个可以倒着 dp 出来，可以通过预处理每一个字母的后缀 mx 做到 O(n) 的。

然后每一次贪心的时候判断 f_{i} \ge rest 就行了，其中 rest 是还需要选择的字母数量。

:::success[code]

namespace my{
    const int N=2e5+5,inf=1000000000;template<typename T>pref T Min(T x,T y){return x<y?x:y;}template<typename T>pref T Max(T x,T y){return x>y?x:y;}template<typename T>pref T Abs(T x){return x<0?-x:x;}
    int n,m,k,f[N],mx[26],nxt[N][26];
    bool ban[26][26];
    string s;
    pref void SOLVE(){
        cin>>n>>m>>k>>s;
        s=" "+s;
        __builtin_memset(ban,false,sizeof(ban));
        __builtin_memset(mx,0,sizeof(mx));
        __builtin_memset(nxt[n+1],0,sizeof(nxt[n+1]));
        up(i,1,m){
            char x,y;cin>>x>>y;
            ban[x-'a'][y-'a']=true;
        }
        up(i,1,n)f[i]=1;
        int best=0;
        dn(i,n,1){
            int c=s[i]-'a';
            up(j,0,25){
                nxt[i][j]=nxt[i+1][j];
                if(!ban[c][j])f[i]=Max(f[i],mx[j]+1);
            }
            nxt[i][c]=i,mx[c]=Max(mx[c],f[i]);
            best=Max(best,f[i]);
        }
        if(best<k)return cout<<"-1\n",void();
        string ans="";
        ans.reserve(k);
        int p=0,lst=-1;
        dn(r,k,1){
            up(c,0,25){
                if(lst!=-1&&ban[lst][c])continue;
                int j=nxt[p+1][c];
                if(j&&f[j]>=r){
                    ans+='a'+c;
                    p=j,lst=c;
                    break;
                }
            }
        }cout<<ans<<'\n';
    }
}

:::