← 返回题目列表

AtCoder · arc119_b

B. 电板

中文机器翻译题面 查看原题

分数: 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),将板上的字符串从 1110110 to 1011110.
  • 进行操作 (l, r) = (4, 7),将板上的字符串从 1011110 to 1010111.

示例输入 2

20
11111000000000011111
11111000000000011111

示例输出 2

0

面板已显示字符串 T 在进行任何操作之前,所以答案是 0.


示例输入 3

6
111100
111000

示例输出 3

-1

如果没有使面板显示字符串的操作序列 T,打印 -1.


示例输入 4

119
10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011
11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011

示例输出 4

22