A. Little Elephant and Interval

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.

Input

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.

Output

On a single line print a single integer — the answer to the problem.

Sample test(s)

input

2 47

output

input

47 1024

output

看了其他博客都是数位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\n",cal(m)-cal(n-1));

		//printf("%I64d\n",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\n",solve(m+1)-solve(n) );

    }

    return 0;

}

巴特西

A. Little Elephant and Interval

最新文章

热门文章