我爱口胡之CSP-S2025T3

cjdstttttt

2025-11-03 23:39:51

发布于：广东

21阅读

0回复

0点赞

在家想了一整天+在学校想了一整天才想出来。

题意解析：

定义可替换字符串如下：

对于 $A,B,S,T(|A|=|B|,|S|=|T|,A\not= B,S\not= T)$ ，

若存在至少一个 $[l,r]$ 使得 $[S_l,...,S_r]=A$ ，且将其中一个 $[S_l,...,S_r]$ 替换为 $B$ 后 $S=T$ ，

则成 $A,B$ 为 $S,T$ 的可替换字符串。

给定 $n$ 个字符串组合 $[A_1,B_1],[A_2,B_2],...,[A_n,B_n]$ ，其中 $|A_i|=|B_i|$ 。给出 $q$ 次询问，每次询问给出两个字符串 $S_i,T_i$ ，求出满足 $A_i,B_i$ 为 $S_i,T_i$ 的可替换字符串的 $i$ 的个数，特别地，若 $|S_i|\not= |T_i|$ ，输出 0。

$1\le n,q\le 2\times 10^5,1\le \sum |A_i|+|B_i|,\sum |S_i|+|T_i|\le 5\times 10^6$ 。即 $\sum A_i\le 2.5\times 10^6$ ，且对于所有答案不为 $0$ 的询问， $\sum S_i\le 2.5\times 10^6$ 。

首先考虑如何才能满足 $A,B$ 为 $S,T$ 的可替换字符串。

定义两个字符串 $S,T(|S|=|T|,S\not= T)$ 的核心为在所有满足除去该区间以外，所有的 $S_i=T_i$ 的区间中，长度最短的一个。

令 $[l,r]$ 为 $S,T$ 的核心， $[l',r']$ 为 $B$ 的核心， $A,B$ 为 $S,T$ 的可替换字符串当且仅当：

$[S_l,...,S_r]=[A_{l'},...,A_{r'}]$ 。
$[T_l,...,T_r]=[B_{l'},...,B_{r'}]$ 。
$[...,A_{l'}]$ 为 $[...,S_{l-1}]$ 的后缀。
$[A_{r+1},...]$ 为 $[S_{r+1},...]$ 的前缀。

知道这个结论后，就可以通过哈希 $O(nq)$ 求出了，搭配性质 B 可以得到 $70pts$ 的高分。

而且正解也很简单了……吗？

接下来才是真正折磨的点。

首先前面两个要求可以通过哈希快速寻找，后面的要求字典树很可做。

所以考虑 umap 套 Trie 套 Trie。

umap 第一个值是字符串的哈希值，第二个值是第一个 Trie 的根，可以用来快速查找满足前面两个条件的 $A_i,B_i$ 。

两个 Trie 分别存储 $[...,A_{i,l}]$ 与 $[A_{i,r},...]$ ，其中第一个倒序存储。

这样预处理显然可以做到 $O(\sum |A_i|)$ 。

然后考虑查询怎么做。

我们先求出核心的哈希值，在 umap 里找。

然后遍历 $[S_i,...,S_l]$ ，如果有这个节点，就再暴力进入第二个 Trie 找 $[S_r,...,S_j]$ ，将答案加上存在的个数。

这样时间复杂度是多少？

首先看单次询问。

前面遍历 $[S_i,...,S_l]$ 是 $O(|S|)$ 的，后面遍历 $[S_r,...,S_j]$ 也是 $O(|S|)$ 的，所以看似是 $O(|S|^2)$ 的，但是注意到我们总共的节点最多有 $O(\sum |A_i|)$ 个，所以时间复杂度应为 $O(\min\{|S|^2,\sum |A_i|\}$ )。