动态规划【页码统计】

参考剑指offer中统计1出现的次数：https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6?f=discussion
在本题中，对于0和1-9的处理思路是不一样的。

对于 0：

个位：每出现一个10，就必然出现一次0，所以只需要用number/10即可得到个位出现的次数。

十位：100-109，200-209以此类推，连续出现10次。假如number==318，那么318/100 = 3，但是其中前99中，是没有十位的0的，所以count += (318/100 - 1)​*10。接下来处理余数，只要其大于9，那么直接count += 10，否则就加 k + 1（k为余数）。

对于1-9，参考上述剑指offer中的题解。

代码如下：
之所以用long long，是因为最后一个测试用例用了最大数字，溢出了。

#include <iostream>
#include <vector>

using namespace std;
long long count(long long number, int n){
    long long k = 0, length = 0;
    if(n == 0){
        for(long i = 10;number/i !=0;i *= 10){
            k = number % i;
            if(i == 10)
                length += number/i*(i/10);
            else{
                length += (number/i-1)*(i/10);
                if(k >= i/10)
                    length += i/10;
                else
                    length += k + 1;
            }
        }
        return length;
    }
    for(long i = 1;number/i != 0;i*=10){
        k = number % (10*i);
        length += number/(10*i) * i;
        if(k >= i*(n+1)-1)
            length += i;
        else if(k < i*n)
            length += 0;
        else
            length += k - i*n + 1;
    }
    return length;
}
int main(){
    long long number = 0;
    cin >> number;
    for(int i = 0;i < 10;++i){
        if(i != 0)
            cout << " ";
        cout << count(number, i);
    }
    return 0;
}