[ABC386F] Operate K 的题解

ANDER_ · 2025-01-01 06:55:13 · 题解

考察：DP、二进制。

题意

判断是否有可能在 0 至 K \le 20 次对字符串 S 进行以下操作，使其与字符串 T 相同。

• 对于每次操作，从以下三个子操作中选择一个并执行。

  • 在 S 的任意位置插入一个字符（可能是开头或结尾）。
  • 从 S 中删除一个字符。
  • 在 S 中选择一个字符并替换为另一个字符。

    数据限制

• ## 思路一 用 DP，设 $dp_{i,j}$ 表示将 $S_1...S_i$ 改成 $T_1...T_j$，最少需要几次操作。最后只需要判断 $dp_{N,M} \le K$ 即可。分操作进行转移：

• 删除一个字符，即 dp_{i - 1,j} + 1。

• 添加一个字符，即 dp_{i,j - 1} + 1。

• 修改一个字符，即 dp_{i - 1,j - 1} + 1。

• 不需要操作，满足 S_i = T_j，即 dp_{i - 1, j - 1}。

这要暴力的时间复杂度为 \mathcal{O}(NM)，起飞了。

注意到 K \le 20，且对于字符串 S,T 的修改次数 tim \ge |(|S|-|T|)|。对于 DP，在 dp_{i,j} 中，若 |i - j| > K，再去计算它毫无意义。只考虑 |i - j| \le K 的 dp_{i,j} 即可，时间复杂度降为 \mathcal{O}(NK)。

对于在 DP 过程中类似这样的优化，我们将此方法称为 稀疏性优化（Sparsity），这本来是人工智能里的一个内容。抽象成一个坐标系 xOy 的第一象限，可以这样 OI 的理解：

• 若 dp_{i,j} 被计算有意义，在 xOy 中记录一个点 (i,j)。若这些点分布在一条由点 A = (0,k_1),B = (k_2, 0) 连成的线段 AB 附近（其中 k_1,k_2 \isin \R_+）。那么只需要计算一部分的点，而不是计算所有满足 i \isin (0,k_1],j\isin (0,k_2] 的点 (i,j)。

其本质上是来解一个线性方程组，其中 x \isin \R^n,y \isin \R^m，矩阵 A \isin \R^{n\times m}，且 m \ll n：

这里没必要继续深入，代码并不难写，跑了 147ms。

思路二

我们发现 DP 数组中存储的值都不大，所以可以把数组的定义改一下：dp_{i,r} 表示 S_1...S_i 在经过 r 次操作之后，能匹配到哪些 T_1...T_j。也就是说，每个 dp_{i,r} 都是一个 vector。但是，如果暴力维护 vector，复杂度是 \mathcal{O}(NK^2) 的，会超时。

注意到，\forall x \isin dp_{i,r}(x \isin [i - r,i + r])。这个值域大小不会超过 2\times K + 1，因此可以使用 long long 进行压位，转移时使用位运算即可。转移方程与思路一类似，无需赘述。

时间复杂度为 \mathcal{O}(NK)，但常数比较小，跑了 93ms。代码。