首页 > 代码库 > hdu-5491 The Next(贪心)

hdu-5491 The Next(贪心)

2024-08-16 11:14:05   217人阅读

题目链接：

The Next

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1766    Accepted Submission(s): 669


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
 
题意：
 
给一个D,现在让求最小的ans>D,且ans的二进制中1的个数是[s1,s2];
 
思路：
 
套路题,从高位到低位按位贪心,对于当前位,如果为1,那么这一位就一定要取1,然后d,s1,s2都变小了;
如果当前位为0,那么就要看取最多个数的1能得到的数如果大于当前的数,那么还可以取0;
否则就要取1了;就这样贪心,具体的可以看代码;
 
AC代码：
#include <bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1e5+10;int l,r;LL d,ans,dp[40];void dfs(LL cur,int hi,int lo,int pos){    if(hi<=0||pos<0)return ;    if(cur>=dp[pos]){ans+=dp[pos],dfs(cur-dp[pos],hi-1,lo-1,pos-1);}    else     {        if(lo==pos+1)        {            ans+=dp[lo]-1;            return ;        }        else         {            LL num=0;            for(int i=pos-1;i>=max(0,pos-hi);i--)num+=dp[i];            if(num>cur)dfs(cur,hi,lo,pos-1);            else             {                ans+=dp[pos];                lo--;                if(lo>0)ans+=dp[lo]-1;                return ;            }        }    }}int main(){    int t,Case=0;    scanf("%d",&t);    dp[0]=1;    for(int i=1;i<=33;i++)dp[i]=dp[i-1]*2;    while(t--)    {        scanf("%lld%d%d",&d,&l,&r);        ans=0;        dfs(d,r,l,32);        if(d==0)        {            if(l==0)ans=1;            else ans=dp[l]-1;        }        printf("Case #%d: %lld\n",++Case,ans);    }    return 0;}

　　

 

hdu-5491 The Next(贪心)


联系
我们