「LightOJ 1140」How Many Zeroes?

题目链接:LightOJ-1140

Description

求$[a,b]$中每一个数的数位为$0$的个数总和。

Data Range

$a,b$为无符号$32$位正整数。

Solution

定义$f[i][j]$表示当前到第$i$个数位,非前导零的零一共有$j$个的$0$的个数总和。

然后数位$DP$。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace _digit {
  int q[105], tot;
  void get_digit(ll x) {
    for (tot = 0; x; x /= 10) {
      q[++ tot] = x % 10;
    }
  }
}

ll f[105][105];

ll dfs(int cur, int cnt, int lead, int limup) {
  if (!cur) {
    return lead ? 1 : cnt;
  }
  if (!lead && !limup && f[cur][cnt]) {
    return f[cur][cnt];
  }
  int up = limup ? _digit::q[cur] : 9;
  ll res = 0;
  for (int i = 0; i <= up; i++) {
    if (lead) {
      res += dfs(cur - 1, 0, (i == 0), limup && (i == up)); 
    } else {
      res += dfs(cur - 1, cnt + (i == 0), 0, limup && (i == up));
    }
  }
  if (!lead && !limup) {
    f[cur][cnt] = res;
  }
  return res;
}

ll solve(ll x) {
  _digit::get_digit(x);
  return dfs(_digit::tot, 0, 1, 1);
}

int main() {
  ios::sync_with_stdio(false);
  int T; 
  cin >> T;
  for (int it = 1; it <= T; it++) {
    memset(f, 0, sizeof f);
    ll l, r;
    cin >> l >> r;
    cout << "Case " << it << ": " << solve(r) - solve(l - 1) << '\n';
  }
  return 0;
}
最后修改:2019 年 09 月 01 日 08 : 58 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论