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

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

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

以下的所有大写字母代表字符串；
$X+Y$ 代表 $X$ 和 $Y$ 拼接起来形成的字符串；
$X^n$ 代表 $X$ 重复 $n$ 次形成的字符串；
$X<Y$ 代表 $X$ 的字典序小于 $Y$ （注意，本文中的 $<$ 不等同于 $\prec$ ）。
以下设 $n,k$ 同阶。

我们考虑套路地定义一种全序关系：字符串

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)

。

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

CPP

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

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

文章操作

相关推荐

评论

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