← 返回题目列表

Codeforces · 1705/D

D. 马克和灯泡

中文机器翻译题面 查看原题

马克刚刚购买了一架 $$$n$$$ 灯泡。灯泡的状态可以用二进制字符串 $$$s = s_1s_2\dots s_n$$$ 来描述,其中 $$$s_i=\texttt{1}$$$ 表示第 $$$i$$$ 个灯泡打开,而 $$$s_i=\texttt{0}$$$ 表示第 $$$i$$$ 个灯泡关闭。

不幸的是,灯泡坏了,他可以执行的唯一操作来更改灯泡的状态如下:

- 从 $$$2,3,\dots,n-1$$$ 中选择索引 $$$i$$$,使得 $$$s_{i-1}\ne s_{i+1}$$$。
- 切换 $$$s_i$$$。即,如果 $$$s_i$$$ 为 $$$\texttt{0}$$$,则将 $$$s_i$$$ 设置为 $$$\texttt{1}$$$,反之亦然。

Mark 希望灯泡的状态是另一个二进制字符串 $$$t$$$。帮助马克确定执行此操作的最少操作数。

输入

输入的第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,打印一行,其中包含 Mark 将 $$$s$$$ 转换为 $$$t$$$ 所需执行的最少操作数。如果没有这样的操作序列,则打印$$$-1$$$。

示例

输入 #1

4
4
0100
0010
4
1010
0100
5
01001
00011
6
000101
010011

输出 #1

2
-1
-1
5

注意

在第一个测试用例中,实现最少操作数的操作序列如下。

- 选择 $$$i=3$$$,将 $$$\texttt{01}\color{red}{\texttt{0}}\texttt{0}$$$ 更改为 $$$\texttt{01}\color{red}{\texttt{1}}\texttt{0}$$$。
- 选择 $$$i=2$$$,将 $$$\texttt{0}\color{red}{\texttt{1}}\texttt{10}$$$ 更改为 $$$\texttt{0}\color{red}{\texttt{0}}\texttt{10}$$$。

在第三个测试用例中,尽管$$$s$$$和$$$t$$$的第一位数字相同,并且$$$s$$$和$$$t$$$的最后一位数字相同,但可以表明不存在满足条件的操作序列。

在第四个测试用例中,实现最少操作数的一个序列如下:

- 选择 $$$i=3$$$,将 $$$\texttt{00}\color{red}{\texttt{0}}\texttt{101}$$$ 更改为 $$$\texttt{00}\color{red}{\texttt{1}}\texttt{101}$$$。
- 选择 $$$i=2$$$,将 $$$\texttt{0}\color{red}{\texttt{0}}\texttt{1101}$$$ 更改为 $$$\texttt{0}\color{red}{\texttt{1}}\texttt{1101}$$$。
- 选择 $$$i=4$$$,将 $$$\texttt{011}\color{red}{\texttt{1}}\texttt{01}$$$ 更改为 $$$\texttt{011}\color{red}{\texttt{0}}\texttt{01}$$$。
- 选择 $$$i=5$$$,将 $$$\texttt{0110}\color{red}{\texttt{0}}\texttt{1}$$$ 更改为 $$$\texttt{0110}\color{red}{\texttt{1}}\texttt{1}$$$。
- 选择 $$$i=3$$$,将 $$$\texttt{01}\color{red}{\texttt{1}}\texttt{011}$$$ 更改为 $$$\texttt{01}\color{red}{\texttt{0}}\texttt{011}$$$。