题面
题目链接
大秦 为你打开 题目传送门
备用题面
将 $N$ 到 $M$ 的数字依次写在一张纸上,问出现多少个 $0$ 。
思路
就是一道数位DP板子题,不想说话了。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
|
#include<bits/stdc++.h> using namespace std;
typedef long long ll; typedef __int128 int128;
namespace FastIO { template<typename T> inline T read(T& x) { x = 0; int f = 1; char ch; while (!isdigit(ch = getchar())) if (ch == '-') f = -1; while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); x *= f; return x; } template<typename T, typename... Args> inline void read(T& x, Args &...x_) { read(x); read(x_...); return; } inline ll read() { ll x; read(x); return x; } }; using namespace FastIO;
ll n, m;
int a[110]; ll dp[110][110];
inline void Input() { read(n, m); }
inline ll Dfs(int len, int lim, int top, int sum) { if(len == 0) { if(top) return 1; return sum; } if(!lim && !top && dp[len][sum] != -1) return dp[len][sum]; int mx = lim ? a[len] : 9; ll ans = 0; for(int i = 0; i <= mx; i++) { ans += Dfs( len - 1, lim && i == mx, top && i == 0, top ? 0 : sum + (i == 0) ); } if(!lim && !top) dp[len][sum] = ans; return ans; }
inline ll Calc(ll x) { if(x < 0) return 0; int len = 0; while(x) { a[++len] = x % 10; x /= 10; } return Dfs(len, 1, 1, 0); }
inline void Work() { memset(dp, -1, sizeof(dp)); printf("%lld", Calc(m) - Calc(n - 1)); }
int main() { int T = 1; while(T--) { Input(); Work(); } return 0; }
|