POJ 3252 Round Numbers (区间DP,基础)
2024-10-21 11:50:14
题意:
统计区间[L,R]有多少个数,其二进制表示法中的0的个数不少于1的个数?(不允许前缀0)
思路:
状态表示为 [当前第几位][总位数][1的个数],最后判断一下1的个数是否满足条件,要注意前导0的问题,可以通过枚举二进制的位数来解决。
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define INF 0x7f3f3f3f
#define LL long long
#define ULL unsigned long long
using namespace std;
const double PI = acos(-1.0);
const int N=; int f[N][N][N], bit[N];
//[当前第几位][总位数][1的个数]
int dfs(int i,int up,int cnt,bool e)
{
if(i==) return cnt*<=up;
if(!e && ~f[i][up][cnt]) return f[i][up][cnt];
if(cnt*>up) return ; int ans=;
int d= i==up?:;
int u= e? bit[i]: ;
for( ; d<=u; d++)
{
ans+=dfs(i-,up,cnt+d,e&&d==u);
}
return e? ans: f[i][up][cnt]=ans;
} int cal(int n)
{
if(n<=) return ;
int len=;
while(n) //拆数
{
bit[++len]=(n&);
n>>=;
}
int ans=;
for(int i=; i<len; i++) ans+=dfs(i,i,,false);
ans+=dfs(len,len,,true);
return ans;
} int main()
{
//freopen("input.txt","r",stdin);
memset(f, -, sizeof(f));
int a, b;
scanf("%d%d",&a,&b);
printf("%d\n",cal(b)-cal(a-) ); return ;
}
AC代码
最新文章
- mac 下 chrome 语言环境 设置
- 编写高质量iOS代码与OS X代码的effective 方法小结
- Xcode好用的插件
- typedef和#define的区别
- [Javascript] JavaScript Array Methods in Depth - push
- (原)torch7中添加新的层
- Linux内核学习趣谈
- JS 获取上传文件的内容
- 安卓TextView完美展示html格式代码
- 008_tcp探测
- 【Flask-RESTPlus系列】Part1:快速入门
- array_walk函数与call_user_func_array函数
- 【经典】5种IO模型 | IO多路复用
- Docker中使用createdump调试coreclr
- php里单引和双引的用法区别和连接符(.)
- nginx 反向代理到目录
- hdfs遍历文件方法
- 理解面向消息中间件及JMS 以及 ActiveMQ例子
- LabVIEW之生产者/消费者模式--队列操作
- SQL多行并一行统计例子之STUFF()函数+FOR XML PATH()函数应用
热门文章
- React库protypes属性
- Struts&;nbsp;result&;nbsp;param详细设置
- 《精通Spring4.X企业应用开发实战》读后感第二章
- ASP.NET Core会议管理平台实战_4、参数校验、操作结果封装,注册参数配置
- Do not have XXX handler in current page
- java面试一定会遇到的56个面试题
- SqlHelper 增删改查
- IntelliJ IDEA 安装golang 插件
- python接口自动化(三十九)- logger 日志 - 上(超详解)
- Java 多线程高并发编程 笔记(二)