分数: 600 点
问题陈述
给出的是长度-N 字符串 S 和 T 组成 0 和 1。
您可以进行以下操作 S 任意次数:
- 选择 i (2 \leq i \leq N)这样 S_i=
1,并替换 S_i 与0。 另外,反转 S_{i-1},即改为1如果是0现在,反之亦然。
是否可以使 S 完全匹配 T? 如果可以的话,至少需要多少次手术?
约束
- 1 \leq N \leq 5 \times 10^5
- S 是一个长度为的字符串 N 组成
0和1. - T 是一个长度为的字符串 N 组成
0和1.
输入
输入由标准输入按以下格式给出:
N S T
输出
如果可以的话 S 完全匹配 T,打印所需的最少操作数。 否则,打印 -1.
示例输入 1
3 001 100
示例输出 1
2
我们可以这样做: 001 → (选择 i=3) → 010 → (选择 i=2) → 100.
示例输入 2
3 001 110
示例输出 2
-1
示例输入 3
5 10111 01010
示例输出 3
5