题意:给出l、r,求区间[l,r]内二进制中0的个数大于等于1的个数的数字有多少个.
简单的数位dp。
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=100+10;
int l,r,ans,len;
int a[maxn],dp[maxn][2*maxn][2]; void get_s(int x) { len=0; while(x) { a[++len]=x&1; x>>=1; } } int f(int pos,int cha,int now) {//2:lim 1:fir
if(!pos) return cha>=0;
if(!(now&2)&&dp[pos][cha+100][now&1]!=-1) return dp[pos][cha+100][now&1];
int p= (now&2)&&(!a[pos])? 0:1,rs=0;
for(int i=0;i<=p;++i) rs+=f(pos-1,i||(!(now&1))? cha+(!i)-i:0,now&((!i)|((i==p)<<1)));
if(!(now&2)) dp[pos][cha+100][now&1]=rs;
return rs;
} int main() {
scanf("%d%d",&l,&r);l--;
memset(dp,-1,sizeof(dp));
get_s(r);ans+=f(len,0,3);
get_s(l);ans-=f(len,0,3);
printf("%d",ans);
return 0;
}

  

最新文章

  1. C语言共用体(Union)
  2. 第三周作业--Word Counter
  3. wpf配置菜单栏
  4. 什么是linux的ftp
  5. 淘宝首页源码藏美女彩蛋(上)(UED新作2013egg)
  6. UVa 658 (Dijkstra) It&#39;s not a Bug, it&#39;s a Feature!
  7. js的引用顺序
  8. Java 实现二分(折半)插入排序
  9. 进阶之初探nodeJS
  10. vue怎么样创建组件呢??
  11. Python中str()与repr()函数的区别
  12. R语言之Apriori算法
  13. Python内置函数(22)——float
  14. 移动端适配方案-rem(基础篇)
  15. 二十九、Linux 进程与信号——minishell(2)
  16. Android 的提权(root)原理【转】
  17. windows10+Python3.6+Anaconda3+tensorflow1.10.0配置和安装
  18. ansible2.4.x RPM急速安装
  19. maven GroupId 和ArtifactId通常填什么
  20. Java 实验案例(多态)

热门文章

  1. MyBatis配置文件(四)--typeHandlers
  2. 011-python列表,元组,字典的用法
  3. 垂直对齐:vertical-align属性——使用中注意事项
  4. python-基础-面向对象2-异常-模块工厂模式
  5. 啊啊我找不到web.xml怎么办呀~~
  6. pytorch 多GPU训练过程中出现ap=0情况
  7. xshell评,xftp估过期解决办法
  8. goland设置go build的工作目录
  9. 洛谷P3300 城市规划
  10. TZ_15Spring-Cloud_Eureka-Ribbon-Hystix-Feign-Zuul微服务整合