题解：P15951 [ICPC 2018 Jakarta R] Edit Distance

· · 题解

先统计目标串里字符 0 与 1 的出现频次，再分三类情况构造答案串即可。

核心

一、

若串中 1 的总数比 0 更少，直接构造全 1 字符串。由于原串内 0 占比过半，全 1 会在所有 0 所在位置形成字符差异，最终编辑距离必然超过原串长度的一半。

二、

若串中 0 的数量少于 1，则统一输出全 0 序列。此时原串里多数位置都是 1，全 0 会和大量位置产生不同字符，轻松满足编辑距离大于半数长度的要求。

三、

当 0 和 1 数量完全一致时，先取与原串首位相反的字符作为答案首字符，再剔除原串第一位，重新统计剩余子串中两类字符的数量，后续整段统一填充数量更少的那类字符。

该做法下，除去首位强制不同外，剩余所有位置也能全部错位不匹配，整体编辑距离等于字符串总长度，完全满足大于一半长度的限制条件。