【洛谷】题解 P1633 【二进制】
dalao 都用 DP，我发一发贪心的题解。 DP 题硬生生被做成了思维题 首先，不考虑长度限制，只考虑两个数字的 1 的个数。设 A 中 1 的个数为 an a n ，B 中为 bn b n ，C 中为 cn c n 。 如果 an+bn<cn a n + b n < c n 的话，显然无解，因为 1 不可能被凭空创生而来。如果 an+bn=cn a n + b n = c n 的话，只需要不产生进位，即让两个加数的二进制表示全部错开就好。然后考虑 an+bn>cn a n + b n > c n 的情况。 在这种情况下，我们需要通过进位消掉 an+bn-cn a n + b n − c n 个 1，然后保证答案最小。 容易发现，可以简单地使用连续进位来消掉任意个数的 1： 11111 + 1 ------ 100000 消掉的 1 的个数即为第一个加数的长度。 严格来说，消掉的 1 的个数的范围为 [0,an+bn-1] [ 0 , a n + b n − 1 ] 。因为，我们可以这样子： 11111 1 + 111111 -------------- 100000000000 （空格为 0） 可行性可以保证。然后就是考虑最优性。 很显然，对于这样一组连续进位，两个加数在连续进位之前的位必须都是 0。也就是说，算式里面最多只能有一组连续进位。如果有两组连续进位，可以将这两组合并，然后偷掉一个位（全 0 位显然可以直接抠掉），这样两个加数都会变小，和也会变小。 唯一的进位处就在那个连续进位的地方。 同理，这个连续进位必须在最高位。如果不是的话，可以交换顺序使它在最高位，然后偷掉一个位。 基本框架就确定了，由于消掉的 0 的个数确定，连续进位的长度也确定了，然后只需要在这个基础上贪心地将 1 用完就好了。 在这个连续进位式骨架上，我们可以做的事情包括将一个连续进位中的改成 1，以及在后面跟单独一个 1。容易证明，最优的解就是尽量用 1 填那个进位中的空，如果还有多余的 1...
评论
发表评论