这题是经典的数位dp题,是真的学了很久,一开始就不明白怎么做,特别是那个类似二叉树的分叉的过程,以及为啥乘10^i,这个乘10^i是真的怎么想也想不明白,幸亏看了yxc的视频,他的解释是真的很棒(虽然那期视频还挺搞,把自己绕迷糊了)

步入正题

本题关键的核心点,是理解到,可以求,每一位上该数的个数

a b c d e f g

对于d

第一种情况

左半部分         000~abc - 1

右半部分        000~999

为啥上半部分是000开始??其实关键是d这一位要有效,这一步是真挺搞,所以d = 0的时候要从001开始

上面所以,是 abc * 1000 ,这才是乘10^i的原因,因为类似组合问题,000左半部分和000~999左半部分依次配对,这才是乘的原因,y总的视频对我而言最棒的就是解释了这个点,这才真正搞明白为啥是乘

第二种情况

左半部分        abc

右半部分        分类讨论

    d > x  右半部分任意取 1000 也就是10^i

    d = x 右半部分是000~efd 也就是efg + 1

    d < x 取不到,0

接下来是对x = 0的讨论,这点是真的搞,看视频笑死了,y总越改越迷糊,和我敲代码一样,莫名感同身受

对于x = 0的情况,关键在于第一种情况,这个左半部分,是不能从000开始的,得从001,为啥?

前面从000开始,是因为,比如0001xxx,这个1xxx,实际上就代表了第四位是1的情况的其中一种,你可能疑问,不对啊,这个1xxx明明是第一位啊!没错,但实际上,此时的前导0默认占位了,这个位当前的数字是有效的,而对于000 0xxx,这个数字就成了xxx,前面的0直接没了!!!这就导致,这种不合理的数字的0也被记录了,是多出来的这部分,得删除!,所以才从001开始,最开始y总写的从100开始,这更搞

还有一点,对于第一位是0的情况,直接跳过,这种的没有讨论价值,因为前面没数,这个第一位是0是无效数字

对于第一位,第一种情况是无效情况,其实不需要特殊处理,因为l <= r是get函数中循环进行的条件,但y总改迷糊改成特殊处理了,这是不需要的

这题难度其实是真挺大的,主要x = 0的情况是真挺搞,还有就是,首位不能为0,这两个点是最折磨的,很难改的,特别是这个首位不能为0,非常难考虑,我现在也就纯理解核心点+背模板,对于这种特殊点的处理也就是背下来,理解确实难..

#include<bits/stdc++.h>
#define endl '\n'
#define int int64_t
using namespace std;
int pow10(int b) {int res = 1, a = 10;while (b) {if (b & 1) res *= a;a *= a, b >>= 1;}return res;
}
int get(vector<int>& num,int l,int r) {int res = 0;for (int i = l; i <= r; ++i) {res = res * 10 + num[i];}return res;
}
int cnt(int n,int x) {// 1 - n中x出现的次数vector<int>num;while (n) num.push_back(n % 10), n /= 10;reverse(num.begin(), num.end());n = num.size();int res = 0;for (int i = (x == 0 ? 1 : 0); i < n; ++i) {res += get(num, 0, i - 1) * pow10(n - i - 1);if (!x) res -= pow10(n - i - 1);//这就是减去000的这种特殊情况,这种的不成数字if (num[i] > x) res += pow10(n - i - 1);else if (num[i] == x) res += get(num, i + 1, n - 1) + 1;}return res;
}
signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int a, b; cin >> a >> b;for (int i = 0; i < 10; ++i)cout << cnt(b, i) - cnt(a - 1, i) << " ";cout << endl;return 0;
}