← 返回题目列表

AtCoder · arc132_d

D. 两个二进制字符串之间

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

分数: 700 点

问题陈述

让我们定义 美女 长度为 $$$m$$$(其中 $$$m \ge 2$$$)的数组 $$$b$$$ 的 作为两个相邻字符相同的位置数。 例如,美丽 00011 is 3,以及美丽 10101 is 0.

让 S_{n,m} 是所有长度为的字符串的集合 n+m 组成 n 0和 m 1s。

对于 s_1,s_2 \in S_{n,m},让我们定义 距离 of s_1 和 s_2, d(s_1,s_2),作为重新排列字符串时所需的最小交换次数 s_1 to s_2 通过交换两个相邻字符。

此外,对于 s_1,s_2,s_3\in S_{n,m}, s_2 据说是 之间 s_1 和 s_3 当 d(s_1,s_3)=d(s_1,s_2)+d(s_2,s_3).

鉴于 s,t\in S_{n,m},打印字符串之间最大的美 s 和 t.

约束

  • 2 \le n + m\le 3\times 10^5
  • 0 \le n,m
  • 每个 s 和 t 是一个长度为 n+m 组成 n 0和 m 1s。

输入

输入由标准输入按以下格式给出:

n m
s
t

输出

打印字符串之间的最大美 s 和 t.


示例输入 1

2 3
10110
01101

示例输出 1

2

之间 10110 和 01101,其距离为 2,我们有以下字符串: 10110, 01110, 01101, 10101。 她们的美貌是 1, 2, 1, 0分别,所以答案是 2.


示例输入 2

4 2
000011
110000

示例输出 2

4

之间 000011 和 110000,其距离为 8,最美的琴弦是 000011 和 110000,所以答案是 4.


示例输入 3

12 26
01110111101110111101001101111010110110
10011110111011011001111011111101001110

示例输出 3

22