輸入n,m,求n~m范圍內的所有數字中,分別輸出0~9出現的總數是多少。
和 POJ 3286 How many 0’s? (數位dp)的思路基本是一樣的,只是略有區別。
0和1~9要分開處理,是因為前綴0的問題。因為當某一位取0時,前面部分的數是不能為0的,而取1~9是可以前面為0的。
<code class="hljs perl">#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cstdlib> #include <vector> #include <cmath> #include<map> using namespace std; #define LL long long LL p[20]; LL ans[10] = {}; void init() { p[0] = 1; for(int i=1; i<18; i++) p[i] = p[i-1]*10; } void solve(LL x, int f) { if(x == -1) { ans[0]++; return; } for(int k=1; k<10; k++) { for(int i=1; ; i++) { LL l = x/p[i]; LL r = x%p[i-1]; LL now = x%p[i]/p[i-1]; if(now > k) ans[k] += (l+1)*p[i-1]*f; else if(now == k) ans[k] += (l*p[i-1]+r+1)*f; else ans[k] += l*p[i-1]*f; if(p[i] > x) break; } } for(int i=1; ; i++) { LL l = x/p[i]; LL r = x%p[i-1]; LL now = x%p[i]/p[i-1]; if(now > 0) ans[0] += l*p[i-1]*f; else ans[0] += ((l-1)*p[i-1]+r+1)*f; if(p[i] > x) break; } } int main() { LL n, m; init(); cin>>n>>m; solve(m, 1); solve(n-1, -1); for(int i=0; i<9; i++) printf("%lld ", ans[i]); printf("%lld\n", ans[9]); return 0; }</map></cmath></vector></cstdlib></cstdio></cstring></algorithm></iostream></code>