题解 | #统计数字#

（截止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;
}