hdu-5491 The Next(贪心)

时间:2022-08-30 12:59:11

题目链接:

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(贪心)的更多相关文章

  1. HDU 4442 Physical Examination&lpar;贪心&rpar;

    HDU 4442 Physical Examination(贪心) 题目链接http://acm.split.hdu.edu.cn/showproblem.php?pid=4442 Descripti ...

  2. 【贪心】【模拟】HDU 5491 The Next &lpar;2015 ACM&sol;ICPC Asia Regional Hefei Online&rpar;

    题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5491 题目大意: 一个数D(0<=D<231),求比D大的第一个满足:二进制下1个个数在 ...

  3. hdu 5491 The Next (位运算)

    http://acm.hdu.edu.cn/showproblem.php?pid=5491 题目大意:给定一个数D,它的二进制数中1的个数为L,求比D大的数的最小值x且x的二进制数中1的个数num满 ...

  4. HDU 5835 Danganronpa (贪心)

    Danganronpa 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5835 Description Chisa Yukizome works as ...

  5. HDU 5821 Ball (贪心)

    Ball 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5821 Description ZZX has a sequence of boxes nu ...

  6. hdu 5491&lpar;2015合肥网赛&rpar;The Next

    题目;http://acm.hdu.edu.cn/showproblem.php?pid=5491 题意就是,T组测试数据.然后L,S1,S2.L的二进制中有x个1,x满足  S1<=x< ...

  7. hdu 4004 &lpar;二分加贪心&rpar; 青蛙过河

    题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4004 题目意思是青蛙要过河,现在给你河的宽度,河中石头的个数(青蛙要从石头上跳过河,这些石头都是在垂 ...

  8. Saving HDU(hdu2111,贪心)

    Saving HDU Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total ...

  9. HDU 4714 Tree2cycle:贪心

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4714 题意: 给你一棵树,添加和删除一条边的代价都是1.问你将这棵树变成一个环的最小代价. 题解: 贪 ...

  10. HDU 5303 Delicious Apples &lpar;贪心 枚举 好题&rpar;

    Delicious Apples Time Limit: 5000/3000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Other ...

随机推荐

  1. spring MVC &commat;Resource不支持Lazy加载

    今天迁一系统时发现有个bean使用@Resource注入了另外一个bean,这个被注入的bean是将被deprecated的类,而且只有一两个功能使用到,为了先调整进行测试,增加了@Lazy注解,启动 ...

  2. &lt&semi;实训&vert;第十天&gt&semi;从底层解释一下U盘内存为什么变小的原因附数据恢复的基本原理

    [root@localhost~]#序言 我们平时不论是买一个U盘硬盘,或者自己在电脑上创建一个分区,大小总是比我们创建的要小一点,有些人会说,这个正常啊,是因为厂家规定的1M=1000k,真正的是1 ...

  3. 下载image或者其他文件

    public void SaveDownLoadAsPNG(Image img, string filePath) { try { WebRequest request = WebRequest.Cr ...

  4. js——cookie

    cookie:存储数据,当用户访问了某个网站(网页)的时候,我们就可以通过cookie来向访问者电脑上存储数据 1.不同的浏览器存放的cookie位置不一样,也是不能通用的 2. cookie的存储是 ...

  5. Java 8 特性 —— Stream

    Stream 是用函数式编程方式在集合类上进行复杂操作的工具,其集成了Java 8 中的众多新特性之一的聚合操作,开发者可以更容易地使用Lambda表达式,并且更方便地实现对集合的查找.遍历.过滤以及 ...

  6. &lbrack;Swift&rsqb;LeetCode971&period;翻转二叉树以匹配先序遍历 &vert; Flip Binary Tree To Match Preorder Traversal

    Given a binary tree with N nodes, each node has a different value from {1, ..., N}. A node in this b ...

  7. Python基础训练题-简单数学公式

    1.在100内,将遇到被7除余数为0的都显示PASS: n=1 while n < 101: if n % 7 == 0: pass print('pass') else: print(n) n ...

  8. Oracle12c从入门到精通(第二版) PDF 下载

    一:下载地址: 二:本书图样 三本书目录 前言 第一章 Oracle数据库概述 第二章 Oracle在Windows 8上的安装与配置 第三章 SQL基础 第四章 Oracle PL/SQL及编程 第 ...

  9. 批量增删改&quot&semi;&lowbar;bulk&quot&semi;

    除了delete以外,每个操作需要两个json字符串,语法如下:{"action":{"metadata"}}{"data"}bulk ap ...

  10. Python 全栈开发十 socket网络编程

    一.客户端(client)服务端(sever)架构 在计算机中有很多常见的C/S架构,例如我们的浏览器是客户端.而百度网站和其他的网站就是服务端:视频软件是客户端,提供视频的腾讯.优酷.爱奇艺就是服务 ...