设一个 01 串的美丽值为相同的相邻数字个数。举个例子,00011
的美丽值为 3,而 10101
的美丽值为 0。
设两个长度相同,且 0 的个数相同的 01 串 s1,s2 之间的距离 dis(s1,s2) 为仅能交换相邻字符,使得 s1 变成 s2 的最小交换次数。
如果一个字符串 s3 满足它在 s1,s2 中间,则需要 dis(s1,s2)=dis(s1,s3)+dis(s3,s2)。
现在,给定两个长度为 n+m 的,有 n 个 0 的字符串 s,t,请求出所有 s,t 中间的字符串中,最大的美丽值。
2≤n+m≤3×105。