HDU 5491 The Next（技巧性模拟）

╰+攻爆jí腚メ 2022-06-08 02:58 114阅读 0赞

Let L L denote the number of 1s in integer D D’s binary representation. Given two integers S1 S1 and S2 S2, we call D D a WYH number if S1≤L≤S2 S1≤L≤S2.  
With a given D D, we would like to find the next WYH number Y Y, which is JUST larger than D D. In other words, Y Y is the smallest WYH number among the numbers larger than D D. Please write a program to solve this problem.

Input

The first line of input contains a number T T indicating the number of test cases ( T≤300000 T≤300000).  
Each test case consists of three integers D D, S1 S1, and S2 S2, as described above. It is guaranteed that 0≤D<231 0≤D<231 and D D is a WYH number.

Output

For each test case, output a single line consisting of “Case \#X: Y”. X X is the test case number starting from 1. Y 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

题解：

题意：

给你一个数x，和两个数字s1，s2，让你找出大于x的满足二进制中1的个数在s1和s2之间的数的最小值

思路：

转化成二进制以后，从右往左扫，如果1的个数小于了s1，将扫到的0变成1，如果个数大于s2，将扫到的1进位，循环到符合条件为止

代码：

#include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    #include<algorithm>
    #define ll long long
    using namespace std;
    ll a[40];
    int cmp(ll x,ll y)
    {
        return x>y;
    }
    int main()
    {
        int test,i,j,n,m,q,s1,s2,len,num,tag;
        ll d,s,x,t;
        scanf("%d",&test);
        for(q=1;q<=test;q++)
        {
            scanf("%lld%d%d",&x,&s1,&s2);
            memset(a,0,sizeof(a));
            len=0;
            num=0;
            x++;
            t=x;
            while(x>0)
            {
                a[len]=x%2;
                x/=2;
                len++;
                if(a[len-1]==1)
                    num++;
            }
            s=0,d=1;
            while(num<s1||num>s2)
            {
                while(num<s1)
                {
                    tag=0;
                    for(i=0;i<len;i++)
                    {
                        if(a[i]==0)
                        {
                            tag=1;
                            a[i]=1;
                            num++;
                            if(num>=s1)
                                break;
                        }
                    }
                    if(!tag)
                    {
                        a[len]=1;
                        num++;
                        len++;
                    }
                }
                while(num>s2)
                {
                    for(i=0;i<len;i++)
                    {
                        if(a[i])
                        {
                            a[i]=0;
                            num--;
                            j=i+1;
                            if(j==len)
                            {
                                a[j]=1;
                                len++;
                                num++;
                                break;
                            }
                            while(j<len&&a[j])
                            {
                                a[j]=0;
                                num--;
                                j++;
                            }
                            if(j==len)
                            {
                                a[j]=1;
                                num++;
                                len++;
                                break;
                            }
                            else
                            {
                                a[j]=1;
                                num++;
                            }
                            if(num<=s2)
                                break;
                        }
                    }
                }
            }
            for(i=0;i<len;i++)
            {
                s=s+d*a[i];
                d*=2;
            }
            printf("Case #%d: %lld\n",q,s);
        }
        return 0;
    }