自动搬运

查看原文

来自洛谷，原作者为

	lonlyn **

搬运于2025-08-24 21:34:07，当前版本为作者最后更新于2017-10-04 18:08:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

乍一看还以为是什么高深的数位dp（应该可以这么做，然而蒟蒻我不会啊orz）。。。。。。

其实，我们可以用简单的找规律方法来解决这个问题啊=￣ω￣=

求L到R的数目不太好想，那我们转化一下，设sum（x）代表从1到x合法的数有多少个。

那么结果就是sum（R）-sum（L-1）。

那么怎么求sum（x）呢？

sum（x）=x （x<=9） （你要是这个再不懂就没办法了。。）

我们可以发现，从10开始，每10个数分一组（10-19,20-29.......230-239......），每一组中有且只有一个合法的数。

这个很好理解，当最高位确定的时候，最低位有0...10十种情况，但只有1种符合。

所以我们就可以再加上一位数的9种情况得到sum（x）=9+x/10 （x>=10）

但仔细一想，这就完了吗？有没有让结果变大了？

当x=2333时是可以的，但当x=3332时，x所处的组（3330-3339）中3333是合法的，但是取不到。

所以当个位<最高位的时候，要记得减去取不到的一种。

#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long 
using namespace std;
ll l,r;
ll ans;
ll getsum(ll x){
    if (x<=9) return x;
    ll a=x%10;
    ll ans=x/10+9;
    ll b=x; while (b>=10) b/=10;
    if (b>a) --ans;
    return ans;
}
int main(){
    scanf("%lld%lld",&l,&r);
    printf("%lld",getsum(r)-getsum(l-1));
    return 0;
}

蒟蒻丑陋的代码附上orz