第一种做法:直接模拟,可以看出0-10 之间有10个满足,10-100之间9个,100-1000之间是90,1000-10000之间是900....即为1xxx1-9xxx9,就是9*pow(10,3),以此类推,分别求出两个数到pow(10,L-1)之间的满足的数的个数(L为数的长度),在求出pow(10,L1----L2-1)的个数,在井陉加减运算就行了,不过这样做起来实在太麻烦,这里只给出代码,不推荐使用这种方法。
代码:
#include <iostream> #include <cstdio> #include <cmath> typedef long long LL; using namespace std; LL ppow(LL a, LL b) //幂运算 { LL sum = 1; for (LL i = 1; i <= b; i++) sum *= a; return sum; } int length(LL a) //求数的长度 { int i=0; while(a>0) { a/=10;i++; } return i; } int main() { LL m,n,i; LL a[20]={0,1,1}; for (i = 3; i <= 19; i++) //初始化 a[i] = a[i - 1] * 10; while (scanf("%lld%lld",&m,&n)!=-1) { LL l1 =length(m) , l2 =length(n) ; m--; LL mm = ppow(10, l1-1), nn = ppow(10, l2-1); LL ml = m / mm, mr = m % 10; LL nl = n / nn, nr = n % 10; if(l1==1&&l2==1) { printf("%lld\n",n-m); continue; } LL x = 1, y = 1; if (l1 == 1) x = m; else { m /= 10; x = m - mm*ml/10 + 1; if (ml > mr) x--; } if (l2 == 1) y = n; else { n /= 10; y = n-nn*nl/10 + 1; if (nl > nr) y--; } if(l1!=1) x+=(ml-1)*a[l1]; if(l2!=1) y+=(nl - 1)*a[l2]; LL sum=0; for (i = l1 ; i < l2; i++) sum += a[i] * 9; cout << sum + y - x<< endl; } return 0; }
第二种方法:也是属于模拟吧,只不过这次分不太详细,写一个函数sum,sum求出的是某个数a,从0-a之间满足题目要求的数的数目,假设a的位数是L,L位长的满足题目要求的数的个数就是a/10-pow(10,L-1),如果a的首位小于等于其末尾位,则上式+1(想想为什么?例如:a=2234567 L=7 sum‘=(2-1)23456 即123456+1 当a=2234561 sum’=123456),此时就完成了大部分工作,在长度为1---L-1的所有的满足情况的数加上就行了,具体见代码吧。
代码:
#include <iostream> #include <cstdio> #include <cmath> typedef long long LL; using namespace std; LL Pow(LL k) //pow函数,不要使用c++自由的函数,因为会琐事精度 { LL ans=1; for(int i=0; i<k; i++) ans*=10; return ans; } LL sum(LL a) //求出0-a满足条件的数的函数 { if(a>=0&&a<=9) return a+1; //0<=a<=9的情况单独处理,为什么是a+1? LL b=a,r=a%10,ans=0; LL i=9,j=0; while(b>=10) { ans+=i; i*=10; j++; b/=10; } a/=10; a-=Pow(j); if(r>=b) a++; //末尾位大于等于首位,则+1 return a+ans+10; } int main() { LL m,n; while(scanf("%lld%lld",&m,&n)!=-1) { m--; printf("%lld\n",sum(n)-sum(m)); } return 0; }
codeforce 205C - Little Elephant and Interval,布布扣,bubuko.com
codeforce 205C - Little Elephant and Interval
原文:http://blog.csdn.net/knight_kaka/article/details/20645827