[CF1036C]Classy Numbers
2024-09-02 11:26:43
题目大意:多个询问,每个询问问$[l,r](1\leqslant l\leqslant r\leqslant10^{18})$内有多少个数满足非零数位小于等于$3$。
题解:数位$DP$,$f_{i,j}$表示在第$i$位,有$j$个数位不是$0$的方案数
卡点:无
C++ Code:
#include <cstdio>
#include <cstring>
int Tim, num[20];
long long M[5][20];
long long run(int x, int cnt, int lim) {
if (cnt > 3) return 0;
if (!x) return 1;
if ((~M[cnt][x]) && !lim) return M[cnt][x];
long long ans = 0;
for (int op = lim, i = lim ? num[x] : 9; ~i; i--, op = 0) {
ans += run(x - 1, cnt + bool(i), op);
}
if (!lim) M[cnt][x] = ans;
return ans;
}
long long solve(long long x) {
int len = 0;
while (x) {
num[++len] = x % 10;
x /= 10;
}
return run(len, 0, 1);
}
int main() {
scanf("%d", &Tim);
memset(M, -1, sizeof M);
while (Tim --> 0) {
long long l, r;
scanf("%lld%lld", &l, &r);
printf("%lld\n", solve(r) - solve(l - 1));
}
return 0;
}
最新文章
- yii2使用相关记录
- MATLAB plot 绘图的一些经验,记下来,facilitate future work
- Jasmine入门(上)
- redis 学习笔记(3)-master/slave(主/从模式)
- Javah提示未找到 ..的类文件
- Python从内存中使用编译后的模块
- Ubuntu 14.04中文输入法的安装
- 《Linux内核设计的艺术》学习笔记(七)INT 0x15中断
- js的严谨模式
- Android开发之异步获取并下载网络资源-下载图片和下载文本内容
- setInterval()-----------js 函数总结
- HDU3709:Balanced Number(数位DP+记忆化DFS)
- (三)Python在windows上安装
- Scala内部类
- vc中Error spawning cl.exe错误的解决方法.
- 初识Python装饰器
- Struts2实现文件上传报错(一)
- 探寻 webpack 插件机制
- f12 headers 变字典快捷方式
- c# 读取json文件信息