本文主要是介绍POJ - 3286 - How many 0's? - （统计0的个数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=3286
题意：
给出[a,b]，统计这个闭区间中的所有数中包含多少个0。
解析：
整体思路就是我们用函数solve(n)求出[0,n]中包含0的总个数，答案就是solve(b)-solve(a-1);
具体solve函数做法就是对于n的每一位，判断该位为0方案数（该位为0，其余位任意，但是整体的值要小于等于n），统计完所有位上的方案数，就是要求的答案即包含0的个数。
在solve函数中对于n，当我们枚举它的每一位，令该位为0时（所以不用枚举最高位，最高位不会有0）的方案数就是，该位左边位的和法组合数*该位右边数的合法组合数。
1.若该位本来不是0，比如n=120345，我们处理3这一位时，令此位为0，为了保证组合值小于等于n，右边高位合法取值为[1，120]（共120个），而左边的两位是任意取的也就是[0,99]（共100个），方案数就是：120*100
2.若该位本来就是0，比如处理120354中的0所在位时，右边可以先取到[1,119]（右边为120是单独讨论），左边还是任取[0,999]；右边取120时，为了保证组合值小于等于n，左边只能取[0,345]（共345+1个）方案数就是：119*1000+346
代码：
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<queue>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
#define M 35
ll solve(ll n)
{if(n<0)return 0;ll sum=1,div=10; //sum初始化为1是因为一位数中的0while(n/div) //div有几个0处理的就是第几位{if((n%div)==(n%(div/10))) //如果当前位为0sum+=(n/div-1)*(div/10)+n%(div/10)+1;else //当前位不为0sum+=(n/div)*(div/10);//n/div是左边的高位（高位组合方案即是此值），div/10得到右边的低位组合方案div=div*10;}return sum;
}
int main()
{ll a,b;while(scanf("%lld%lld",&a,&b)!=EOF){if(a<0&&b<0)break;printf("%lld\n",solve(b)-solve(a-1));}return 0;
}这篇关于POJ - 3286 - How many 0's? - （统计0的个数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
