This message is used to verify that this feed (feedId:68119418071751680) belongs to me (userId:67570460419266560). Join me in enjoying the next generation information browser https://follow.is.
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...
评论
发表评论