#arc132d. [arc132_d]Between Two Binary Strings

[arc132_d]Between Two Binary Strings

设一个 01 串的美丽值为相同的相邻数字个数。举个例子,00011 的美丽值为 3,而 10101 的美丽值为 0。

设两个长度相同,且 0 的个数相同的 01 串 s1,s2s_1,s_2 之间的距离 dis(s1,s2)dis(s_1,s_2) 为仅能交换相邻字符,使得 s1s_1 变成 s2s_2 的最小交换次数。

如果一个字符串 s3s_3 满足它在 s1,s2s_1,s_2 中间,则需要 dis(s1,s2)=dis(s1,s3)+dis(s3,s2)dis(s_1,s_2)=dis(s_1,s_3)+dis(s_3,s_2)

现在,给定两个长度为 n+mn+m 的,有 nn 个 0 的字符串 s,ts,t,请求出所有 s,ts,t 中间的字符串中,最大的美丽值。

2n+m3×1052\le n+m\le 3\times 10^5