hdu5491 The Next

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 740    Accepted Submission(s): 294
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≤300000 ).
Each test case consists of three integers 
D , 
S1 , and 
S2 , as described above. It is guaranteed that 
0≤D<231  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 1. 
Y  is the next WYH number.
 
Sample Input

   
   
   
   

    
    
    
    3
11 2 4
22 3 3
15 2 5
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    Case #1: 12
Case #2: 25
Case #3: 17
   
   
   
   

 
Source
2015 ACM/ICPC Asia Regional Hefei Online
この問題は自分では考えられなかったが、試合の時はチームメートがやったので、後でやり方を知った.まずDプラス1をmにして、mが条件を満たしているかどうかを判断し、満足していなければmを直接出力し、満足していなければ、2つの場合があります.1つ目はバイナリ後の1の個数がs 1より小さい場合、右から左へ1つ目の0を探して、それを1にします(つまり2^iを加えます)、2つ目の後の1の個数がs 1より大きい場合、私たちは右から左へ1つ目の1を探します.そして(2^i)を付けて0にして、続けます.
この方法が実行可能なのは,毎回変化を最小限に抑えるため,得られた値は必ず成立中最小である.

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
#define ll long long
#define inf 0x7fffffff
int main()
{
    ll n,m,i,j,T,t1,t2,wei,num1=0,num;
    int a[40];
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld%lld",&n,&t1,&t2);
        n++;
        while(1){
            m=n;
            wei=0;num=0;
            while(m){
                a[++wei]=m%2;
                if(m%2==1)num++;
                m/=2;
            }
            if(num<t1){
               for(i=1;i<=wei;i++){
                    if(a[i]==0){
                        j=i;break;
                    }
               }
               n+=(1<<(j-1));
            }
            else if(num>t2){
                for(i=1;i<=wei;i++){
                    if(a[i]==1){
                        j=i;break;
                    }
                }
                n+=(1<<(j-1) );

            }
            else break;
        }
        num1++;
        printf("Case #%lld: %lld
",num1,n);

    }
    return 0;
}