专栏文章

P9873 [EC Final 2021] Beautiful String

AAutream
P9873题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio6elks
此快照首次捕获于
2025/12/02 14:07
3 个月前
此快照最后确认于
2025/12/02 14:07
3 个月前
查看原文
题目要求形如 AABCABAABCAB 的子串的个数。观察到其中有两个 ABAB，考虑去枚举第一个 ABAB，那么满足要求的子串就是 ABAB 前面紧跟着一个它的前缀，在它后面还有一个 ABAB 不与它相邻。
设第一个 ABAB 的第一个字符在位置 ii，第二个 ABAB 的第一个字符在位置 jj，l1=∣A∣,l2=∣AB∣l_1 = |A|, l_2 = |AB|，为了保证 AA 非空，l1<l2l_1 < l_2。
那么前后能匹配的最大长度就是 ma=min⁡{j−i−1,lcpi,j}ma = \min \{j - i - 1, lcp_{i, j}\}，其中 lcpi,jlcp_{i, j} 表示以 ii 开头的后缀和以 jj 开头的后缀的最长公共前缀，可以 O(n2)O(n ^ 2) 预处理，j−i−1j - i - 1 是因为要保证它们不相邻，所以长度最大为这么多。
答案即为：
∑i∑j∑l2=1ma∑l1=1l2−1[lcpi−l1,i≥l1]\sum _i \sum _j \sum _{l_2 = 1} ^{ma} \sum _{l_1 = 1} ^{l_2 - 1} [lcp_{i - l_1, i} \ge l_1]
i,ji, j 是必须要枚举的，考虑优化后面的循环。
将内层循环展开：
∑l1=1ma−1(ma−l1)×[lcpi−l1,i≥l1]\begin{aligned} \sum _{l_1 = 1} ^{ma - 1} (ma - l_1)\times [lcp_{i - l_1, i} \ge l_1] \end{aligned}
继续展开并整理可得原式是以下项的和：
l1=1:[lcpi−1,i≥1]l1=2:[lcpi−1,i≥1],[lcpi−2,i≥2]l1=3:[lcpi−1,i≥1],[lcpi−2,i≥2],[lcpi−3,i≥3]⋮l1=ma−1:[lcpi−1,i≥1],[lcpi−2,i≥2],[lcpi−3,i≥3],…,[lcpi−ma+1,i≥ma−1]\begin{aligned} &l_1 = 1: [lcp_{i - 1, i} \ge 1] \\ &l_1 = 2: [lcp_{i - 1, i} \ge 1], [lcp_{i - 2, i} \ge 2] \\ &l_1 = 3: [lcp_{i - 1, i} \ge 1], [lcp_{i - 2, i} \ge 2], [lcp_{i - 3, i} \ge 3] \\ \vdots \\ &l_1 = ma - 1: [lcp_{i - 1, i} \ge 1], [lcp_{i - 2, i} \ge 2], [lcp_{i - 3, i} \ge 3] , \dots, [lcp_{i - ma + 1, i} \ge ma - 1] \end{aligned}
应该很好想了，发现每一行行内可以前缀和优化，之后再将每一行做前缀和。
具体地，设
fi,j=∑k=1j[lcpi−k,i≥j]gi,j=∑k=1j(j−k+1)×[lcpi−k,i≥k]=∑k=1jfi,k\begin{aligned} &f_{i, j} = \sum \limits _{k = 1} ^j [lcp_{i - k, i} \ge j] \\ &g_{i, j} = \sum _{k = 1} ^ j (j - k + 1) \times [lcp_{i - k, i} \ge k] = \sum \limits _{k = 1} ^j f_{i, k} \end{aligned}
最后答案为 ∑i∑jgi,ma−1\sum \limits _i \sum \limits _j g_{i, ma - 1}，注意越界处理。
时间复杂度 O(n2)O(n ^ 2)。

代码

CPP
CI N = 5e3 + 5;
int n, ans, lcp[N][N], f[N][N], g[N][N];
std::string s;
signed main() {
	int T = read();
	while(T --) {
		std::cin >> s, n = s.size(), s = " " + s, ans = 0;
		dep(i, n, 1) dep(j, n, i) if(s[i] == s[j]) lcp[i][j] = lcp[i + 1][j + 1] + 1;
		rep(i, 1, n) rep(j, 1, n) f[i][j] = i - j >= 0 ? f[i][j - 1] + (lcp[i - j][i] >= j) : f[i][i];
		rep(i, 1, n) rep(j, 1, n) g[i][j] = g[i][j - 1] + f[i][j];
		rep(i, 2, n) rep(j, i + 3, n - 1) ans += g[i][std::max(1ll, std::min(j - i - 1, lcp[i][j])) - 1];
		printl(ans);
		rep(i, 1, n) rep(j, 1, n) lcp[i][j] = f[i][j] = g[i][j] = 0;
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...