题解：AT_abc416_c [ABC416C] Concat (X-th)

Frank2010 · 2025-07-27 08:12:10 · 题解

AT_abc416_c [ABC416C] Concat (X-th) - 洛谷

题意简述

给定 n 个字符串，任选 k 个拼接（可重复选择同一个字符串），求拼接后字典序第 x 大的字符串。

解题思路

暴搜

注意到 N\le10 和 K\le5，暴搜的复杂度也就是 O(N^{k})，也就是 10^5（显然带个 log 都不带怕的），回溯也可以直接用 t.erase(t.size()-s[j].size())，毕竟说过字符串长度不超过 10。

排序

求字典序第 x 小，很容易想到直接排序（大不了就是带个 log 嘛），那么复杂度就是 O(N^{k}\log{N^{k}})，显然不会超时。

AC 代码

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=15;
int n,k,x;
string s[N],t;
vector<string>v;
void dfs(int i){
    for(int j=1;j<=n;j++){
        t+=s[j];
        if(i==k)v.emplace_back(t);
        else dfs(i+1);
        t.erase(t.size()-s[j].size());
    }
}
//暴搜
int main(){
    scanf("%d%d%d",&n,&k,&x);
    for(int i=1;i<=n;i++)cin>>s[i];
    dfs(1);
    sort(v.begin(),v.end());
    //sort 自动用字典序排序字符串
    puts(v[x-1].c_str());
    //下标从 0 开始，故需要减 1
    return 0;
}