题意:

  统计区间[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代码

最新文章

  1. mac 下 chrome 语言环境 设置
  2. 编写高质量iOS代码与OS X代码的effective 方法小结
  3. Xcode好用的插件
  4. typedef和#define的区别
  5. [Javascript] JavaScript Array Methods in Depth - push
  6. (原)torch7中添加新的层
  7. Linux内核学习趣谈
  8. JS 获取上传文件的内容
  9. 安卓TextView完美展示html格式代码
  10. 008_tcp探测
  11. 【Flask-RESTPlus系列】Part1:快速入门
  12. array_walk函数与call_user_func_array函数
  13. 【经典】5种IO模型 | IO多路复用
  14. Docker中使用createdump调试coreclr
  15. php里单引和双引的用法区别和连接符(.)
  16. nginx 反向代理到目录
  17. hdfs遍历文件方法
  18. 理解面向消息中间件及JMS 以及 ActiveMQ例子
  19. LabVIEW之生产者/消费者模式--队列操作
  20. SQL多行并一行统计例子之STUFF()函数+FOR XML PATH()函数应用

热门文章

  1. React库protypes属性
  2. Struts&amp;nbsp;result&amp;nbsp;param详细设置
  3. 《精通Spring4.X企业应用开发实战》读后感第二章
  4. ASP.NET Core会议管理平台实战_4、参数校验、操作结果封装,注册参数配置
  5. Do not have XXX handler in current page
  6. java面试一定会遇到的56个面试题
  7. SqlHelper 增删改查
  8. IntelliJ IDEA 安装golang 插件
  9. python接口自动化(三十九)- logger 日志 - 上(超详解)
  10. Java 多线程高并发编程 笔记(二)