BZOJ 1833 【ZJOI2010】 数字计数
2024-08-27 00:49:39
题目链接:数字计数
没啥好说的,裸裸的数位\(dp\)。
先枚举当前是算数字\(x\)出现的次数,设\(f_{i,j}\)表示从高位往低位\(dp\),\(dp\)完了前\(i\)位之后\(x\)出现了\(j\)次的方案数。然后再加一维,表示当前这一位能否自由选数(也就是说之前是否是一路选最大值过来的)。转移分情况讨论一下就好了。
注意这种写法还有一点情况,就是算\(0\)出现的次数时需要减去区间内前导\(0\)的个数。
下面贴代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std;
typedef long long llg; llg l,r,f[21][21][2],mi[21];
int a[21],b[21],l1,l2; void divide(llg x,int *s,int &len){
llg y=x; while(y) len++,y/=10;
for(int i=len;i;i--) s[i]=x%10,x/=10;
} llg work(int *s,int n,int x){
f[0][0][1]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=i;j++){
f[i][j][0]=f[i-1][j][0]*9;
if(j) f[i][j][0]+=f[i-1][j-1][0];
if(s[i]>x){
f[i][j][0]+=f[i-1][j][1]*(s[i]-1);
if(j) f[i][j][0]+=f[i-1][j-1][1];
}
else f[i][j][0]+=f[i-1][j][1]*s[i];
if(s[i]==x){
if(j) f[i][j][1]=f[i-1][j-1][1];
else f[i][j][1]=0;
}
else f[i][j][1]=f[i-1][j][1];
}
llg now=0;
for(int i=1;i<=n;i++) now+=i*(f[n][i][0]+f[n][i][1]);
if(!x){
mi[0]=1; now-=n;
for(int i=1;i<n;i++) mi[i]=mi[i-1]*10;
for(int i=1;i<n;i++) now-=(mi[i]-mi[i-1])*(n-i);
}
return now;
} int main(){
File("a");
scanf("%lld %lld",&l,&r); l--;
divide(l,a,l1); divide(r,b,l2);
for(int i=0;i<=9;i++){
if(i) printf(" ");
printf("%lld",work(b,l2,i)-work(a,l1,i));
}
return 0;
}
最新文章
- 在文件夹中 的指定类型文件中 查找字符串(CodeBlocks+GCC编译,控制台程序,仅能在Windows上运行)
- SQL(触发器)
- IT菜鸟的第2天(输入输出,数据类型,运算符的使用)
- vs代码段快捷键设置
- xcode6中如何添加pch文件
- arm-none-eabi-gcc,makefile,stm官方库构建stm32f4xx工程
- 编译SASS
- vue项目,axios请求图片接口,接口返回的是文件流的形式,如何转换成图片?
- Hadoop高可用集群
- [原创]基于Zynq Linux环境搭建(二)
- (Beta)Let&#39;s-M2后分析报告
- Java 实现String语句的执行(Jexl)
- java.lang.NoSuchMethodException: .<;init>;()
- Nuxt.js部署应用的方式
- BZOJ 3745: [Coci2015]Norma(分治)
- linux每日命令(8):mv命令
- 1-1-linux环境搭建
- 人工智能-机器学习之numpy方法
- go 编译问题
- AI入门课程资源