題目大意：多個詢問，每個詢問問$[l,r](1\leqslant l\leqslant r\leqslant10^{18})$內(nèi)有多少個數(shù)滿足非零數(shù)位小于等于$3$。

題解：數(shù)位$DP$，$f_{i,j}$表示在第$i$位，有$j$個數(shù)位不是$0$的方案數(shù)

卡點：無

?

C++ Code：

#include <cstdio> #include <cstring> int Tim, num[20]; long long M[5][20]; long long run(int x, int cnt, int lim) {if (cnt > 3) return 0;if (!x) return 1;if ((~M[cnt][x]) && !lim) return M[cnt][x];long long ans = 0;for (int op = lim, i = lim ? num[x] : 9; ~i; i--, op = 0) {ans += run(x - 1, cnt + bool(i), op);}if (!lim) M[cnt][x] = ans;return ans; } long long solve(long long x) {int len = 0;while (x) {num[++len] = x % 10;x /= 10;}return run(len, 0, 1); } int main() {scanf("%d", &Tim);memset(M, -1, sizeof M);while (Tim --> 0) {long long l, r;scanf("%lld%lld", &l, &r);printf("%lld\n", solve(r) - solve(l - 1));}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/Memory-of-winter/p/9744644.html

總結(jié)

以上是生活随笔為你收集整理的[CF1036C]Classy Numbers的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。