题意
给定一个长度为 \(n + m\) 的二进制数，你需要将这个二进制数划分别划分为长度为 \(n\) 的二进制数 \(a\) 与长度为 \(m\) 的二进制数 \(b\)。
你需要输出 \(a + b\) 的二进制形式。
\(n \le 10 ^ 6\)。
Sol
考虑发现一些性质。
设 \(n \ge m\)，则：
考虑最优方案给 \(a\) 与 \(b\) 添加字符的过程，注意到一定存在一种最优方案，可以使得在 \(b\) 被填完之前，\(a\) 不会被填任何一个 \(0\)。
证明如下，由于可以交换 \(a\) 与 \(b\) 的任意位，所以我们可以认为在过程中 \(n - |a| \le m - |b|\)，于是可以发现给 \(a\) 一直填 \(1\) 遇到 \(0\) 就给 \(b\)，才会最优。
我们可以考虑设 \(i\) 表示给 \(a\) 分配 \([1, i]\) 中的 \(i - m\) 个 \(1\)，剩下的分配给 \(b\)，最后接上一段。
这样时间复杂度来到了 \((n + m) ^ 2\)。
平凡的，考虑 \(i + 1\) 对最终答案的贡献。
不难发现当 \(s_{i + 1} = 1\) 时对答案无贡献，当 \(s_{i + 1} = 0\) 时，会去掉 \(b\) 的最后一位 \(1\)，给 \(a\) 的最后加上一个 \(1\)。
可以发现这两个递增递减操作会有交叉，直接找到这个交叉点即可。
时间复杂度：\(O(n + m)\)。
标签：20240708,省选,复杂度,partition,二进制,划分,le,最优 From： https://www.cnblogs.com/cxqghzj/p/18306175