【bzoj1833】 ZJOI2010—count 数字计数
2024-08-26 08:42:54
http://www.lydsy.com/JudgeOnline/problem.php?id=1833 (题目链接)
题意
求在${[a,b]}$范围内整数中,每个数码出现的次数。
Solution
数位dp。
${t}$数组取到最大数时表示每一位是多少。
${f[i][j][k]}$表示第${i}$位,这一位上的数为${j}$,数字${k}$的出现次数。转移:$${f[i][j][k]=\sum_{l=0}^9f[i-1][l][k]+10^(i-1)}$$
${g[i][k]}$表示第${i}$位,这一位上的数取到最大时数字${k}$的出现次数。转移:$${g[i][k]=\sum_{j=0}^{t[i-1]-1}f[i-1][j][k]+g[i-1][k]}$$
当然,如果${g[i][t[i]]}$还要再加上${t[i]}$对方案的贡献。
细节
感觉细节还是蛮多的,还是不够熟练啊
代码
// bzoj1833
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<ctime>
#define LL long long
#define inf (1ll<<30)
#define MOD 1000000007
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; LL a[2],t[20],f[20][10][10],g[20][10],ans[10];
int n; void solve(int p) {
memset(f,0,sizeof(f));memset(g,0,sizeof(g));
for (n=0;a[p];a[p]/=10) t[++n]=a[p]%10;
for (int i=0;i<10;i++) f[1][i][i]=1;
LL bin=1,bb=0;
g[1][t[1]]=1;
for (int i=2;i<=n;i++) {
bb+=bin*t[i-1],bin*=10;
for (int j=0;j<10;j++) {
for (int k=0;k<10;k++)
for (int l=0;l<10;l++) f[i][j][k]+=f[i-1][l][k];
f[i][j][j]+=bin;
}
for (int k=0;k<10;k++) {
g[i][k]=g[i-1][k];
for (int j=0;j<t[i-1];j++) g[i][k]+=f[i-1][j][k];
}
g[i][t[i]]+=bb+1;
}
int q=p ? 1 : -1;
for (int i=1;i<n;i++)
for (int j=1;j<10;j++)
for (int k=0;k<10;k++)
ans[k]+=f[i][j][k]*q;
for (int j=1;j<t[n];j++)
for (int k=0;k<10;k++)
ans[k]+=f[n][j][k]*q;
for (int k=0;k<10;k++)
ans[k]+=g[n][k]*q;
}
int main() {
scanf("%lld%lld",&a[0],&a[1]);a[0]--;
solve(0);solve(1);
for (int i=0;i<10;i++) {
printf("%lld",ans[i]);
if (i<9) printf(" ");
}
return 0;
}
最新文章
- poj 3069 Saruman&#39;s Army
- Backbone源码解析(三):Collection模块
- C#无需IIS构建XmlRpc服务器
- Working with Data &#187; Getting started with ASP.NET Core and Entity Framework Core using Visual Studio &#187; 创建复杂数据模型
- ios调打电话代码
- (转载)Undefined variable: PHP_SELF的问题解决方法
- HTTP数据包头解析---之温故而知新!
- php 控制页面跳转
- 关于SVN配置文件的一个小例子
- RobotFramework自动化测试框架-移动手机自动化测试Click Element At Coordinates关键字的使用
- iOS 写给iOS开发者的React Native学习路线(转)
- Android For JNI(二)——C语言中的数据类型,输出,输入函数以及操作内存地址,内存修改器
- chrome通过devtools来查看Devtools Extension与浏览器内核实际通信的数据情况
- SpringIOC框架详解
- JAVA课程课后作业之使用递归完成回文
- input type=file实现图片上传,预览以及图片删除
- ubuntu下安装nodejs和npm
- ios 处理WKContentView的crash
- 前端常见算法面试题之 - 从尾到头打印链表[JavaScript解法]
- [hihoCoder] #1055 : 刷油漆