#题目描述
输入三个整数a, b, c,把它们写成无前导0的二进制整数。比如a=7, b=6, c=9,写成二进制为a=111, b=110, c=1001。接下来以位数最多的为基准,其他整数在前面添加前导0,使得a, b, c拥有相同的位数。比如在刚才的例子中,添加完前导0后为a=0111
, b=0110
, c=1001
。最后,把a, b, c的各位进行重排,得到a’, b’, c’,使得a’+b’=c’。比如在刚才的例子中,可以这样重排:a’=0111
, b’=0011
, c’=1010
。
你的任务是让c’最小。如果无解,输出-1。
#做法
暴力搞搞即可
记\(f_{bit,i,j,k,flag}\)表示当前是第\(bit\)位,a用了\(i\)个1
,b用了\(j\)个1
,c用了\(k\)个1
,用\(flag\)表示是否进位
状态转移的话,看代码。。。
#复杂度分析 \(O((\log a)^4)\)
#AC Code