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，如果不满足，那么有两种情况，第一种是二进制后的1的个数小于s1,那么我们只要从右往左找第一个0，使得其变为1(即加上2^i)，如果二进制后的1的个数大于s1,那么我们只要从右往左找第一个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\n",num1,n);

    }

    return 0;

}

巴特西

hdu5491 The Next

最新文章

热门文章