POJ3252Round Numbers(数位dp)
2018-09-18 06:25:02来源:博客园 阅读 ()
题意
给出区间$[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 = 101; LL A, B; LL num[MAXN], tot, f[MAXN][MAXN][MAXN]; LL dfs(LL x, bool lim, LL ze, LL on) { if(x == 0) return (ze != -1) && (on != -1) && (ze >= on); if(!lim && f[x][ze][on]) return f[x][ze][on]; LL ans = 0; for(LL i = 0; i <= (lim ? num[x] : 1); i++) { if(i == 0) ans += dfs(x - 1, lim && (i == num[x]), ze == -1 ? 1 : ze + 1, on); else { if(on == -1) ans += dfs(x - 1, lim && (i == num[x]), 0, 1); else ans += dfs(x - 1, lim && (i == num[x]), ze, on + 1); } } if(!lim) f[x][ze][on] = ans; return ans; } LL solve(LL x) { tot = 0; while(x) num[++tot] = x % 2, x >>= 1; return dfs(tot, 1, -1, -1); } int main() { cin >> A >> B; cout << solve(B) - solve(A - 1); return 0; } /* 1234 4444 2 */
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:洛谷P2062 分队问题(dp)
下一篇:BZOJ2244 拦截导弹
- 数位dp踩坑 2019-08-26
- 数位dp 2019-08-26
- bzoj3209: 花神的数论题(数位DP) 2019-08-16
- bzoj1799: [Ahoi2009]self 同类分布(数位DP) 2019-08-16
- Add Two Numbers 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash