本文共 1018 字，大约阅读时间需要 3 分钟。
题意：
就是在l到r之间有多少个数满足 没有包含62相连的 并且不含有4
#include #include #include #include #include #include #include #include #include using namespace std;#define INF 0x3f3f3f3f#define LL long long#define N 106#define Lson rood<<1#define Rson rood<<1|1LL dp[20][20],d[20];LL dfs(int now,int up,int fp){ if(now==1) return 1; if(!fp&&dp[now][up]!=-1) return dp[now][up]; LL ans=0; int ma=fp?d[now-1]:9; for(int i=0;i<=ma;i++) { if(i==4||(up==6&&i==2)) continue; ans+=dfs(now-1,i,fp&&i==ma); } if(!fp&&dp[now][up]==-1) dp[now][up]=ans; return ans;}LL calc(LL x){ if(x==0) return 1; LL xxx=x; int len=0; while(xxx) { d[++len]=xxx%10; xxx/=10; } LL sum=0; for(int i=0;i<=d[len];i++) { if(i!=4) sum+=dfs(len,i,i==d[len]); } return sum;}int main(){ LL l,r; memset(dp,-1,sizeof(dp)); while(scanf("%lld%lld",&l,&r),l+r) { printf("%lld\n",calc(r)-calc(l-1)); } return 0;}
转载于:https://www.cnblogs.com/a719525932/p/7759971.html