AT_arc193_d [ARC193D] Magnets

[problemUrl]: https://atcoder.jp/contests/arc193/tasks/arc193_d 给定两个仅由 `0` 和 `1` 组成的长度为 $N$ 的字符串 $A = A_1A_2\ldots A_N$ 和 $B = B_1B_2\ldots B_N$。 有 $N$ 个单元格从左到右排成一列。对于 $i = 1, 2, \ldots, N$，左数第 $i$ 个单元格称为单元格 $i$。初始时，若 $A_i = $ `1`，则单元格 $i$ 放置 $1$ 个棋子；若 $A_i = $ `0`，则单元格 $i$ 没有棋子。 你可以进行任意次数（包括 $0$ 次）的以下操作： 1. 首先选择整数 $i$（$1 \leq i \leq N$）。 2. 然后，将所有棋子**同时**向单元格 $i$ 靠近的方向移动 $1$ 个单元格。具体规则如下：设某个棋子移动前的位置为单元格 $j$，移动后的位置为单元格 $j'$， - 若 $i < j$，则 $j' = j - 1$； - 若 $i > j$，则 $j' = j + 1$； - 若 $i = j$，则 $j' = j$。 请判断是否可以通过上述操作使网格满足以下条件，若可能，还需输出达成该条件所需的最小操作次数： > 对于所有 $i = 1, 2, \ldots, N$，当且仅当 $B_i = $ `1` 时，单元格 $i$ 中存在至少 $1$ 个棋子。 给定 $T$ 个独立的测试用例，请分别输出每个用例的答案。

输入通过标准输入给出，格式如下： > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ 其中，$\mathrm{case}_i$ 表示第 $i$ 个测试用例。每个测试用例的格式为： > $N$ $A$ $B$

输出 $T$ 行。对于第 $i$ 个测试用例： - 若无法满足条件，输出 `-1`； - 若可以满足条件，输出所需的最小操作次数。

### 约束条件 - $1 \leq T \leq 2 \times 10^5$ - $1 \leq N \leq 10^6$ - $T, N$ 为整数 - $A, B$ 均为仅由 `0` 和 `1` 组成的长度为 $N$ 的字符串 - 存在至少一个 $i$ 满足 $A_i = $ `1` - 存在至少一个 $i$ 满足 $B_i = $ `1` - 所有测试用例的 $N$ 之和不超过 $10^6$ ### 样例解释 1 输入包含 $3$ 个独立测试用例。对于第 $1$ 个测试用例： - 初始棋子分布为 $(0, 1, 0, 0, 1, 1, 0, 1)$ - 通过以下 $3$ 次操作可达成目标： 1. 选择 $i = 5$，分布变为 $(0, 0, 1, 0, 2, 0, 1, 0)$ 2. 选择 $i = 8$，分布变为 $(0, 0, 0, 1, 0, 2, 0, 1)$ 3. 选择 $i = 8$，分布变为 $(0, 0, 0, 0, 1, 0, 2, 1)$ - 无法在少于 $3$ 次操作内达成目标，因此输出 $3$ 对于第 $2$ 个测试用例，无论如何操作都无法满足条件，因此输出 `-1`。 翻译由 DeepSeek R1 完成