Description
定义一个数字是好数,当且仅当它的十进制表示下有不超过 $ 3 $ 个数字 $ 1 sim 9 $。给定 $ [l,r] $,问有多少个 $ x $ 使得 $ l le x le r $,且 $ x $ 是好数。$ 1 le l_i le r_i le 10^{18} $
Solution
常规的数位 dp,设 (f[i][j]) 表示前 (i) 个数位,有 (j) 个非零数位时,有多少个数满足条件
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[20],f[20][5];
int dfs(int pos,int num,int lim) {
if(pos<0) return 1;
if(lim==0 && f[pos][num]>=0) return f[pos][num];
int up=lim?a[pos]:9;
int ans=0;
for(int i=0;i<=up;i++) {
if(i==0) ans+=dfs(pos-1,num,lim&&a[pos]==i);
else if(num<3) ans+=dfs(pos-1,num+1,lim&&a[pos]==i);
}
if(lim==0) f[pos][num]=ans;
return ans;
}
int calc(int x) {
int tot=0;
while(x) {
a[tot++]=x%10;
x/=10;
}
return dfs(tot-1,0,1);
}
signed main() {
int T;
cin>>T;
memset(f,-1,sizeof f);
while(T--) {
int l,r;
cin>>l>>r;
cout<<calc(r)-calc(l-1)<<endl;
}
}