题解：AT_abc434_f [ABC434F] Concat (2nd)
dyc2022
·
·
题解
更好的阅读体验
别的题解把贪心策略和证明讲得很清楚了：先将所有字符串按照 s_i + s_j < s_j + s_i 排序，然后尝试交换 s_n, s_{n-1} 和 s_{n-1}, s_{n-2}，比较字典序。
大家做法的差别大部分都是在按照 s_i + s_j < s_j + s_i 的排序上。然后就发现了一个很趣味的事情：将 s random_shuffle 一下，然后直接比，能过。
为啥。其实这个复杂度是对的。
容易发现这样一次比较的复杂度是 |s_i| + |s_j|。我们钦定随机打乱之后，每个数字参与的比较次数是相等的，假设对于 n，单个数参与比较的次数为 E_0(n)。假设 E(n) 为全局比较次数，那么 E(n) = n E_0(n)。
我们了解快排的算法过程：把一部分数字分到左边，另外一部分分到右边。我们认为划分点也是随机的。
E(n) = \frac{1}{n-1} \sum_{k=1}^{n-1}[E(k) + E(n-k) + n]
其中 +n 是把数字分成两组的比较次数。
把常数和每个 E(k) 的贡献领出来，可以得到
E(n) = n + \frac{2}{n-1}\sum_{k=1}^{n-1}E(k)
接下来假设 S(k) = \sum_{i=1}^{k} E(i)。
S(n) - S(n-1) = n + \frac{2}{n-1}S(n-1)
S(n) = n + \frac{n+1}{n-1}S(n-1)
\frac{S(n)}{n(n+1)} = \frac{1}{n+1}+\frac{S(n-1)}{(n-1)n}
\frac{S(n)}{n(n+1)} = \sum_{i = 3}^{n+1} \frac{1}{i} = H_{n+1} - \frac{3}{2}
$$S(n) = n(n+1)(H_{n+1} - \frac{3}{2})$$
$$
\begin{align}
E(n) &= S(n) - S(n-1) \nonumber \\
&= n(n+1)(H_{n+1} - \frac{3}{2}) - n(n-1)(H_n - \frac{3}{2})\nonumber \\
&= n[(n+1)H_{n+1}-nH_n - 3] \nonumber \\
&= n[(n+1)(H_n + \frac{1}{n+1}) - nH_n - 3] \nonumber \\
&= 2n(H_n - 1) \nonumber \\
&= O(n \ln n) \nonumber
\end{align}
$$
$$E_0(n) = O(\ln n)$$
所以一个字符串均摊下来会被计算 $O(\ln n)$ 次，总复杂度 $O(\sum|s_i| \log n)$，非常优秀，比 $O(\sum|s_i| \log n + n \log n)$ 的后缀数组做法牛逼而且好写多了！
```cpp
#include<bits/stdc++.h>
#define endl '\n'
#define N 1000006
using namespace std;
int n;
string t[N],s1,s2,s3;
inline bool cmp(string x,string y){return x+y<y+x;}
void solve()
{
cin>>n,s1=s2=s3=""; int tot=0;
for(int i=1;i<=n;i++)cin>>t[i],tot+=t[i].length();
random_shuffle(t+1,t+1+n);
sort(t+1,t+1+n,cmp);
for(int i=1;i<=n;i++)s1+=t[i]; swap(t[n],t[n-1]);
for(int i=1;i<=n;i++)s2+=t[i]; swap(t[n],t[n-1]);
if(n>2)
{
swap(t[n-1],t[n-2]);
for(int i=1;i<=n;i++)s3+=t[i]; swap(t[n-1],t[n-2]);
} else for(int i=1;i<=tot+1;i++)s3+='z';
string ans=min(s2,s3);
for(int i=2;i<=n;i++)
if(t[i]+t[i-1]==t[i-1]+t[i]){ans=min(s1,ans); break;}
cout<<ans<<endl;
}
main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T; cin>>T; while(T--)solve();
return 0;
}
```