题目描述
给定两个整数 a 和 b,求 a 和 b 之间的所有数字中0~9的出现次数。
样例
注意到样例里面有个坑是第一个数有可能大于第二个
1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0
数位DP树形统计方法
参考资料:算法提高班
手写笔记
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
int base[10];
int f[10][10];
int g[10][10];
void init()
{
base[0] = 1;
for(int i = 1 ; i <= 9 ; i++) base[i] = base[i-1]*10;
//从00……0 - 99……9 的各位数字有多少个,其中i为数字个数(包含前导零)
for(int i = 0 ; i <= 9 ; i++) f[1][i] = 1;
for(int i = 2 ; i <= 9 ; i++)
for(int j = 0 ; j <= 9 ; j++)
f[i][j] = f[i-1][j]*10 + base[i-1];
//从1 - 99……9 的各位数字有多少个,其中i为数字个数(不包含前导零)
for(int i = 1 ; i <= 9 ; i++) g[1][i] = 1;//循环从1开始
for(int i = 2 ; i <= 9 ; i++) {
g[i][0] = g[i-1][0] + f[i-1][0]*9;
for(int j = 1 ; j <= 9 ; j++)
g[i][j] = g[i-1][j] + f[i-1][j]*9 + base[i-1];
}
}
vector<int> dp(int n)
{
vector<int> ans(10,0); //记录答案
if(n<=0) return ans; //边界条件
vector<int> nums;
while(n) nums.push_back(n%10), n/=10;
vector<int> last(10,0); //记录前缀中各个数字个数
//统计1 - 99……9(n-1个9)里面各个数字有多少个
for(int i = 0 ; i <= 9 ; i++) ans[i] = g[nums.size()-1][i];
//统计大于10……0(n-1个0) 的树里各个数字有多少个
for(int i = nums.size()-1 ; i >=0 ; i--) {
//循环变量i可以表示剩下的数字有多少个
int x = nums[i];
for(int j = i==nums.size()-1 ; j < x ; j++) { //第一次循环不能有0
//前缀部分
for(int k = 0 ; k <= 9 ; k++)
ans[k] += last[k] * base[i];
//当前位置部分
ans[j] += base[i];
//后缀部分
for(int k = 0 ; k <= 9 ; k++)
ans[k] += f[i][k];
}
//更新前缀计数器
last[x] ++;
//统计叶子节点(这个数本身)
if(!i) for(int k = 0 ; k <= 9 ; k++) ans[k] += last[k];
}
return ans;
}
vector<int> ask(int a, int b)
{
auto x = dp(b);
auto y = dp(a-1);
vector<int> ans;
for(int i = 0 ; i <= 9 ; i++) ans.push_back(x[i]-y[i]);
return ans;
}
void print(vector<int> ans)
{
for(auto x:ans) printf("%d ",x);
puts("");
}
bool check(int x)
{
auto t = ask(x,x);
vector<int> cnt(10,0);
while(x) cnt[x%10]++,x/=10;
for(int i = 0 ; i <= 9 ; i++)
if(cnt[i] != t[i])
return false;
return true;
}
int main()
{
init();
//这里是一个DEBUG函数
// for(int i = 1 ; i <= 1000000 ; i*=10) {
// if(!check(i))
// printf("ERROR:%d\n",i);
// }
int a,b;
while(cin >> a >> b, a||b) {
if(a>b) swap(a,b);
auto t = ask(a,b);
print(t);
}
return 0;
}
你说得对。但我认为母猪产后护理,首先要从产前做起,母猪产前四五天要逐渐减少饲喂量,其目的是减少腹部压力,产前吃得少,产后才能吃得多。若产前吃得多,不仅会使产程过长,而且还会造成产后胃积食,你不关心,你不在乎,你只想着你自己
你说的对, 但<原神>是由拳头公司开发的一款全新射击类fps游戏..........
楼主练过瘦金体吧?
借个楼,我觉得我的代码看着更简单些,思路同上,路过的可以看看哈~
https://www.acwing.com/activity/content/code/content/4041182/
大佬666
人家在用dp 你这根本不是dp的思想
她用的就是dp的思想
兄弟们,我不敲代码了,改行学书法去了
hhhhh
牛,看完视频发现y总这题没用dp
## 不会写书法的程序员
# 不是好的题解人
这个字也太好看了!!!
这个字,要不手写代码吧
写得都很好,但是没有递推公式…呕
lz多少学过书法的 hhh
所以评论里是因为解题思路太难理解了于是把注意力转移到了字体上吗?
赞,hh
现实版的买椟还珠
6
好漂亮的字的啊
yxc划分法
第二篇更好理解qaq,这篇题解字真好看
我是来看字儿的
//统计叶子节点(这个数本身) if(!i) for(int k = 0 ; k <= 9 ; k++) ans[k] += last[k];
救命啊,最后一下为什么又要加上last中的数讲实话我觉得分析的非常到位,各个细节都讲到了
这字写的 你还来码代码
## 计算0和非0分开处理