poj3532 Round Numbers
2024-10-08 01:47:35
题意:给出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;
}
最新文章
- C语言共用体(Union)
- 第三周作业--Word Counter
- wpf配置菜单栏
- 什么是linux的ftp
- 淘宝首页源码藏美女彩蛋(上)(UED新作2013egg)
- UVa 658 (Dijkstra) It&#39;s not a Bug, it&#39;s a Feature!
- js的引用顺序
- Java 实现二分(折半)插入排序
- 进阶之初探nodeJS
- vue怎么样创建组件呢??
- Python中str()与repr()函数的区别
- R语言之Apriori算法
- Python内置函数(22)——float
- 移动端适配方案-rem(基础篇)
- 二十九、Linux 进程与信号——minishell(2)
- Android 的提权(root)原理【转】
- windows10+Python3.6+Anaconda3+tensorflow1.10.0配置和安装
- ansible2.4.x RPM急速安装
- maven GroupId 和ArtifactId通常填什么
- Java 实验案例(多态)
热门文章
- MyBatis配置文件(四)--typeHandlers
- 011-python列表,元组,字典的用法
- 垂直对齐:vertical-align属性——使用中注意事项
- python-基础-面向对象2-异常-模块工厂模式
- 啊啊我找不到web.xml怎么办呀~~
- pytorch 多GPU训练过程中出现ap=0情况
- xshell评,xftp估过期解决办法
- goland设置go build的工作目录
- 洛谷P3300 城市规划
- TZ_15Spring-Cloud_Eureka-Ribbon-Hystix-Feign-Zuul微服务整合