CF1705D Mark and Lightbulbs

Mark 刚刚买了一排 $n$ 个灯泡。灯泡的状态可以用一个二进制字符串 $s = s_1s_2\dots s_n$ 来描述，其中 $s_i=\texttt{1}$ 表示第 $i$ 个灯泡是开着的，$s_i=\texttt{0}$ 表示第 $i$ 个灯泡是关着的。 不幸的是，这些灯泡坏了，他唯一能进行的操作如下： - 选择一个下标 $i$，其中 $2 \leq i \leq n-1$，并且满足 $s_{i-1} \ne s_{i+1}$。 - 翻转 $s_i$。也就是说，如果 $s_i$ 是 $\texttt{0}$，就将其变为 $\texttt{1}$，反之亦然。 Mark 想要将灯泡的状态变为另一个二进制字符串 $t$。请你帮助 Mark 计算最少需要多少次操作才能实现。

输入的第一行包含一个整数 $q$（$1 \leq q \leq 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 2 \cdot 10^5$），表示灯泡的数量。 每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$，表示初始状态。 每个测试用例的第三行包含一个长度为 $n$ 的二进制字符串 $t$，表示目标状态。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行，表示将 $s$ 变为 $t$ 所需的最小操作次数。如果无法通过操作实现，输出 $-1$。

在第一个测试用例中，实现最小操作次数的一种操作序列如下： - 选择 $i=3$，将 $\texttt{01}\color{red}{\texttt{0}}\color{black}\texttt{0}$ 变为 $\texttt{01}\color{red}{\texttt{1}}\color{black}\texttt{0}$。 - 选择 $i=2$，将 $\texttt{0}\color{red}{\texttt{1}}\color{black}\texttt{10}$ 变为 $\texttt{0}\color{red}{\texttt{0}}\color{black}\texttt{10}$。 在第二个测试用例中，没有可行的操作序列，因为无法改变 $s$ 的第一个或最后一个数字。 在第三个测试用例中，尽管 $s$ 和 $t$ 的首位和末位相同，但可以证明不存在满足条件的操作序列。 在第四个测试用例中，实现最小操作次数的一种操作序列如下： - 选择 $i=3$，将 $\texttt{00}\color{red}{\texttt{0}}\color{black}\texttt{101}$ 变为 $\texttt{00}\color{red}{\texttt{1}}\color{black}\texttt{101}$。 - 选择 $i=2$，将 $\texttt{0}\color{red}{\texttt{0}}\color{black}\texttt{1101}$ 变为 $\texttt{0}\color{red}{\texttt{1}}\color{black}\texttt{1101}$。 - 选择 $i=4$，将 $\texttt{011}\color{red}{\texttt{1}}\color{black}\texttt{01}$ 变为 $\texttt{011}\color{red}{\texttt{0}}\color{black}\texttt{01}$。 - 选择 $i=5$，将 $\texttt{0110}\color{red}{\texttt{0}}\color{black}\texttt{1}$ 变为 $\texttt{0110}\color{red}{\texttt{1}}\color{black}\texttt{1}$。 - 选择 $i=3$，将 $\texttt{01}\color{red}{\texttt{1}}\color{black}\texttt{011}$ 变为 $\texttt{01}\color{red}{\texttt{0}}\color{black}\texttt{011}$。 由 ChatGPT 4.1 翻译