Codeforces 204A Little Elephant and Interval

http://codeforces.com/problemset/problem/204/A

题意:给定一个【L,R】区间，求这个区间里面首位和末尾相同的数字有多少个

思路:考虑这个问题满足区间加减，我们只考虑【1,n】，考虑位数小于n的位数的时候，我们枚举头尾的数是多少，然后乘上10的某幂次，再考虑位数相等时，从高位往低位走，先考虑头尾数字小于最高位的情况，也像刚才那个随便取，当头尾数字等于最高位时，从高往低走，先算不与这位相等的，走下一步就代表与这位相等。最后要记得判断一下如果原数字头等于尾，答案要加1.

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#define ll long long

ll st[];

ll solve(ll x){

    if (x<=){

       return std::min(9LL,x);

    }

    if (x<=){

       ll t=x/10LL;

       return 9LL+t-+(t<=(x%));

    }

    ll res=;

    int top=;

    while (x){

        st[++top]=x%;

        x/=;

    }

    ll s=;

    for (int i=;i+<=top;i++){

        res+=*s;

        s*=10LL;

    }

    for (int i=;i<st[top];i++){

        res+=s;

    }

    s/=;

    for (int i=top-;i>=;i--)

    {

         for (int j=;j<st[i];j++)

          res+=s;

         s/=;

    }

    if (st[]>=st[top]) res++;

    return res;

}

int main(){

    ll n,m;

    scanf("%I64d%I64d",&n,&m);

    printf("%I64d\n",solve(m)-solve(n-));

}

巴特西

Codeforces 204A Little Elephant and Interval

最新文章

热门文章