题解：AT_abc416_g [ABC416G] Concat (1st)

· · 题解

提示：这篇题解中部分内容借鉴了官方题解的思路，但是相较而言省略了部分推导过程，直接进入做法部分。

首先，我们有一些前置的约定/定义：

我们考虑套路地定义一种全序关系：字符串 X,Y(X\neq Y) 满足 X\prec Y 当且仅当 X+Y<Y+X 或 (X+Y=Y+X) \land X< Y。容易发现，它能构成一种全序关系，且具有传递性。因此，我们可以以 O(n|S_i|\log n) 的复杂度将所有字符串按照它来排序。设排序后最小的字符串为 T。

举例而言，当 X 为 a，Y 为 ab 的时候，X<Y 是成立的，但 X\prec Y 不成立。

下面所说的字符串之间的比较，都以这种全序关系为准。

现在，我们给出本题的一个重要结论：答案串一定是 T^{+\infty} 的一个前缀。

官方题解中对此给出了严谨的证明以及循序渐进的推导过程，但是我个人倾向于在赛时通过观察样例发现这一点（这个性质其实非常自然）。当然也可以这么理解：我们刚刚定义的全序关系使得答案串无法找到一个位置满足它与 T^{+\infty} 对应位置的字符不同，否则这个位置所使用的 S_i（显然不是 T）一定比 T 更小，矛盾。

这样，我们有了这条性质，就只需要找到可以构造出的前缀中最短的即可。可以考虑 dp，设 f_i 代表当前答案串长度为 i，使用了最多的 S_i 的个数。这样每次枚举 j\in[i-10,i-1]、尝试让前缀串的 [j+1,i] 作为一个新的 S_i 拼入串中即可。至于如何取前缀串的某一区间，可以直接暴力把前缀串做出来。

这里可以使用字符串哈希，当然也可以用 map 直接实现，复杂度为 O(n|S_i|^2\log n)。当然，如果这里你使用哈希、且前面不排序而是直接找到最小的 T，那也可以做到 O(n|S_i|^2)。

代码仅作参考，跑了九百多毫秒，不能要了。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
string s[N],t;
int dp[N];
int n,k;
map<string,int>mp;
signed main(){
    memset(dp,0xcf,sizeof dp);
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        cin>>s[i];
        mp[s[i]] = 1;
    }
    sort(s+1,s+n+1,[&](auto x,auto y){
        return (x+y<y+x) || (x<y && x+y==y+x);
    });
    string S = " ";
    for(int i=1;i<=k;++i) S += s[1];
    dp[0] = 0;
    for(int i=1;i<(int)S.size();++i){
        string cur;
        for(int j=i;j>=i-10 && j;--j){
            cur = S[j] + cur;
            if(mp[cur]) dp[i] = max(dp[i],dp[j-1]+1);
        }
        cout<<S[i];
        if(dp[i]==k) return 0;
    }
    return 0;
}