POJ3252Round Numbers(数位dp)
2024-08-29 18:34:54
题意
给出区间$[A, B]$,求出区间内的数转成二进制后$0$比$1$多的数的个数
$1 \leqslant A, B \leqslant 2,000,000,000$
Sol
比较zz的数位dp
直接在二进制下dp就好
$f[i][ze][on]$表示第$i$位,填了$ze$个$0$,$on$个1的方案数
#include<cstdio>
#include<cstring>
#include<iostream>
// #include<map>
using namespace std;
#define LL long long
const LL MAXN = ;
LL A, B;
LL num[MAXN], tot, f[MAXN][MAXN][MAXN];
LL dfs(LL x, bool lim, LL ze, LL on) {
if(x == ) return
(ze != -) && (on != -) && (ze >= on);
if(!lim && f[x][ze][on]) return f[x][ze][on];
LL ans = ;
for(LL i = ; i <= (lim ? num[x] : ); i++) {
if(i == ) ans += dfs(x - , lim && (i == num[x]), ze == - ? : ze + , on);
else {
if(on == -) ans += dfs(x - , lim && (i == num[x]), , );
else ans += dfs(x - , lim && (i == num[x]), ze, on + );
}
}
if(!lim) f[x][ze][on] = ans;
return ans;
}
LL solve(LL x) {
tot = ;
while(x) num[++tot] = x % , x >>= ;
return dfs(tot, , -, -);
}
int main() {
cin >> A >> B;
cout << solve(B) - solve(A - );
return ;
}
/*
1234 4444
2
*/
最新文章
- MySQL索引下推技术
- Universal Link 笔记
- POJ1014 解题报告(DFS)
- linux系统的任务计划crontab使用详解
- cobbler安装、部署、测试
- VMware安装的相关文章
- git patch
- android之TextView
- 《JavaScript模式》读书笔记
- Java笔记(二十七)&hellip;&hellip;IO流中 File文件对象与Properties类
- CocoaPods导入第三方库头文件自动补齐
- HDOJ(HDU) 1465 不容易系列之一(错排)
- ThinkPHP - 自定义标签库 - 标签驱动
- Android灯光系统--深入理解背光灯
- swift -- 代理delegate
- Dell poweredge r210进BIOS改动磁盘控制器(SATA Controller)接口模式
- 【BZOJ3309】DZY Loves Math
- ETL总结(扫盲版)
- 2018-2019-2 20165234 《网络对抗技术》 Exp2 后门原理与实践
- Beta 冲刺(7/7)
热门文章
- Ubuntu Hadoop环境搭建(Hadoop2.6.5+jdk1.8.0_121)
- DCloud-HTML5+:5+ App开发入门指南
- java&;nbsp;原始类与封装类&;nbsp;的区别
- Obama&;nbsp;unveils&;nbsp;his&;amp;nbsp…
- 利用mysql客户端查询UCSC数据库
- hdu2732 Leapin&#39; Lizards (网络流dinic)
- ZOJ 2671 Cryptography 矩阵乘法+线段树
- Spring入门第二十一课
- 10. windows下原来可以这样隐藏webshell
- SQL SERVER动态列名