← 返回题目列表

Codeforces · 2061/F2

F2. 凯文和二进制字符串(硬版)

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

这是问题的困难版本。版本之间的区别在于,在此版本中,字符串$$$t$$$ 由'0'、'1' 和'?' 组成。只有解决了该问题的所有版本,您才能破解。

Kevin 有一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$。 Kevin 可以执行以下操作:

- 选择 $$$s$$$ 的两个相邻块并交换它们。

块是相同字符的最大子串$$$^{\text{*}}$$$。形式上,将 $$$s[l,r]$$$ 表示为子字符串 $$$s_l s_{l+1} \ldots s_r$$$。一个块是 $$$s[l,r]$$$ 满足:

- $$$l=1$$$ 或 $$$s_l\not=s_{l-1}$$$。
- $$$s_l=s_{l+1} = \ldots = s_{r}$$$。
- $$$r=n$$$ 或 $$$s_r\not=s_{r+1}$$$。

相邻块是满足 $$$r_1+1=l_2$$$ 的两个块 $$$s[l_1,r_1]$$$ 和 $$$s[l_2,r_2]$$$。

例如,如果 $$$s=\mathtt{000}\,\mathbf{11}\,\mathbf{00}\,\mathtt{111}$$$,Kevin 可以选择两个块 $$$s[4,5]$$$ 和 $$$s[6,7]$$$ 并交换它们,将 $$$s$$$ 转换为$$$\mathtt{000}\,\mathbf{00}\,\mathbf{11}\,\mathtt{111}$$$。

给定一个长度为 $$$n$$$ 的字符串 $$$t$$$,由 '0'、'1' 和 '?' 组成,Kevin 希望确定执行所需的最小操作数,使得对于任何索引 $$$i$$$ ($$$1\le i\le n$$$),如果 $$$t_i\not=$$$ '?'那么$$$s_i=t_i$$$。如果不可能,则输出$$$-1$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个由“0”和“1”组成的字符串$$$s$$$。

每个测试用例的第二行包含一个由“0”、“1”和“?”组成的字符串$$$t$$$。

保证$$$s$$$ 和$$$t$$$ 的长度相同。

保证所有测试用例$$$s$$$的长度总和不会超过$$$4\cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数——所需的最少操作数。如果不可能,则输出$$$-1$$$。

示例

输入 #1

6
0001100111
0000011111
010101
111000
0101
0110
0101
1010
011001
001110
0
1

输出 #1

1
3
1
-1
-1
-1

输入 #2

6
010101
?0?0??
0101
?0?0
11100101
????????
11100101
???11?1?
1000100011
?11?000?0?
10101
?1011

输出 #2

2
-1
0
2
2
-1

注意

在第一个示例的第一个测试用例中,语句中显示了可能的方式。

在第一个示例的第二个测试用例中,一种可能的方法是:

- 交换块 $$$[2, 2], [3, 3]$$$, $$$s$$$ 将变为 $$$\mathtt{001101}$$$。
- 交换块 $$$[3, 4], [5, 5]$$$, $$$s$$$ 将变为 $$$\mathtt{000111}$$$。
- 交换块 $$$[1, 3], [4, 6]$$$, $$$s$$$ 将变为 $$$\mathtt{111000}$$$。

在第二个示例的第一个测试用例中,一种可能的方法是:

- 交换块 $$$[1, 1], [2, 2]$$$, $$$s$$$ 将变为 $$$\mathtt{100101}$$$。
- 交换块 $$$[4, 4], [5, 5]$$$, $$$s$$$ 将变为 $$$\mathtt{100011}$$$。