Problem Description Let L denote the number of 1s in integer D’s binary representation. Given two integers S1 and S2, we call D a WYH number if S1≤L≤S2.
With a given D, we would like to find the next WYH number Y, which is JUST larger than D. In other words, Y is the smallest WYH number among the numbers larger than D. Please write a program to solve this problem. Input The first line of input contains a number T indicating the number of test cases (T≤).
Each test case consists of three integers D, S1, and S2, as described above. It is guaranteed that ≤D< and D is a WYH number. Output For each test case, output a single line consisting of “Case #X: Y”. X is the test case number starting from . Y is the next WYH number. Sample Input Sample Output Case #:
Case #:
Case #: Source ACM/ICPC Asia Regional Hefei Online
这道题在比赛的时候我就是用的这个方法，但是一直超时。后来重新写了一遍，用了G++过了。
思路：
从小到大找必定超，我看限制条件一的个数是0~32差不多，这么个循环是不会超时的。我就从i->s1~s2循环，里面找一的个数为i的。
这里因为要i个1，然后又要比L大那么把第i个1前移一位。
下面这里分两个情况：
以需要3个1为例
①11011->11100
②10111->11001如果进位了，就在末尾补1.
还有一种情况就是找不到第i个1：就从后往前变0为1，直到满足i个1.
然后去每种1个数的最小值。
证明正确性：
试想要i个1那么不够的话还要比他大是不是往后补就行，因为1放在越后面越小。
要是够，因为要比他大，这里可知1的个数比需要的多。我们就要删掉1，那么删哪些呢？到第i个1为止，你后面在怎么变①后面1变少，数值变小，不行②1变多，我们现在要删掉1，不行；
所以后面的都不行，那么第i个1要进位了。然后进位完，1不够了，最小就往最后面补。
#include<stdio.h>
int main()
{
int T,s1,s2;
__int64 L,p;
int cas=; scanf("%d",&T);
while(T--)
{
scanf("%I64d%d%d",&L,&s1,&s2);
p=(__int64)<<; if(L==&&s1==&&s2==){
printf("Case #%d: 0\n",++cas);
continue;
}
int flag=;
__int64 t;
for(int i=s1;i<=s2;i++)
{
int s=,f=;
t=(__int64);
for(int j=;j>=;j--)
{
if(L&((__int64)<<j))s++;
if(s==i)
{
int z,k;
for(k=j;k<=;k++)
{if(L&((__int64)<<k));
else {
t|=(__int64)<<k;
break;
}
} z=;
for(int kk=k+;kk<=;kk++)
{
if(L&((__int64)<<kk))t|=(__int64)<<kk,z++;
}
z=i-z;
for(k=;k<=&&z>;k++)t|=(__int64)<<k,z--;
p=p>t?t:p; f=;
break;
}
}
if(!f)
{
s=i-s;
t=L;
for(int k=;k<=&&s>;k++){
if(L&((__int64)<<k));
else t|=(__int64)<<k,s--;
}
p=p>t?t:p; } }
printf("Case #%d: %I64d\n",++cas,p);
}
}