锐客网

  1. 首页 > it技术 > >

构造|[bzoj3107][CQOI2013]二进制a+b

题目大意及模型转换 给定三个二进制数a,b,c。对每个数进行重组变为a’,b’,c’。你需要满足a’+b’=c’，并令c’最小。若无解输出-1。
a,b,c<= 231 。
考虑简化 其实，我们发现有用的东西只是a,b,c的最大位数（决定了答案最多可以多少位，注意这里的位数是十进制下的，那么最小的答案都超过极限位数证明输出-1），以及a,b,c中1的个数（记为x,y,z）。为方便讨论，我们应当规定x>=y。
分类讨论 现在我们考虑这样一个子问题。
设为 solve(x,y,z,p) 表示第一个数有x个1，第二个数有y个1，得到的数需要有z个1，其中最低位相加时要加上进位的p=0..1。
z=1很显然了，举个例子x=10,y=5,z=1。
当p=0时：
000001111111111
011110000000001
100000000000000
最优策略是把x个1都堆在后面，最低位放1，然后接下来再放y-1个1，使得c’最高位为1。
所以 solve(x,y,z,0)=2x+y?1
当p=1时：
0000001111111111
0111110000000000
1000000000000000
最优策略是把x个1都堆在后面，但因为有进位，所以最低位不能放1，然后再往前放y个1，同样令c’最高位为1。
所以 solve(x,y,z,1)=2x+y
所以 solve(x,y,z,p)=2x+y?1+p
z=y设x=10,y=5,z=5。
当p=0时：
01111111111
00000011111
10000011110
显然这种情况保证a’,b’最小会最优。因为a’，b’最小时刚好c’有y个1，所以合法。又因为a’,b’最小，所以c’也最小。
所以 solve(x,y,z,0)=2x+2y?2
当p=1时：
001111111111
010000011110
100000011110
这种情况我们只能把b’最低位变成0，然后在第x+1位补上一个1，使得c’的最高位的1落在第x+2位。
所以 solve(x,y,z,1)=2x+1+2y?1?1
所以 solve(x,y,z,p)=2x+p+2y?p?2+p
1 有点不好搞。我们来看看最低位应该怎么弄，然后可以继续将它分成下一个子问题。先考虑p=0。
如果最低位是1+0=1，那么下一个子问题将会变为 solve(x?1,y,z?1,0) 。
按照策略会继续减，一直到z=1时。
那么答案自然是 2x+y?z?2z?1+2z?1?1
如果最低位是0+1=1，那么下一个子问题将会变为 solve(x,y?1,z?1,0)
按照策略已知道z=1。
那么答案自然是 2x+y?z?2z?1+2z?1?1
两种一样，我们合并。
如果最低位是1+1=0，那么下一个子问题将会变为 solve(x?1,y?1,z,0)
按照策略会一直到y=z时。
那么答案自然是 2x?y+z?2z?1+2z?2z?1?2?2z?1
我们进行比较。
第一、二种策略： 2z?1?(2x+y?z+1)?1
第三种策略： 2z?1?(2x?y+z+2z?2)
由于我们知道y>z。那么显然第三种策略更优。
p=1可以研究一下，还是1+1最优。
因此可以得知。
solve(x,y,z,p)=2?solve(x?1,y?1,z?p,1)+p
y01111111111
00011111000
10011110111
这种情况不需要管进位。
因为初始状态p=0，而这种情况只有初始情况才会出现。
在c’中如果它的1跑的比较后面，它就会比较小。
因此最后z-y位都应该是1+0=1。
直至缩到y=z。
所以 solve(x,y,z,p)=2z?y?solve(x+y?z,y,y,0)+2z?y?1
x0111111111100
0111000000011
1110111111111
这种情况同样不需要理进位。
同样我们使c’的1弄到后面去。
因此最后z-x位都应该是0+1=1。
所以 solve(x,y,z,p)=2z?x?solve(x,y+x?z,x,0)+2z?x?1
z=x+y不需要理进位。
x=10,y=5,z=15,p=0。
000001111111111
111110000000000
111111111111111
显然可得。
solve(x,y,z,p)=2x+y
不是以上情况中任意一种 solve(x,y,z,p)=-1
注意 最终得到的答案应该和最大位比较。
参考代码 【构造|[bzoj3107][CQOI2013]二进制a+b】（写的很优美呢）

#include #include #include #define fo(i,a,b) for(i=a; i<=b; i++) #define two(x) (1<1&&zy&&z<=x) return two(z-y)*solve(x+y-z,y,y,0)+two(z-y)-1; else if (z>x&&zn) ans=-1; printf("%d\n",ans); }

    推荐阅读


    上一篇：一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半，都要花费20个铜板。一群人想整分整块金条，怎么分最省铜板。

    下一篇：我不是药神的精神