锐客网

  1. 首页 > it技术 > >

bzoj 3107: [cqoi2013]二进制a+b 构造

日常orzPo爷的时候看到的。感觉挺好玩的就推了一下md发现自己智商不够。
感觉举个例子真是简单易懂啊。下面的a,b,c均表示原题中a,b,c的位数：另外不妨令a 【bzoj 3107: [cqoi2013]二进制a+b 构造】1.c
0001111111
0110000011
1000000010
令f(a,b,c)表示满足c
2.a 00011110
01111111
10011101
显然位数一定>b，那么位数为b+1一定是最优的，因此只能让第二个数的b个1在最后。假设第一个数的最后一位是第k位（从低到高），那么先把第k位加入，就变成100......0010000（假设k=5），然后加入的数显然是第k~k+a-2位才能让答案最小。那么现在考虑满足c的限制，发现第三个数是这样的10......01......101......1，然后我们知道有c个1，知道最高位是b+1，然后那个单独的0的位置是第c-a+1位，就好了。
3.b 011100001
011111110
111101111
同样的显然位数>c（除非a+b=c），那么位数为c+1一定最优，于是我们要让0出现的尽可能早。注意到以第二个数为基准，第一个数的开头的1的个数就是a+b-c，那么我们让开头a+b-c全都是1即可。
4.无解情况。。。。这个还用讲吗。。。
AC代码如下：

#include #include using namespace std; int calc(int x){ int t=0; for (; x; x>>=1) t++; return t; } int getit(int x){ int t=0; for (; x; x^=x&-x) t++; return t; } int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); int len=max(max(calc(a),calc(b)),calc(c)),ans; a=getit(a); b=getit(b); c=getit(c); if (a>b) swap(a,b); if (c<=a) ans=(1<<(a+b-c))|((1<




by lych
2016.4.7
这样能让0

    推荐阅读


    上一篇：tp6框架的学习和使用

    下一篇：QT QTableView表格左上角样式