The Little Elephant very much loves sums on intervals.
This time he has a pair of integers l and r (l ≤ r). The Little Elephant has to find the number of such integers x (l ≤ x ≤ r), that the first digit of integer x equals the last one (in decimal notation). For example, such numbers as 101, 477474 or 9 will be included in the answer and 47, 253 or 1020 will not.
Help him and count the number of described numbers x for a given pair l and r.
The single line contains a pair of integers l and r (1 ≤ l ≤ r ≤ 1018) — the boundaries of the interval.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64dspecifier.
On a single line print a single integer — the answer to the problem.
2 47
12
47 1024
98
看了其他博客都是数位dp,我用了不同的解法。对于n,m，分别算出cal(n),cal(m)，即（0，n]符合结果的数，然后算出cal(n)-cal(m-1);
#include<stdio.h>
#include<string.h>
int b[100]={0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101};
__int64 pow(int n,int m)
{
int i;
__int64 sum=1;
for(i=1;i<=m;i++){
sum=sum*n;
}
return sum;
}
__int64 cal(__int64 n)
{
int len=0,i,j,sum;
if(n>=0 && n<=9)return n;
/*if(n>=10 && n<=99){ //这里两位数的可以在这里特判一下，时间会减少30ms;
for(i=1;i<=20;i++){
if(n>=b[i]){
sum=i;
}
else break;
}
return sum;
}*/
__int64 x=n,ans=0,t,num;
int a[100];
memset(a,0,sizeof(a));
while(x>0){
a[++len]=x%10;x=x/10;
}
ans=ans+9;
for(i=2;i<=len-1;i++){
ans=ans+9*pow(10,i-2);
}
if(len>2) ans=ans+a[len]*(pow(10,len-2))-pow(10,len-2);
if(a[1]>=a[len]){
if(len>2)
{
ans=ans+(n-a[len]*pow(10,len-1))/10+1;
return ans;
}
else {ans=ans+a[len];return ans;}
}
t=n;
while((t%10)!=a[len]){ //如果最高位和最低位不同，那么先让这个数每次减一，减到最低位等于一开始的最高位，
t--; //然后看最高位的数是否改变，如果没有改变，那么总数加上除了首尾的中间一些数，如57895，取中间为789.
} //如果改变，则直接返回
if(len==2){
ans=ans+a[len]-1;return ans;
}
if(t-a[len]*pow(10,len-1)<0){
return ans;
}
else{
ans=ans+(t-a[len]*pow(10,len-1))/10+1;
return ans;
}
}
int main()
{
__int64 n,m,n1,m1;
int i,j;
//while(scanf("%I64d",&n)!=EOF)
while(scanf("%I64d%I64d",&n,&m)!=EOF)
{
printf("%I64d
",cal(m)-cal(n-1));
//printf("%I64d
",cal(n));
}
return 0;
}
今天又用数位dp的方法做了一下。
思路：先预处理出dp[i][j]表示第i位为j符合要求的数的个数，然后就和普通的数位dp一样了，算的时候算[0,r)的个数，那么最后答案就是solve(m+1)-solve(n)。这里注意pow函数精度不够，所以要自己手写一个。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
#define inf 99999999
#define pi acos(-1.0)
#define maxn 1000050
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef long double ldb;
ll po[25];
void init1()
{
int i,j;
po[0]=1;
for(i=1;i<=18;i++)po[i]=po[i-1]*10;
}
ll dp[24][12];
void init()
{
int i,j,k;
memset(dp,0,sizeof(dp));
for(j=0;j<=9;j++)dp[1][j]=1;
for(i=2;i<=19;i++){
for(j=0;j<=9;j++){
if(j==0){
for(k=0;k<=9;k++){
dp[i][j]+=dp[i-1][k];
}
}
else{
dp[i][j]=po[i-2];
}
}
}
}
ll solve(ll x)
{
int i,j,len=0;
ll t=x;
int wei[20];
while(t){
wei[++len]=t%10;
t/=10;
}
wei[len+1]=0;
if(len==1){
return x;
}
ll sum=0;
for(i=len;i>=1;i--){
if(i==len){
for(j=0;j<wei[i];j++){
sum+=dp[i][j];
}
}
else{
if(i==1){
if(wei[1]>wei[len] ){
sum++;
}
}
else{
for(j=0;j<wei[i];j++){
sum+=po[i-2];
}
}
}
}
return sum;
}
int main()
{
//freopen("o.txt","w",stdout);
ll n,m;
int i,j;
init1();
init();
while(scanf("%I64d%I64d",&n,&m)!=EOF){
printf("%lld
",solve(m+1)-solve(n) );
}
return 0;
}