专栏文章

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

FFrank2010
AT_abc416_c题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miopkdok
此快照首次捕获于
2025/12/02 23:03
3 个月前
此快照最后确认于
2025/12/02 23:03
3 个月前
查看原文

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

题意简述

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

解题思路

暴搜

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

排序

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

AC 代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...