基础题复习
这次用了dfs写法，感觉比较好#include#include #include #include using namespace std;typedef long long ll;const int N=10;inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int r, l, a[N], len;int f[N][2];int dfs(int d, bool flag, bool sky) { //printf("dfs %d %d %d\n",d,flag,sky); if(d==0) return 1; if(!sky && f[d][flag]!=-1) return f[d][flag]; int now=0, lim = sky ? a[d] : 9; for(int i=0; i<=lim; i++) { if(i==4 || (flag && i==2)) continue; now += dfs(d-1, i==6, i==lim && sky); } return sky ? now : f[d][flag]=now;}int cal(int n) { len=0; while(n) a[++len]=n%10, n/=10; return dfs(len, 0, 1);}int main() { freopen("in","r",stdin); memset(f, -1, sizeof(f)); while(true) { l=read(); r=read(); if(l==0 && r==0) break; printf("%d\n", cal(r)-cal(l-1)); }}
#include#include #include #include using namespace std;typedef long long ll;const int N=15;inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int l, r, a[N], len;int f[N][N];int dfs(int d, int last, bool zero, bool sky) { //printf("Dfs %d %d %d\n",d,last,sky); if(d==0) return 1; if(!sky && !zero && f[d][last]!=-1) return f[d][last]; int now=0, lim = sky ? a[d] : 9; //printf("lim %d\n",lim); for(int i=0; i<=lim; i++) if(zero || abs(i-last)>=2) now += dfs(d-1, i, zero && i==0, sky && i==lim); return (sky||zero) ? now : f[d][last]=now;}int cal(int n) { len=0; while(n) a[++len]=n%10, n/=10; return dfs(len, 0, 1, 1);}int main() { freopen("in","r",stdin); memset(f,-1,sizeof(f)); //for(int i=0; i<=50; i+=10) printf("hi %d %d \n",i,cal(i)); //printf("hi %d %d\n",24,cal(24)); l=read(); r=read(); printf("%d\n", cal(r)-cal(l-1));}