题解：AT_abc225_f [ABC225F] String Cards

· · 题解

前言

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

思路

假作法

老师看错难度把这题放到模拟赛的签到题，以至于我随意看了一眼后把字符串排了序后直接顺次输出。

发现过不了样例：

3 2
baa
ba
b

尝试解决

问题

问题出在哪？

最小字符串为 S，记含有其作为前缀的字符串 S+A=SA，A 为字符串中除前缀 S 外的部分。

发现可能出现 A 比 S 外所有字符串都小的情况，放到样例中就是 aa \lt ba。

解决方案

如何解决？

首先，无论我们选什么，S 的前缀必然不会变，于是答案可以先加上一个 S。

采用类似反悔贪心的思想，看能不能将 A 转化成新的字符串，再和其他的字符串作比较。

如果我们下一个字符串选了 A，则意味着我们的第一个字符串从 S 换成了 SA，但是我们其实是在第二轮选了 A，所以 A 后还应选一个字符串接着，又因为 S 是最小的字符串，所以 A 后接着的必然是 S。

于是对于 SA，将其变为 AS 。

以上操作重复 k 遍即可。

新的问题已经出现~

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

真正做法

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

时间复杂度

于是总的时间复杂度为 \mathcal{O}(kn\log{n}+kn\left|s\right|)，题目中 n，\left|S\right|，k 均小于 50，轻松通过。

代码

代码很清晰，不写注释了，有问题评论区见。

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