锐客网

  1. 首页 > it技术 > >

BZOJ|BZOJ 3107 CQOI2013 二进制a+b 构造

题目大意：给定 n 位二进制数 a,b,c ，要求重组三个数的各个位，使得 a′+b′=c′ 且最小化 c′
一个构造题咋这么多人写DP……
不考虑位数限制，显然答案只与三个数中 1 的个数有关
令 x=cnta,y=cntb,z=cntc ，其中 cntx 代表 x 中 1 的个数
不妨令 x≥y
以下用 x=10,y=5 来举例
若 z=1 ，构造方式如下：
000001111111111
011110000000001
100000000000000
证明：显然最低位肯定是 1+1=10 ，然后再往上肯定都是单个 1 ，构造方式唯一
若 10001111111111
0110000000111
1000000000110
证明：
若最低位为 1+0=1 ，则去掉最低位后变成了 (x?1,y,z?1) 或 (x,y?1,z?1) ，二者都需要 x+y?z+1 位，算上最低位有 x+y?z+2 位，而这种构造法只需要 x+y?z+1 位，由数学归纳法可证最低位为 1+0=1 不优
那么最低位为 1+1=10 就确定了。然后……然后自己YY吧我没证出来不过应该是对的，感觉数学归纳法啥的能证
若 z=y ，构造方式如下：
01111111111
00000011111
10000011110
证明：这种构造方式保证 a′ 和 b′ 都是最小的，显然最优
若 y01111111111
00011111000
10011110111
证明：
显然 c′ 最小 x+1 位
如果想要使 c′ 减小，只能将前面的那些 0 往前挪或将最后一个 0 往前挪
显然前面那些 0 挪不动，只能将最后一个 0 往前挪(比如变成 1001101111 )
这说明最后 z?y 位必须是 1+0=1
那么去掉最后 z?y 位，问题变成了 (x+y?z,y,y)
由 y=z 的证明可得这种构造法是最优的
若 x0111111111100
0111000000011
1110111111111
证明：
显然答案至少 z+1 位，因为 z 个 1?x 个 1 一定会得到 z?x 个 1 ，
而 z?x 然后位数确定后证明就同上了
若 z=x+y ，构造方式如下：
000001111111111
111110000000000
111111111111111
证明：这个用证明么。。。
【BZOJ|BZOJ 3107 CQOI2013 二进制a+b 构造】然后……就完事了

#include #include #include #include using namespace std; int Digit(int x) { int re=0; while(x) ++re,x>>=1; return re; } int Count(int x) { int re=0; while(x) x^=x&-x,++re; return re; } int main() { //freopen("3107.in","r",stdin); //freopen("3107.out","w",stdout); int x,y,z,limit,ans; cin>>x>>y>>z; limit=max( max( Digit(x) , Digit(y) ) , Digit(z) ); x=Count(x); y=Count(y); z=Count(z); if(xlimit) ans=-1; cout

    推荐阅读


    上一篇：犹太人做生意就很会做。一个十字路口，第一个人开了一个加油站，第二个人开商店，第三个人开饭馆，第四个开别的。中国人在一个路口开了一家饭店，别人看赚了钱，其他人一下子就在这里开

    下一篇：数值|数值 Python —— 常微分方程-（转）