- 题目描述：
-
亲们！！我们的外国友人YZ这几天总是睡不好,初中奥数里有一个题目一直困扰着他,特此他向JOBDU发来求助信,希望亲们能帮帮他。问题是：求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
- 输入：
-
输入有多组数据,每组测试数据为一行。
每一行有两个整数a,b(0<=a,b<=1,000,000,000)。
- 输出：
-
对应每个测试案例,输出a和b之间1出现的次数。
样例输入：
0 5 1 13 21 55 31 99样例输出：
1 6 4 7【解题思路】对于给定一个数，算包含的1的个数，我们可以将这个数分为很多部分，然后分别算1的个数。首先我们很容易得到一个n位数中1的个数，n位数1的个数等于n-1位数中1的个数与10相乘加上第n位为1的额外增加的个数pow(10,n-1)。
例如给定105，可以从第一位开始计算，首先是两位数0-99中1的个数，然后是100-105中首位1的个数为6，然后到第二位0，不计算。第三位5，计算0位数1个数0个，然后计算1这个数1的个数为1。最后将所有计算结果相加。
AC code：
#include <cstdio> #include <iostream> #include <string> #include <vector> #include <cmath> #include <cstring> #include <cstdlib> using namespace std; int clude(string &str,const int&k) { int re=0; for(int i=k;i<str.length();++i) re=re*10+str[i]-'0'; return re; } int cal(const int &tt,const vector<int> &numidx) { if(tt<=0) return 0; int all=0; int idx; char strc[15]; sprintf(strc,"%d",tt); string str(strc); for(int i=0,j=str.length()-1;i<str.length();++i,--j) { idx=str[i]-'0'; if (idx==0) continue; else if(idx==1) { all+=clude(str,i+1); ++all; all+=numidx[j]; } else { all+=pow(10.,j); all+=numidx[j]*idx; } } return all; } int main() { int a,b; vector<int> numidx(13,0); numidx[1]=1; for(int i=2;i<13;++i) numidx[i]=numidx[i-1]*10+pow(10.,i-1); while(cin>>a>>b) { if(a<b) printf("%d ",cal(b,numidx)-cal(a-1,numidx)); else printf("%d ",cal(a,numidx)-cal(b-1,numidx)); } return 0; } /************************************************************** Problem: 1373 User: huo_yao Language: C++ Result: Accepted Time:40 ms Memory:1520 kb ****************************************************************/题目链接：http://ac.jobdu.com/problem.php?pid=1373九度-剑指Offer习题全套答案下载：http://download.csdn.net/detail/huoyaotl123/8276299