【1-1】统计数字问题
程序员文章站
2024-03-14 21:03:44
...
【题解】
000..0~999..9 (n个9)则0~9中每个数字出现的次数都是n*10^(n-1),即每个数字出现次数相同。
但是因为不含前导0.
所以要把多算的0给去掉。
具体的,设n这个数字的长度为L,则需要减去1111....1(L个1)个多余的0. 然后做个数位DP就好。
详见:https://www.cnblogs.com/AWCXV/p/7632451.html
【代码】
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
string s;
int _pow = 1;
int cnt[10];
int get_num(int l,int r){
int temp = 0;
for (int i = l;i <= r;i++){
temp = temp*10+s[i]-'0';
}
temp++;
return temp;
}
int main(){
cin >> s;
int len = s.size();
for (int i = 1;i <= len-1;i++) _pow*=10;
for (int i = 0;i < len;i++){
int si = s[i]-'0';
for (int j = 0;j <= 9;j++) cnt[j]+=si*(len-i-1)*_pow/10;
for (int j = 0;j <=si-1;j++){
cnt[j]+=_pow;
}
cnt[si]+=get_num(i+1,len-1);
_pow=_pow/10;
}
int more0 = 0;
for (int i= 1;i <= len;i++){
more0 = more0*10+1;
}
cnt[0]-=more0;
for (int i = 0;i <= 9;i++){
cout<<cnt[i]<<endl;
}
return 0;
}
推荐阅读
-
回溯算法批处理作业调度问题
-
【1-1】统计数字问题
-
最大公约数和最小公倍数问题
-
Leetcode:204. Count Primes 求素数的优化问题
-
面试问题总结(问题篇) 博客分类: 面试 面试多线程javajdbc
-
谷歌浏览器使用百度引擎跳转到百度主页的问题 博客分类: 浏览器设置 谷歌浏览器地址栏跳转百度主页
-
elasticsearch2.0源码在开发环境eclipse中启动的问题及解决方案 博客分类: 开源软件 elasticsearch
-
elasticsearch2.0源码在开发环境eclipse中启动的问题及解决方案 博客分类: 开源软件 elasticsearch
-
maven使用时遇到的一些小问题 博客分类: maven mavenjava
-
超链接target为_blank时的问题 博客分类: html/css/ckeditor javascripthtmlhreftarget