分数: 1000 点
问题陈述
你有两个长度-N 字符串 A = A_1A_2 \ldots A_N 和 B = B_1B_2 \ldots B_N,每个由 0 和 1.
有 N 方块从左到右排成一行。对于 i = 1, 2, \ldots, N, i从左边算起第一个方格称为方格 i。最初,正方形 i 包含一个片段,如果 A_i = 1,并且如果 A_i = 0.
您可以重复以下操作任意次数(可能为零):
- 选择一个整数 i 之间 1 和 N,包括在内。
- 同时将所有棋子移近一格 i。也就是说,对于每一块,让平方 j 是其当前位置和方块 j' 为其新位置,并且以下内容成立:
- if i < j,那么 j' = j-1;
- if i > j,那么 j' = j+1;
- if i = j,那么 j' = j.
确定是否有可能达到满足以下条件的配置,如果可能,则找到所需的最少操作数:
对于每个 i = 1, 2, \ldots, N,正方形中至少有一块 i 当且仅当 B_i =
1.
你被给予 T 独立测试用例。打印每个人的答案。
约束
- 1 \leq T \leq 2 \times 10^5
- 1 \leq N \leq 10^6
- T 和 N 是整数。
- A 和 B 是长度的字符串 N,每个由
0和1. - 存在 i 这样 A_i =
1. - 存在 i 这样 B_i =
1. - 总和 N 所有测试用例最多 10^6.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
在这里, \mathrm{case}_i (i=1,2,\ldots,T) 表示 i- 第一个测试用例。
每个测试用例均按以下格式给出:
N A B
输出
打印 T 行。
对于每个 i = 1, 2, \ldots, T,在 i第行,打印 -1 如果不可能达到满足条件的配置 i- 第一个测试用例。否则,打印所需的最少操作数。
示例输入 1
3 8 01001101 00001011 3 010 111 20 10100011011110101011 00010001111101100000
示例输出 1
3 -1 5
输入具有三个独立的测试用例。
在第一个测试用例中,最初,方格中棋子的数量顺序为 (0, 1, 0, 0, 1, 1, 0, 1)。通过如下操作3次,即可满足条件:
- 选择 i = 5。运行后配置为 (0, 0, 1, 0, 2, 0, 1, 0).
- 选择 i = 8。运行后配置为 (0, 0, 0, 1, 0, 2, 0, 1).
- 选择 i = 8。运行后配置为 (0, 0, 0, 0, 1, 0, 2, 1).
不可能用少于 3 次的操作来满足条件,所以答案是 3.
在第二个测试用例中,无论你如何执行操作,都无法满足条件,所以答案是 -1.