数位dp.
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0); void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } int dp[15][5],t[15]; void pre() { memset(dp,0,sizeof dp); dp[0][0]=1; // get时要× dp[1][0]=8; // 0 1 2 4 5 6 7 9 dp[1][1]=1; // 3 dp[1][2]=1; // 8 for(int i=2;i<=10;i++) { dp[i][0]=8*dp[i-1][0]; dp[i][1]=dp[i-1][0]+9*dp[i-1][1]; dp[i][2]=dp[i-1][0]+9*dp[i-1][2]; } } int get(int x) { int sz=0; while(x) t[sz++]=x%10, x=x/10; for(int i=sz;i>=1;i--) t[i]=t[i-1]; int res=0; bool san=0,ba=0; for(int i=sz;i>=1;i--) { //该位可以放 0 1 2 3 4....t[i]-1 if(san==0&&ba==0) { //放 0 1 2 if(t[i]<=3) res=res+ dp[i-1][1]*t[i]+ dp[i-1][2]*t[i]; //放 0 1 2 3 4 5 6 7 else if(t[i]<=8) res=res+ dp[i-1][0]+ dp[i-1][1]*t[i]+ dp[i-1][2]*(t[i]-1); //放 0 1 2 3 4 5 6 7 8 else if(t[i]==9) res=res+ dp[i-1][0]+ dp[i-1][0]+ dp[i-1][1]*(t[i]-1)+ dp[i-1][2]*(t[i]-1); if(t[i]==3) san=1; if(t[i]==8) ba=1; if(san==1&&ba==1) return res; continue; } int id,limit; if(san==0) id=2,limit=3; else id=1,limit=8; //放 0 1 2 .. limit-1 if(t[i]<=limit) res=res+ dp[i-1][0]*t[i]+ dp[i-1][id]*t[i]; //放 0 1 2 .. t[i]-1 else res=res+ dp[i-1][0]*(t[i]-1)+ dp[i-1][id]*(t[i]-1); if(t[i]==3) san=1; if(t[i]==8) ba=1; if(san==1&&ba==1) return res; } return res; } int main() { pre(); int T,L,R; scanf("%d",&T); while(T--) { scanf("%d%d",&L,&R); printf("%d ",get(R+1)-get(L)); } return 0; }