【YBTOJ】【Luogu P6218】[USACO06NOV] Round Numbers S
2021/7/11 23:17:38
本文主要是介绍【YBTOJ】【Luogu P6218】[USACO06NOV] Round Numbers S,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
【YBTOJ】【Luogu P6218】[USACO06NOV] Round Numbers S
链接:
洛谷
题目大意:
在 \([l,r]\) 中找到二进制中零数大于等于一数的数的个数。
正文:
数位 DP 板子题。设 \(f_{len,A,B,pos}\) 表示当前 \(len\) 位 \(A\) 个零、\(B\) 个一,碰没碰顶的方案数。
代码:
const int N = 60; inline ll Read() { ll x = 0, f = 1; char c = getchar(); while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') f = -f, c = getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar(); return x * f; } ll l, r; int a[N], Len; ll f[N][N][N][2]; ll DP (int len, int A, int B, bool pos) { if (~f[len][A][B][pos]) return f[len][A][B][pos]; if (!len) return A >= B; int m = pos? a[len]: 1; ll ans = 0; for (int i = 0; i <= m; i++) ans += DP(len - 1, (B > 0) * (A + (i == 0)), B + (i == 1), pos && i == m); return f[len][A][B][pos] = ans; } ll Solve (ll n) { if (!n) return 1; Len = 0; memset (a, 0, sizeof a); for (ll m = n; m; m /= 2) a[++Len] = m % 2; ll ans = 0; for (int i = 0; i <= a[Len]; i++) ans += DP(Len - 1, 0, i == 1, i == a[Len]); return ans; } int main() { l = Read(), r = Read(); memset (f, -1, sizeof f); printf ("%lld\n", Solve(r) - Solve(l - 1)); return 0; }
这篇关于【YBTOJ】【Luogu P6218】[USACO06NOV] Round Numbers S的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升