CF1834C Game with Reversing

Alice 和 Bob 正在玩一个游戏。他们有两个长度为 $n$ 的字符串 $S$ 和 $T$，均由小写拉丁字母组成。两位玩家轮流操作，Alice 先手。 在她的回合，Alice 可以选择一个整数 $i$（$1 \le i \le n$），选择字符串 $S$ 或 $T$ 中的一个，并选择任意一个小写拉丁字母 $c$，然后将所选字符串的第 $i$ 个字符替换为字符 $c$。 在他的回合，Bob 可以选择字符串 $S$ 或 $T$ 中的一个，并将其反转。更正式地说，Bob 可以执行 $S := \operatorname{rev}(S)$ 或 $T := \operatorname{rev}(T)$，其中 $\operatorname{rev}(P) = P_n P_{n-1} \ldots P_1$。 游戏一直持续到 $S$ 和 $T$ 完全相同为止。一旦两个字符串相同，游戏立即结束。 游戏的持续时间定义为游戏过程中两位玩家总共进行的操作次数。例如，如果 Alice 总共操作了 $2$ 次，Bob 操作了 $1$ 次，则游戏持续时间为 $3$。 Alice 的目标是最小化游戏的持续时间，而 Bob 的目标是最大化游戏的持续时间。 如果两位玩家都采取最优策略，游戏将持续多少步？可以证明，游戏一定会在有限步内结束。

每个测试包含多组测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。接下来是每组测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示字符串 $S$ 和 $T$ 的长度。 第二行包含一个长度为 $n$ 的字符串 $S$，由小写拉丁字母组成。 第三行包含一个长度为 $n$ 的字符串 $T$，由小写拉丁字母组成。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试用例，输出一个整数，表示在两位玩家都采取最优策略的情况下，游戏的持续时间。每个答案占一行。

在第一个测试用例中，Alice 可以在她的回合将字符串 $S$ 的第 $3$ 个字符替换为 x。此后，两个字符串都变为 "abxde"，游戏在一次操作后结束。由于 Alice 的目标是尽快结束游戏，这将是她的最优首步操作之一，最终答案为 $1$。 在第二个测试用例中，Alice 可以在她的回合将字符串 $T$ 的第 $5$ 个字符替换为 h。此后，$S = $ "hello"，$T = $ "olleh"。然后 Bob 进行操作，他必须反转其中一个字符串。如果 Bob 选择反转 $S$，则两字符串都变为 "olleh"；如果他选择反转 $T$，则两字符串都变为 "hello"。因此，在 Alice 的上述首步操作后，游戏一定会在 $2$ 步内结束。可以证明，在双方都采取最优策略的情况下，Alice 无法在少于 $2$ 步内结束游戏，最终答案为 $2$。 在第三个测试用例中，Alice 可以在她的首步将字符串 $S$ 的第 $2$ 个字符替换为 c。此后，$S = $ "ac"，$T = $ "cd"。然后 Bob 进行操作。如果 Bob 反转字符串 $S$，则 $S = $ "ca"，$T = $ "cd"。此时 Alice 可以在第 $3$ 步将字符串 $T$ 的第 $2$ 个字符替换为 a，此后两个字符串都变为 "ca"。如果 Bob 反转字符串 $T$，则 $S = $ "ac"，$T = $ "dc"。此时 Alice 也可以在第 $3$ 步将字符串 $S$ 的第 $1$ 个字符替换为 d，此后两个字符串都变为 "dc"。因此，无论 Bob 如何操作，Alice 都可以确保在 $3$ 步内结束游戏。可以证明，在双方都采取最优策略的情况下，游戏无法在少于 $3$ 步内结束。 在第五个测试用例中，字符串 $S$ 和 $T$ 已经相等，因此游戏在开始前就结束了，持续时间为 $0$。 由 ChatGPT 4.1 翻译