本文共 1701 字，大约阅读时间需要 5 分钟。
数位dp.
#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include 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\n",get(R+1)-get(L)); } return 0;}
转载于:https://www.cnblogs.com/zufezzt/p/5782046.html