专栏文章

题解：AT_abc225_f [ABC225F] String Cards

hhyxgg
AT_abc225_f题解参与者 2已保存评论 1

文章操作

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

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

前言

发现其他所有题解都是 DP，实际上这题只需要一个贪心。

思路

假作法

老师看错难度把这题放到模拟赛的签到题，以至于我随意看了一眼后把字符串排了序后直接顺次输出。
发现过不了样例：
CPP
3 2
baa
ba
b

尝试解决

问题

问题出在哪？
最小字符串为 SS，记含有其作为前缀的字符串 S+A=SAS+A=SA，AA 为字符串中除前缀 SS 外的部分。
发现可能出现 AA 比 SS 外所有字符串都小的情况，放到样例中就是 aa <\lt ba。

解决方案

如何解决？
首先，无论我们选什么，SS 的前缀必然不会变，于是答案可以先加上一个 SS。
采用类似反悔贪心的思想，看能不能将 AA 转化成新的字符串，再和其他的字符串作比较。
如果我们下一个字符串选了 AA，则意味着我们的第一个字符串从 SS 换成了 SASA，但是我们其实是在第二轮选了 AA，所以 AA 后还应选一个字符串接着，又因为 SS 是最小的字符串，所以 AA 后接着的必然是 SS。
于是对于 SASA，将其变为 ASAS 。
以上操作重复 kk 遍即可。

新的问题已经出现~

交上去发现并不行，发现 SASA 本身也可作为下一个字符串接在后面，不能直接将其变为 ASAS，而开一个新的字符串则会导致空间时间双双阵亡。

真正做法

其实解决这个问题也很简单，无论是 SSASSA 还是 SASSAS 都只涉及到 SS 和 SASA，长度也一样，选哪个都不会对其他的字符串及后面的选择产生影响，于是在这里直接贪心地选择 SASA 和 ASAS 中更小的那个作为新的字符串即可。

时间复杂度

  • 一找共 kk 个字符串，时间复杂度为 O(k)\mathcal{O}(k)。
  • 每轮一个排序找 SS，时间复杂度为 O(nlog⁡n)\mathcal{O}(n\log{n})。
  • 然后找 SASA，遍历找，逐字比较即可，更改也一个一个字符加即可，时间复杂度为 O(n∣S∣)\mathcal{O}(n\left|S\right|)。
于是总的时间复杂度为 O(knlog⁡n+kn∣s∣)\mathcal{O}(kn\log{n}+kn\left|s\right|)，题目中 nn，∣S∣\left|S\right|，kk 均小于 5050，轻松通过。

代码

代码很清晰，不写注释了，有问题评论区见。
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
struct yc
{
    string s;
    bool bj;
}yy[5005];

string ans;
ll n,k,dd=1;
bool cmp(yc a,yc b){
    return a.bj==b.bj?a.s<b.s:a.bj<b.bj;
}
void yb(){
    sort(yy+1,yy+1+n,cmp);
    ans+=yy[1].s;
    ll dn=yy[1].s.size();
    yy[1].bj=1;
    ll i;
    ll nn=n;
    for(i=2;i<=n;i++){
        if(yy[i].bj)break;
        bool p=0;
        for(ll j=0;j<dn;j++){
            if(yy[i].s[j]!=yy[1].s[j]){
                p=i;break;
            }
        }
        if(p){
            break;
        }
        string ns;
        ns.clear();
        ll id=yy[i].s.size();
        for(ll j=dn;j<id;j++){
            ns+=yy[i].s[j];
        }
        yy[i].s=(yy[i].s>(ns+yy[1].s))?ns+yy[1].s:yy[i].s;
    }
    n=nn;

}
int main(){
    scanf("%lld%lld",&n,&k);
    for(ll i=1;i<=n;i++){
        cin>>yy[i].s;
    }
    while(k){
        yb();
        k--;
        dd++;
    }
    cout<<ans<<endl;
    return 0;
}

评论

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

正在加载评论...