题目大意:多个询问,每个询问问$[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;
}

  

最新文章

  1. yii2使用相关记录
  2. MATLAB plot 绘图的一些经验,记下来,facilitate future work
  3. Jasmine入门(上)
  4. redis 学习笔记(3)-master/slave(主/从模式)
  5. Javah提示未找到 ..的类文件
  6. Python从内存中使用编译后的模块
  7. Ubuntu 14.04中文输入法的安装
  8. 《Linux内核设计的艺术》学习笔记(七)INT 0x15中断
  9. js的严谨模式
  10. Android开发之异步获取并下载网络资源-下载图片和下载文本内容
  11. setInterval()-----------js 函数总结
  12. HDU3709:Balanced Number(数位DP+记忆化DFS)
  13. (三)Python在windows上安装
  14. Scala内部类
  15. vc中Error spawning cl.exe错误的解决方法.
  16. 初识Python装饰器
  17. Struts2实现文件上传报错(一)
  18. 探寻 webpack 插件机制
  19. f12 headers 变字典快捷方式
  20. c# 读取json文件信息

热门文章

  1. 【c学习-4】
  2. 【Python 2 到 3 系列】 print 是函数
  3. 【JS】window.print打印指定内容
  4. NPOI导出Excel,添加图片和设置格式,添加条形码
  5. uniqueidentifier数据类型转换
  6. C++继承权限
  7. 统计输入任意的字符中中英文字母,空格和其他字符的个数 python
  8. Android AppUtil通用类
  9. 9.2python操作redis
  10. java练习题——字符串