分数: 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和 m1s。
输入
输入由标准输入按以下格式给出:
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