BZOJ 1833 [ZJOI2010]count 数字计数(数位dp)

本文主要是介绍BZOJ 1833 [ZJOI2010]count 数字计数(数位dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：[kuangbin带你飞]专题十五 数位DP D - Bomb

题意

输入n,m，求n～m范围内的所有数字中，分别输出0～9出现的总数是多少。

思路

和 POJ 3286 How many 0’s? (数位dp)的思路基本是一样的，只是略有区别。
0和1～9要分开处理，是因为前缀0的问题。因为当某一位取0时，前面部分的数是不能为0的，而取1～9是可以前面为0的。

代码

#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;elseans[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;elseans[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;
}

这篇关于BZOJ 1833 [ZJOI2010]count 数字计数(数位dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---