题面

解题思路

数位 $DP$

分析

关于数的相关计算，很容易使人想到数位 $DP$，直接记搜即可

如何 $DP$？

众所周知，这里我们只要先把每个数拆成几个数字，然后 $dfs$ 的时候记录 $k,st,op$，分别表示当前是从最低位开始的第 $k$ 位，$st$ 表示当前已枚举的前几位的和，$op$ 表示是否前几位是否达到上界，开数组记忆化即可

Warning

1、传值的时候注意 $long\ long$

2、注意数组 $st$ 那维的大小

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
int num[19],t,nm,T;
LL f[19][191][2],l,r;
inline LL dfs(rint k,rint st,rint op) {
    if(!k) return st;
    if(~f[k][st][op]) return f[k][st][op];
    rint i,t=op?num[k]:9;rll res=0;
    for(i=0;i<=t;i++) res+=dfs(k-1,st+i,op&(i==t));
    return f[k][st][op]=res;
}
inline LL solve(rll c) {
    t=0;while(c) num[++t]=c%10,c/=10;
    memset(f,-1,sizeof(f));//记得初始化为0
    return dfs(t,0,1);
}
int main() {
    scanf("%d",&T);
    while(T--)
        scanf("%lld%lld",&l,&r),l=max(l-1,0ll),//不能为-1
        printf("%lld\n",solve(r)-solve(l));//差分
    return 0;
}

devil.