页码问题

题目来源

这道题来自于牛客

https://ac.nowcoder.com/acm/problem/15327

下面给出该题的题面

原题题面

小明前几天看书看累了，脑海中突然闪过，这书的页码也很可爱啊。一本书的页码从自然数1按自然顺序编码到n.每个页码不会含有多余的前导数字0.例如，第6页用数字6表示，而不是06、006表示。下面问题来了，你能帮忙小明解决以下问题：给定总页码n，计算出书的全部页码中分别用到的多少次数字0，1，2，…，9.

输入格式

输入书的总页码一个整数n。

输出格式

输出总共10行。在第k行输出页码中用到数字k-1的次数。（k=1,2,…,10）

题目解释

暴力

首先，我是直接暴力解法，把每个数的每一位得出来的数字依次相加，设一个数组来记录0到9的数字个数，然后牛客说我超时了，用dev的时候发现在1e9的时候甚至要27s。想了很久没想明白，之后我借鉴了一个大佬的想法，直接算每一个数字的个数，
通过一些规律来计算。

优化

我们先设置一个数，以11459为例

先从1开始，从个位开始数，1，2，3，4，5，6，7，8，9，10每十位就有一个数的个位上是1，那么11459/10=1145……9,一共有1145个10，就有1145个1。由于还余了9，注意9大于1，那么还有11450，11451，11452…11459,这九个数没算，还少了一个1，我们就还要加一个1，所以个位上一共有1146个1；

现在从十位开始，11，12，13，14，15，16，17，18，19，20，…,99每百位就有十个数的十位上是1，那么11459/100=114…..59,一共有114个100，就有114*10个1。由于还余了59，注意5大于1，那么还有11410，11411，…,11419没算，还少了十个1，我们就还要加10个1，所以十位上一共有1150个1；

从百位开始，也遵循上面的思想，11459/1000=11……459,4大于1，所以百位上有11*100+100个1，即1200个1；

从千位开始，对于1来说就有些特别了，因为11459/10000=1……1459,所以有1*1000个1，因为1等于1，所以还有11000，11001，11002…,11459上的千位上的1没有数，从0开始到459有460个数，那就要再加460，即1460个1；

万位也是如此，11459/100000=0……11459,所以有0*10000个1，1等于1，就有10000，10001，10002…,11459上的万位上的1没有数，从0到1459有1460个数，那就要再加1460个1；最后一共有1146+1150+1200+1460+1460=6416个1；

同理2，3，4，5…,9也是这么算

例子

对于6为例

个位	11459/10=1145...9>6 			1145 * 1+1;
十位	11459/100=114...59<60 			114 * 10;
百位	11459/1000=11...459<600 		11 * 100;
千位	11459/10000=1...1459<6000 		1 * 1000;
万位	11459/100000=0...11459<60000 	      0 * 10000;
一共	1146+1140+1100+1000+0=4386个6；

再来考虑特殊的0，还是以11459为例

从个位开始，11459/10=1145…9>0 ,但此时不能单纯的用1145 * 1+1了，因为11450是被计算到那1145个0里面了
（你看1，2，3，4，5，6，7，8，9，10，在出现0的时候进位了，那么这个0在11459/10=1145时就被计算到了）

所以个位上有1145  * 1个0；
十位，		11459/100=114...59>10 				114 * 10；
百位，		11459/1000=11...459>100 			11 * 100；
千位，		11459/10000=1...1459>1000 			1 * 1000；
万位，		11459/100000=0...11459>10000 		      0 * 10000;
一共有		1145+1140+1100+1000+0=4385个0；

代码

代码1(简单循环找规律)

//牛客过不了
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long ll;
ll sum1(ll n, ll i)
{
　　ll sum = 0, m, s = 1, panduan;
　　ll k = n;
　　if (i == 0) {
　　　　while (k > 0) {
　　　　　　m = k / 10;
　　　　　　sum += m * s;
　　　　　　s *= 10;
          k /= 10;
       }
　　}
　　else {
　　　　while (k > 0) {
　　　　　　m = k / 10;
　　　　　　sum += m * s;
　　　　　　panduan = k % 10;
　　　　　　if (panduan > i) {
　　　　　　	sum += s;
　　　　	}
　　　　	if (panduan == i) {
　　　　　　	sum += n - k * s + 1;
　　　　	}
　　　　	s *= 10;
    	}
　　}
　　return sum;
}
int main()
{
　　ll n, i, m;
　　cin >> n;
　　for (i = 0; i <= 9; i++) {
　　　　m = sum1(n,i);
　　　　cout << m << endl;
　　}
　　return 0;
}

代码2(数位dp)

//牛客还是过不了
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
typedef long long ll;
ll l, r, dp[N], sum[N], mi[N];
ll ans1[N], ans2[N];
int a[N];

void solve(ll n, ll *ans) {
  ll tmp = n;
  int len = 0;
  while (n) a[++len] = n % 10, n /= 10;
  for (int i = len; i >= 1; --i) {
    for (int j = 0; j < 10; j++) ans[j] += dp[i - 1] * a[i];
    for (int j = 0; j < a[i]; j++) ans[j] += mi[i - 1];
    tmp -= mi[i - 1] * a[i], ans[a[i]] += tmp + 1;
    ans[0] -= mi[i - 1];
  }
}

int main() {
  scanf("%lld%lld", &l, &r);
  mi[0] = 1ll;
  for (int i = 1; i <= 13; ++i) {
    dp[i] = dp[i - 1] * 10 + mi[i - 1];
    mi[i] = 10ll * mi[i - 1];
  }
  solve(r, ans1), solve(l - 1, ans2);
  for (int i = 0; i < 10; ++i) printf("%lld\n", ans1[i] - ans2[i]);
  return 0;
}

代码3

//牛客依然过不了
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;

int get(vector<int> u, int l, int r) {
    int res = 0;
    for(int i = l;i >= r;i--) {
        res = res * 10 + u[i];
    }
    return res;
}

int get10(int x) {
    int res = 1;
    while(x -- ) {
        res *= 10;
    }
    return res;
}

int count(int n, int x) {
    if(!n) return 0;
    
    vector<int> u;
    int res = 0;
    while(n) {
        u.push_back(n % 10);
        n /= 10;
    }
    n = u.size();
    for(int i = n - 1 - !x;i >= 0;i--) {
        if(i < n - 1) {
            res += get(u, n - 1, i + 1) * get10(i);
            if(!x) res -= get10(i);
        }
        if(u[i] == x) res += get(u, i - 1, 0) + 1;
        else if(u[i] > x) res += get10(i);
    }
    return res;
}

int main()
{
    int a, b;
    while(cin >> a >> b, a) {
        if(a > b) swap(a, b);
        for(int i = 0;i < 10;i++) {
            cout << count(b, i) - count(a - 1, i) << ' ';
        }
        cout << endl;
    }
    return 0;
}