You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

现在，电光显示屏上显示着一个由 0 和 1 组成的长度为 $N$ 的字符串 $S$。

你可以进行任意次数如下操作。这里，电光显示屏上字符串的第 $i$ 个字符记作 $S_i$（$1 \leq i \leq N$）。

操作 选择一组整数 $(l, r)$（$1 \leq l < r \leq N$），并满足以下两个条件之一，然后交换 $S_l$ 和 $S_r$：

• $S_l =$ 0 且 $S_{l+1} = \cdots = S_r =$ 1。
• $S_l = \cdots = S_{r-1} =$ 1 且 $S_r =$ 0。

请判断能否通过若干次操作将显示屏上的字符串变为 $T$，如果可以，输出所需操作次数的最小值；如果不可以，输出 $-1$。

输入格式

输入以如下格式从标准输入给出：

$N$ $S$ $T$

输出格式

如果无法将显示屏上的字符串变为 $T$，请输出 $-1$。

如果可以，请输出所需操作次数的最小值。

输入输出样例 #1

输入 #1

7
1110110
1010111

输出 #1

2

输入输出样例 #2

输入 #2

20
11111000000000011111
11111000000000011111

输出 #2

0

输入输出样例 #3

输入 #3

6
111100
111000

输出 #3

-1

输入输出样例 #4

输入 #4

119
10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011
11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011

输出 #4

22

说明/提示

限制条件

• $2 \leq N \leq 500000$
• $S$ 是由 0 和 1 组成的长度为 $N$ 的字符串
• $T$ 是由 0 和 1 组成的长度为 $N$ 的字符串

样例解释 1

例如，可以如下进行操作，在 $2$ 次操作后将显示屏上的字符串变为 1010111。

• 选择 $(l, r) = (2, 4)$ 进行操作。此时，显示屏上的字符串由 1110110 变为 1011110。
• 选择 $(l, r) = (4, 7)$ 进行操作。此时，显示屏上的字符串由 1011110 变为 1010111。

样例解释 2

在进行任何操作之前，显示屏上的字符串已经是 $T$，因此答案为 $0$。

样例解释 3

无论如何操作，都无法将显示屏上的字符串变为 $T$，此时请输出 $-1$。

由 ChatGPT 4.1 翻译