(截止2020-9-3题目有说是多组输入吗????)

  • 题目考点:数位DP(小学奥数分情况讨论?)
  • 题目大意:统计0 ~ n中的所有数字中,0到9在每个数字的每一位上出现的次数。
  • 题目分析:

1、举例分析: 统计数字2在(0 ~ n=324)的个位上出现的次数,个位有(32 * 1+1)次,在十位上出现(3 * 10+5)次,在百位上出现(0 * 100+100)次;所以数字2共出现(33+35+100=168)次;

如何计算? 我们在计算2在(0 ~ n=324)的十位的时候,可以看到百位上是3,即324之前出现了02X、12X、22X,共30个,然后有320、321、322、323、324共5个数,所以有(3 * 10+5)个(其中的5我们可以直接计算为个位上的4加上1);

注意点1:刚才我们统计的是2,如果统计3在十位上出现的次数呢?观察到324的十位是2,而3大于了十位上的数字,因此在百位到了3之后,十位上不会再出现3,则3在十位只出现了(3 * 10)次; 注意点2:如果统计1在十位上出现的次数呢?由于1小于十位上出现的数字,则31X共出现了10次,即1在十位上共出现了(3 * 10 + 10 * 1)次,这里的10乘1是因为我们现在计算的是十位,若同种情况下统计的是百位应该是100;

2、正常分析: 把数字n拆分成 AAA B CCC 3个部分,统计数字X在B的位置出现的次数时候: (第一步)AAA * 10的位数的次幂(若我们统计的是0则需要将AAA-1后再计算) (第二步)若x大于B位置上的数字,则X不会在该位置出现; 若X等于该位置上的数字,则X在该位置出现次数为CCC+1; 若X小于该位置上的数字,则X在该位置出现次数为10的位数次幂。

由此我们只需统计0到9这10个数字在每一位上出现的次数就好了。 题目代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>

using namespace std;

int len, n, ans, cnt;
vector<int> num;

void solve(int x)  // 拆分数字并统计n的位数
{
    while(x)
    {
        num.push_back(x%10);
        x /= 10;
    }
    reverse(num.begin(), num.end());
    len = num.size();
    return ;
}

int count(int a, int b)
{
    cnt = 0;
    int fr = 0, mid = num[b], be = 0;
    for(int i = 0; i < b; i++)
        fr = fr*10+num[i];
    for(int i = b+1; i < len; i++)
        be = be*10+num[i];
    if(!a && !fr) return 0; // 0不能在最高位
    
    // 第一步
    if(a)
        cnt += fr*pow(10, len-b-1);
    else
        cnt += (fr-1)*pow(10, len-b-1);

    // 第二步
    if(a == mid) cnt += be+1;
    else if(mid > a) cnt += pow(10, len-b-1);

    return cnt;
}

int main()
{
    while(cin >> n)
    {
        num.clear();
        solve(n);
        for(int i = 0; i <= 9; i++)
        {
            ans = 0;
            for(int j = 0; j < len; j++)
                ans += count(i, j);
            printf("%d\n", ans);
        }
    }
    return 0;
}