分数: 500 点
问题陈述
电子公告板显示一条字符串 S 长度 N 组成 0 和 1.
您可以多次执行以下操作,其中 S_i 表示 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,并在可能的情况下找到所需的最少操作数。
约束
- 2 \leq N \leq 500000
- S 是一个长度为 N 组成
0和1. - T 是一个长度为 N 组成
0和1.
输入
输入由标准输入按以下格式给出:
N S T
输出
如果无法让面板显示字符串 T,打印 -1.
如果可能,求所需的最少操作数。
示例输入 1
7 1110110 1010111
示例输出 1
2
这是使面板显示字符串的一种可能方法 1010111 在两个操作中:
- 进行操作 (l, r) = (2, 4),将板上的字符串从
1110110to1011110. - 进行操作 (l, r) = (4, 7),将板上的字符串从
1011110to1010111.
示例输入 2
20 11111000000000011111 11111000000000011111
示例输出 2
0
面板已显示字符串 T 在进行任何操作之前,所以答案是 0.
示例输入 3
6 111100 111000
示例输出 3
-1
如果没有使面板显示字符串的操作序列 T,打印 -1.
示例输入 4
119 10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011 11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011
示例输出 4
22