题解：AT_abc434_f [ABC434F] Concat (2nd)

更差的阅读体验

---

别的题解把贪心策略和证明讲得很清楚了：先将所有字符串按照 \(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} \]

\(H_i\) 是调和级数前 \(i\) 项和。

\[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(n \log n)\) 的后缀数组做法好写多了。

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