CF1943F.Minimum Hamming Distance

给定一个长度为 $n$ 的二进制字符串 $s$。

如果一个长度同为 $n$ 的二进制字符串 $p$ 满足：对于每个 $i$（$1 \leq i \leq n$），都存在下标 $l$ 和 $r$，使得：

• $1 \leq l \leq i \leq r \leq n$
• $s_i$ 是字符串 $p_l p_{l+1} \ldots p_r$ 的众数 $^\ddagger$

则称 $p$ 为一个“好”字符串。

现在给定另一个长度为 $n$ 的二进制字符串 $t$，请你求出 $t$ 与任意一个“好”字符串 $g$ 的最小汉明距离 $^\S$。

$^\dagger$ 二进制字符串是仅由字符 $\mathtt{0}$ 和 $\mathtt{1}$ 组成的字符串。

$^\ddagger$ 字符 $c$ 是长度为 $m$ 的字符串 $p$ 的众数，如果 $c$ 在 $p$ 中出现的次数不少于 $\lceil \frac{m}{2} \rceil$。例如，$\mathtt{0}$ 是 $\mathtt{010}$ 的众数，$\mathtt{1}$ 不是 $\mathtt{010}$ 的众数，$\mathtt{0}$ 和 $\mathtt{1}$ 都是 $\mathtt{011010}$ 的众数。

$^\S$ 长度为 $m$ 的字符串 $a$ 和 $b$ 的汉明距离是满足 $1 \leq i \leq m$ 且 $a_i \neq b_i$ 的下标 $i$ 的个数。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的组数。

每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^4$），表示二进制字符串 $s$ 的长度。

第二行包含一个长度为 $n$ 的二进制字符串 $s$，仅包含字符 $0$ 和 $1$。

第三行包含一个长度为 $n$ 的二进制字符串 $t$，仅包含字符 $0$ 和 $1$。

保证所有测试用例中 $n$ 的总和不超过 $10^6$，且所有测试用例中 $n^2$ 的总和不超过 $10^8$。

对于每组测试用例，输出 $t$ 与任意一个“好”字符串 $g$ 的最小汉明距离。

在第一个测试用例中，$g=\mathtt{000}$ 是一个“好”字符串，与 $t$ 的汉明距离为 $0$。

在第二个测试用例中，$g=\mathtt{0011}$ 是一个“好”字符串，与 $t$ 的汉明距离为 $2$。可以证明不存在与 $t$ 的汉明距离小于 $2$ 的“好”字符串。

在第三个测试用例中，$g=\mathtt{001100}$ 是一个“好”字符串，与 $t$ 的汉明距离为 $1$。

由 ChatGPT 4.1 翻译