2896. 执行操作使两个字符串相等

发表于 2026-01-10 分类于力扣阅读次数： Waline：本文字数： 2.9k 阅读时长 ≈ 10 分钟

考点

线性DP
状态机DP
数学
贪心

思路

1. 问题重述与关键观察

给定两个等长二进制串 $s_1, s_2$，允许两类操作，使 $s_1$ 变为 $s_2$：

任选两个下标 $i \neq j$，同时翻转 $s_1[i]$ 与 $s_1[j]$，代价为 $x$。
任选相邻下标 $i, i+1$，同时翻转 $s_1[i]$ 与 $s_1[i+1]$，代价为 $1$。

目标是最小化总代价。

本题的困难点在于：每次操作都同时改变两个位置，看似难以直接对字符串位置做 DP。关键在于先做等价建模。

2. 建模：转化为异或差分序列

定义长度为 $n$ 的序列 $d$： \[ d[i] = s_1[i] \oplus s_2[i], \quad i=0,1,\dots,n-1 \] 其中 $\oplus$ 表示按位异或。显然：

若 $d[i]=0$，说明当前位置已经相同；
若 $d[i]=1$，说明当前位置不同，需要“修正”。

目标“将 $s_1$ 变成 $s_2$”等价于“将 $d$ 全部变为 0”。

2.1 两种操作在 $d$ 上的等价效果

操作 1：翻转 $s_1[i], s_1[j]$。由于 $s_2$ 不变，因此： \[ d[i] \leftarrow d[i]\oplus 1,\quad d[j] \leftarrow d[j]\oplus 1 \] 即：同时翻转 $d$ 的两个位置，代价为 $x$。
操作 2：翻转相邻 $s_1[i], s_1[i+1]$。同理： \[ d[i] \leftarrow d[i]\oplus 1,\quad d[i+1] \leftarrow d[i+1]\oplus 1 \] 即：同时翻转 $d$ 的相邻两个位置，代价为 $1$。

因此，问题完全转化为：

给定一个 01 序列 $d$，每次可翻转任意两位（代价 $x$）或翻转相邻两位（代价 $1$），问最小代价使全为 0。

3. 奇偶性判定：为什么 1 的个数必须为偶数

无论哪一种操作，每次都会翻转 $d$ 的两个位置，因此序列中 “1 的个数的奇偶性” 不会改变：

翻转两个位置后，1 的数量要么 $\pm 2$，要么不变，但不会改变奇偶性。

因此： \[ \#\{ i \mid d[i]=1 \} \text{ 必须为偶数，否则无解} \] 若为奇数，直接返回 $-1$。

4. 第二种操作（相邻翻转）的“真正用途”

很多人会误以为操作 2 只能“消去两个相邻的 1”。实际上，它的用途更强：可以用多次相邻翻转把一个不一致点“传递”到另一个不一致点，从而消去它们。

4.1 距离代价：两处不一致的消去成本为距离

设 $d$ 中只有两个 1，位置为 $a，其余位置为 0。

反复执行相邻翻转： \[ (a,a+1),\ (a+1,a+2),\ \dots,\ (b-1,b) \] 每次代价为 1，共执行 $b-a$ 次。效果是这两个 1 被消掉。于是： \[ \text{用操作 2 消去 }(a,b)\text{ 这一对的最小代价} = b-a \] 这给出一个关键抽象： 用操作 2 相当于以“距离”为代价，将两处不一致配对消除。

4.2 反证法证明：用第二种操作形成的“距离配对”不需要跨越，只要管 `arr` 相邻即可

设不相等下标升序为 arr。考虑任意一个解，把每一对不相等点的消去方式分成两类：

距离配对：通过若干次相邻翻转（第二种操作）消掉一对 $(u,v)$，代价为 $v-u$；
x 配对：通过一次第一种操作消掉一对 $(u,v)$，代价为 $x$。

命题

存在一个最优解，使得所有“距离配对”都只发生在 arr 中相邻的两个不相等点之间（即不会跳过中间的不相等点）。

证明（反证法 + 替换）

假设命题不成立。则存在一个最优解 $S$，其中至少有一条“距离配对”是跨越的：存在 $a，且 $a,c$ 都是不相等点，$b$ 是 $a$ 右边紧挨着的下一个不相等点，但 $S$ 用距离把 $a$ 与 $c$ 配对消掉（跳过了 $b$）。

记 $b$ 在解 $S$ 中的配对对象为 $d$（必存在，因为每个点必须被消去一次），于是有两种情况：

情况 1：$(b,d)$ 是 x 配对

此时 $S$ 在这四个点上用了：

距离配对 $(a,c)$，成本 $c-a$
x 配对 $(b,d)$，成本 $x$

总成本（只看这部分）为： \[ (c-a) + x \] 构造新解 $S'$：把这两对替换为

距离配对 $(a,b)$，成本 $b-a$
x 配对 $(c,d)$，成本仍为 $x$（因为第一种操作不看距离）

新成本为： \[ (b-a) + x \] 由于 $b，所以 $b-a < c-a$，从而 \[ (b-a) + x < (c-a) + x \] 也就是说 $S'$ 比 $S$ 更便宜，矛盾于 $S$ 是最优解。

情况 2：$(b,d)$ 是距离配对

由于 $a，并且 $a$ 已经用距离连到 $c$，为了让 $b$ 再用距离配对但不“卡死”，其对象必在 $c$ 右侧（否则两条距离配对会形成“交叉/嵌套”，总之可以用更短的配法替换；这里给出最常用的四点形式即可）。取最典型也最关键的形态 $a，且 $S$ 用距离配对了：

$(a,c)$，成本 $c-a$
$(b,d)$，成本 $d-b$

总成本为： \[ (c-a) + (d-b) \] 构造新解 $S'$：把两对替换为“挨着”的

$(a,b)$，成本 $b-a$
$(c,d)$，成本 $d-c$

新成本为： \[ (b-a) + (d-c) \] 比较两者差值： \[ [(c-a)+(d-b)] - [(b-a)+(d-c)] = 2(c-b) > 0 \] 因此新成本严格更小，同样矛盾于 $S$ 最优。

两种情况都得到矛盾，所以最初假设不成立。命题得证。

结论落地到 DP：为什么“距离转移”只写相邻即可

上面证明告诉我们：在某个最优解里，凡是决定用第二种操作（距离）消掉的一对，一定可以假设它来自 arr 里相邻的两点，其代价就是 \[ \Delta = \text{arr}[i-1] - \text{arr}[i-2] \] 因此 DP 只需要这一种距离转移，不需要枚举跨越的 $\text{arr}[i]-\text{arr}[j]$。

同时，“跨越配对”真正需要考虑的部分由第一种操作承担（因为它成本固定为 $x$，并且 DP 通过“留一个点以后用 $x$ 配”来覆盖所有跨越可能）。

5. 只保留不一致的位置：下标数组 `arr`

令不一致位置集合为： \[ \text{arr} = \{ i \mid d[i]=1 \} \] 按升序排列，记 arr[0..n-1]，其中 $n$ 为不一致个数（注意这里 $n$ 与原串长度不同）。

问题变为：对这些位置做最小代价配对消除：

可以用一次代价 $x$ 的操作，直接消去任意两处不一致；
可以用代价 $\text{arr}[j]-\text{arr}[i]$ 的方式（来自操作 2 的连续使用）消去一对不一致。

6. 状态设计：二维 DP（处理到第 $i$ 个不一致位置）

6.1 状态含义

定义 $f[i][t]$：

$f[i][0]$：处理完前 $i$ 个不一致点（arr[0..i-1]），并且 当前没有“落单”的不一致点。
$f[i][1]$：处理完前 $i$ 个不一致点，当前 有恰好一个“落单”的不一致点，留待后续用代价 $x$ 的操作去配对消除。

这里的“落单”只表示“已经看过但尚未被配对消掉的不一致点数量为 1”；不需要记录它的具体下标，因为一旦选择用代价 $x$ 的操作配对，成本与距离无关。

初始化： \[ f[0][0]=0,\quad f[0][1]=+\infty \] 目标答案为 $f[n][0]$。

7. 状态转移（精确描述）

记当前处理到第 $i$ 个不一致点（1-indexed 表述），即位置为 $\text{arr}[i-1]$。

7.1 让当前点成为“落单”（开启落单）

若之前没有落单（状态 0），则可以让当前点暂不配对，成为落单： \[ f[i][1] = \min\bigl(f[i][1],\ f[i-1][0]\bigr) \]

7.2 用代价 $x$ 消去“落单 + 当前点”（关闭落单）

若之前有一个落单（状态 1），则可用操作 1（任意两点翻转）把落单点与当前点配对消去： \[ f[i][0] = \min\bigl(f[i][0],\ f[i-1][1] + x\bigr) \]

7.3 用“距离代价”消去最近两个点（使用操作 2 的连续效果）

当 $i\ge 2$ 时，可以把最近的两个不一致点 $\text{arr}[i-2]$ 与 $\text{arr}[i-1]$ 通过操作 2 连续使用消去，代价为： \[ \Delta = \text{arr}[i-1] - \text{arr}[i-2] \]

如果之前没有落单：

\[ f[i][0] = \min\bigl(f[i][0],\ f[i-2][0] + \Delta\bigr) \]

如果之前已经有一个落单，那么把最近两个点用距离消掉不会影响落单，落单仍然存在：

\[ f[i][1] = \min\bigl(f[i][1],\ f[i-2][1] + \Delta\bigr) \]

这条转移非常关键：它表示“先把眼前这两点用距离消掉，之前的落单不受影响”。

8. 编程实现要点

先构造 arr 收集所有 $s_1[i]\neq s_2[i]$ 的下标。
若 arr.size() 为奇数，直接返回 $-1$。
DP 维度最大为 $n \le 500$（不一致点数不会超过原串长度），用 f[505][2] 足够。
INF 用 0x3f3f3f3f（或更大）初始化，防止溢出时建议用 long long，但该题数据范围下 int 通常可过；若追求严谨，可改成 long long。

9. AC 代码

class Solution {
public:
    int minOperations(string s1, string s2, int x) {
        // f[i][0/1]:
        // i: 已处理完前 i 个不相等的位置（arr[0..i-1]）
        // 0: 当前没有“落单”的不相等点
        // 1: 当前有 1 个“落单”的不相等点，等待未来用一次代价 x 的操作去配对消掉
        int f[505][2];
        memset(f, 0x3f, sizeof(f));

        // 初始：处理 0 个不相等点，且没有落单 => 代价 0
        f[0][0] = 0;
        f[0][1] = 0x3f3f3f3f;

        // 收集所有不相等的位置下标（即 d[i]=1 的位置）
        vector<int> arr;
        int c = 0;
        for (int i = 0; i < (int)s1.size(); ++i) {
            if (s1[i] != s2[i]) {
                arr.push_back(i);
                ++c;
            }
        }

        // 奇偶性：不相等个数为奇数，无解
        if (c & 1) return -1;
        // 没有不相等，已经相同
        if (!c) return 0;

        int n = (int)arr.size();

        // 逐个处理不相等点（i 从 1 到 n，当前点是 arr[i-1]）
        for (int i = 1; i <= n; ++i) {

            // (1) 让当前点 arr[i-1] 暂时不配对，变成“落单”
            // 前提：之前没有落单（状态 0）
            f[i][1] = f[i - 1][0];

            // (2) 用一次代价 x 的操作，把“落单 + 当前点”配对消掉
            // 前提：之前有落单（状态 1）
            f[i][0] = min(f[i][0], f[i - 1][1] + x);

            // (3) 用操作 2 的连续使用，把最近两个不相等点配对消掉
            // 也就是把 arr[i-2] 与 arr[i-1] 这一对，用距离代价 Δ 消掉
            if (i >= 2) {
                int dist = arr[i - 1] - arr[i - 2];

                // 3a) 之前没有落单：消掉两点后仍没有落单
                f[i][0] = min(f[i][0], f[i - 2][0] + dist);

                // 3b) 之前有落单：消掉这两点并不会影响那个落单，仍然保持落单
                f[i][1] = min(f[i][1], f[i - 2][1] + dist);
            }
        }

        // 最终必须没有落单（全部配对消掉），即 f[n][0]
        return f[n][0] == 0x3f3f3f3f ? -1 : f[n][0];
    }
};

10. 总结

先用 $d = s_1 \oplus s_2$ 把“改 $s_1$”转成“消掉 $d$ 的 1”。
奇偶性决定可行性：1 的数量必须为偶数。
操作 2 的价值在于：可以用多次相邻翻转以“距离”为代价消去一对不一致，而不是只能处理相邻的两个 1。
DP 的核心在于：扫描不一致点序列 arr，维护“是否有一个落单点等待用 $x$ 配对”，并在每一步考虑：
- 开启落单；
- 用 $x$ 关闭落单；
- 用距离消去最近两个不一致点（同时兼顾“有落单/无落单”两种情况）。

2896. 执行操作使两个字符串相等

考点

思路

1. 问题重述与关键观察

2. 建模：转化为异或差分序列

2.1 两种操作在 \(d\) 上的等价效果

3. 奇偶性判定：为什么 1 的个数必须为偶数