题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4521
dfs真好用~
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=15; int dg[N]; ll l,r,dp[N][5][N][2][2][2]; ll dfs(int p,int len,int lst,bool p0,bool p1,bool ok,bool fx) { if(!p){return ok&(!(p0&p1));} if(!fx&&dp[p][len][lst][p0][p1][ok]!=-1)return dp[p][len][lst][p0][p1][ok]; int st=0;if(p==11)st=1; int end=9;if(fx)end=dg[p]; ll ret=0; for(int i=st;i<=end;i++) { int lenn=1;if(i==lst)lenn=len+1; if(lenn>3)lenn=3; ret+=dfs(p-1,lenn,i,p0|(i==4),p1|(i==8),ok|(lenn==3),fx&(i==dg[p])); } if(!fx)dp[p][len][lst][p0][p1][ok]=ret; return ret; } ll calc(ll x) { if(x<1e10)return 0; for(int i=1;i<=11;i++)dg[i]=x%10,x/=10; memset(dp,-1,sizeof dp); return dfs(11,0,0,0,0,0,1); } int main() { scanf("%lld%lld",&l,&r); printf("%lld ",calc(r)-calc(l-1)); return 0; }