欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【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;
}

相关标签: 算法设计