【链接】click here~~
【题意】：
），保证D的二进制中1的数量在s1和s2之间
然后让你求一个最小的数，使得这个数的二进制数量大于等于s1，小于等于s2，且大于 d
【思路】虽然是比赛时候的一道水题，但是开始看到的时候并没有想到好的思路，最后还是学弟强行过掉，今天突然想到了可以用lowbit来求
首先看到D的范围是很大的，，那么如何构造呢？
这里举个例子：比如11，二进制表示（1011），取11+1=12，二进制表示（1100）s1=2,那么我们要做的就是考虑构造数的范围，如果当前数的s1 小于左区间的值，我们要做的就是从最后一个0出现的位置添加1，也就是从右到左，我们发现对12取按位反后得到(0011)，取一次lowbit得到从右往左第一个1的位置是1，那么我们就把12+1=13（1101），相当于12的十进制加一，也等于12的二进制多添了一个1，这样是构造小于左区间的，那么如果大于左区间，又要满足条件，即取大于D的最小值，不难发现，只要加上lowbit(d)即可
代码：
/* * Problem: HDU No.5491* Running time: 499MS * Complier: G++ * Author: javaherongwei * Create Time: 8:47 2015/9/28 星期一*/ #include <bits/stdc++.h>using namespace std;typedef long long LL;inline LL read(){int c=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}return c*f;}LL bitwei(LL x){LL s=0;while(x){if(x%2) s++;x/=2;}return s;}LL bitwei2(LL x){x = (x&0x55555555) + ((x>>1) & 0x55555555);x = (x&0x33333333) + ((x>>2) & 0x33333333);x = (x&0x0F0F0F0F) + ((x>>4) & 0x0F0F0F0F);x = (x&0x00FF00FF) + ((x>>8) & 0x00FF00FF);x = (x&0x0000FFFF) + ((x>>16) & 0x0000FFFF);return x;}LL lowbit(LL x){return x&(-x);}int main(){int t,tot=1;t=read();while(t–){LL d,s1,s2;d=read();s1=read();s2=read();d++;LL len=bitwei2(d);while(!(len>=s1&&len<=s2)){if(len<s1) d+=lowbit(~d);else d+=lowbit(d);len=bitwei2(d);}printf("Case #%d: ",tot++);printf("%lld\n",d);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
把自己当傻瓜，不懂就问，你会学的更多
