计数问题

找到 [a,b] 中出现 x 的次数

设定一个函数 count(n, x) 1 ~ n 中出现 x 的次数 则 count(b, x) - count(a - 1, x) 就是 a~b 中出现x的次数

常用技巧，求一个区间不好算，可以求从头到 b, 再求从头到 a, 最后作差即可

求1~n中 出现 x 的次数

暴力法，for(i, n) for(j, get(i)) if(is(x)) res++ 渐进时间复杂度为 O(n * 8) n ~~ 1e8，必超时 需要优化

对于有关大整数的问题，最好是与其位数相关（比如高精度就是以位数处理） 同理，我们把 第 1 ~ get(n) 位中 是 x 的情况求和即可 就像汉明码中检测位分组那样。

外层循环为 for(i, get(n)) 如何求某一位为x的次数和呢？ 设给的n为 abc d efg 一般的来说，符合条件的数为 xxxdxxx，需要找出是这个格式的数量。 类似于石子合并的区间问题，我们可以拆分成两个部分，左侧从 000 ~ abc - 1，那么右侧从 000 ~ 999 都符合条件，即 abc - 1 * 1000 个。 d左边固定，之前算的是 001 ~ abc - 1，故固定为 abc， 则右边就是 efg 个。 可得 res += abc - 1 * 10 ^ (get(n) - j) + efg 为第 j 位的包含 d 的数，但需要求的是包含 x 的数， 左侧为 001 ~ abc - 1 时，当前位可以选 0 ~ 9，故不需要管当前位是否 >= x。 当左侧为 abc 时，当前位若小于 x , 则不符合条件。 若等于x，则 res += efg + 1； 若大于x，则 右侧可取 0 ~ 999， 为 10 ^ (get(n) - j)。 即：

int len = get(n), res = 0;
for(int j = 1; j <= len; i++)
{
	int p = pow(10, len - j);//当前位的进制
	int l_num = n / p / 10; // abc
	int r_num = n % p; // efg
	int i = (n / p) % 10; // 第j位的数
	res += l_num * p;
	if(i > x) res += p;
	else if(i == x)res += r_num + 1; // 加一因为有0
}
 

看起来挺棒对吧，但少考虑了所有数字枚举都要考虑的问题，前导0。 假如说 x == 0，左边 000 ~ abc - 1 为000时，整个数并不一定包含0，为 efg，也就是说加重复了一部分，这之中若为 100，它的0应该在 j == len - 1, len 时计算并加上，这里若加上则属于重复计算。 对于计数问题，不能出现重复计算，对于重复的部分，通常有两种解决办法，不加上重复的 和 加上重复之后减去重复的部分。 不加上：

if(x) res += l_num * p;
else if(l_num)res += (l_num - 1) * p; // 不加000的情况
// 因为有 l_num - 1，那么若左边为0，也不应该加

减去重复的： 把第一条下面加一条：if(x == 0) res -= r_num + 1;

左边的处理好了，对于右边来说，x == 0，始终会进行res += p 或 res += r_num + 1 的运算，正常该数为 abc0efg，符合条件，但若 l_num == 0 呢？ 依然是 efg，直接不让它加上更简洁一些：

if(i > x  && !(x == 0 && l_num == 0)) res += p;
else if(i == x && !(x == 0 && l_num == 0)) res += r_num + 1;
// 或者条件换为 (x != 0 || l_num != 0) 即 (x || l_num)

现在便可得到正确结果了。

最终代码为：

#include <iostream>
#include <cstring>
#include <math.h>
#include <algorithm>
using namespace std;
 
 
int get(int n)
{
    int res = 0;
    while(n)
    {
        res++;
        n /= 10;
    }
    return res;
}
 
 
int count(int n, int x)
{
    int len = get(n), res = 0;
    for(int j = 1; j <= len; j++)
    {
        int p = pow(10, len - j), l_num = n / p / 10, r_num = n % p, i = (n / p) % 10;
        if(x) res += l_num * p;
        else if(l_num) res += (l_num - 1) * p;
        
        if(i > x && !(x == 0 && l_num == 0)) res += p;
        else if(i == x && ! (x == 0 && l_num == 0)) res += r_num + 1;
    }
    return res;
}
 
 
int main()
{
    int a,b;
    while(cin >> a >> b && a + b)
    {
        if(a > b) swap(a,b);
        for(int i = 0; i <= 9; i++)
        {
            cout << count(b,i) - count(a - 1,i) << " ";
        }
        cout << endl;
    }
    return 0;
}