分数: 700 点
问题陈述
给你字符串 A 和 B 长度 N 组成 0 和 1。让 A_i 表示 i- 第一个字符 A.
您可以执行以下操作任意次数,可能为零。
- 选择一个整数 i\ (2 \leq i \leq N-1) 满意 A_{i-1} = A_{i+1},然后翻转 A_i (更改
1to0or0to1).
确定是否可以使 A 等于 B 通过重复操作,如果是,求所需的最少操作次数。
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1 \leq T \leq 2 \times 10^5
- 3 \leq N \leq 10^6
- A 和 B 是长度的字符串 N 组成
0和1. - T 和 N 是整数。
- 总和 N 所有测试用例最多 10^6.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N A B
输出
输出以下问题的答案 \mathrm{case}_1, \mathrm{case}_2, \ldots, \mathrm{case}_T 采用以下格式。
如果不可能 A 等于 B,打印 -1.
如果可能,请打印所需的最少操作数。
示例输入 1
4 4 0001 0111 6 101101 011100 5 10101 10101 10 0101000101 0011100111
示例输出 1
2 -1 0 6
对于第一个测试用例,您可以 A 等于 B 分两次操作如下。
- 选择 i = 2. A 变为
0101. - 选择 i = 3. A 变为
0111.
对于第二个测试用例,不可能使 A 等于 B 无论你如何操作。