本文主要是介绍Poj 2282 The Counting Problem[统计区间 0 - 9出现的次数]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
ps：红色字体为2015/6/14更新
题目链接：http://poj.org/problem?id=2282
问题意思很简单，给你一个闭区间[a, b]，问该区间内的0 - 9出现次数。。a , b <= 10^18。。题目的数据范围还没有这么大，但是，无所谓，10^18也是水水的。。。
断断续续，弄了一天这个问题。。。还是弄明白了。。但是，还是有很多模糊的地方。。但是，应该问题不大。。
我们转化成求f(x, y)，代表 [1, x] 区间内 y出现的次数，当然，y < 10。。
我们的思路就是求每一位上y出现的次数。。。这就是大体上的思路。。
比如 求 f(345, 2)。
我们肯定是先求个位出现2的次数：
该位出现的2次数是怎么求解呢？ 不管是哪一位上的出现某个数字都与他左边和右边的数 以及统计该位上的数有关。。有什么关系呢？
个位(34 + 1) * 1 //左边 * k
十位(3 + 1) * 10
百位(0 + 1) * 100
f(324, 2) =
个位(32 + 1） * 1
十位(3 + 0) * 10 + 4 + 1
百位(0 + 1) * 100
左位 * 该位权值 + (该位 == y ? +右位，该位 < y ? + 0，该位 > y ? + 左位权值)
我这里定义左位该位右位为下：
比如我要统计 16546846，千位上的某个数子出现的次数。。1654为左位，6为该位，846为右位。
为什么左为上影响的个数为 left_digit * k 而不是(left_digit + 1) * k（因为我们考虑到，高位是可以为0的，如果高位为0，就是高位没有数）呢？
假设我们以上面的例子为例：1654为其左位。
我们不考虑1654作为最高位，为什么？因为，如果1654最为最高位的话，我们还需要保证其该为是大于y的，为什么？。。。。。。。。
我们把1654交给其右位来记性处理，如果当前为大于y的话，我们直接加上该位权值即可；如果等于y的话，我们直接加上其右位 ，再加1，为什么？因为我们的右位完全可以把0考虑进去，而没有任何的影响；如果当前位小于y的话，我们就不需要考虑其右位了。
这样说的比较简单。。
还需要注意一下的是，如果y == 0 的话，需要注意高位不能为0，这一点。。。
Code：
<span style="font-size:18px;">#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define INT long long//统计x < 10出现了多少次...
INT Sumof_One_num(INT n, int x)
{INT ans = 0;INT d = 0 , k = 1;while(n){//左侧影响下，应该有多少个.ans += (n / 10 - (x == 0)) * k;//右侧影响应该有多少个..if(n % 10 == x) ans += d + 1;if(n % 10 > x) ans += k;// 记录右侧..d += n % 10 * k;k = k * 10;n /= 10;cout << "ans = " << ans << endl;}return ans;
}int main()
{INT a, b;while(cin >> a >> b && (a || b)){if(a > b) swap(a, b);cout << Sumof_One_num(b, 0) - Sumof_One_num(a - 1, 0);for(int i = 1; i < 10; i ++){cout << ' ' << Sumof_One_num(b, i) - Sumof_One_num(a - 1, i);}cout << endl;}return 0;
}</span>----->
一开始理解起来比较困难，但是，慢慢的讨论一下就会更加的明白，会有更深的认识。。
这篇关于Poj 2282 The Counting Problem[统计区间 0 - 9出现的次数]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
