2 条题解
-
0
推荐：
/* 这题推荐使用记忆化搜索，因为要选的两个条件中有重合的数 且用普通dp不好递推，但记搜需要注意边界和时间限制*/ #include<bits/stdc++.h>//by: hansang.Patto d'Acciaio using namespace std; typedef long long LL; const int N=25; LL f[N][2], a[N]; LL dfs(int x, bool b, bool lim){ //若b为1代表上一个数为6 if(x==0) return 1; if(!lim && f[x][ b ]!=-1) return f[x][ b ]; int up=lim? a[x]: 9; //到了上界最大值只能为a[i] LL ans=0; for(int i=0; i<=up; i++) if(i!=4){ if(b && i==2) continue; //上一个数为6则当前i!=2 ans+=dfs(x-1, (i==6), lim && (i==up)); //注意lim } if(!lim) f[x][ b ]=ans; //若lim为1则是上界，统计不完全不能记录 return ans; } LL calc(LL x){ int len=0; while(x>0) a[++len]=x%10, x/=10; return dfs(len, 0, 1); //lim是有没有到上界的标志，初始要为1 } int main(){ //freopen("a.in", "r", stdin); for(int i=0; i<=20; i++) for(int j=0; j<=1; j++) f[i][j]=-1; int n, m; while(scanf("%d%d", &n, &m)!=EOF){ if(n==0 && m==0) break; LL x=calc(m), y=calc(n-1); printf("%lld\n", x-y); } return 0; }
dp://也放一个dp的版本 #include<bits/stdc++.h>//by: hansang.Patto d'Acciaio using namespace std; typedef long long LL; const int N=25; LL f[N][10][10]; int a[N]; LL calc(int x){ int len=0, last1=0, last2=0; LL ans=0, c=1; if(x==0) return 0; while(x>0) a[++len]=x%10, x/=10; for(int i=len; i>=1; i--){ if(last1==4) break; if(last2==6 && last1==2) break; for(int j=(i==len? 1: 0); j<=a[i]-1; j++) if(j!=4 && !(last1==6 && j==2)) for(int k=0; k<=9; k++) if(k!=4) ans+=f[i][j][k]; last2=last1; last1=a[i]; } for(int i=len-1; i>=1; i--) for(int j=1; j<=9; j++) if(j!=4) for(int k=0; k<=9; k++) if(k!=4) ans+=f[i][j][k]; for(int i=1; i<=len; i++) if(a[i]==4 || (i!=1 && (a[i-1]==2 && a[i]==6))) {c=0; break;} return ans+c; } int main(){ //freopen("a.in", "r", stdin); int n, m; memset(f, 0, sizeof(f)); for(int i=0; i<=9; i++) if(i!=4) f[1][i][i]=1; for(int t=2; t<=20; t++) for(int di=0; di<=9; di++) if(di!=4) for(int dj=0; dj<=9; dj++) if(dj!=4) for(int k=0; k<=9; k++) if(k!=4) if(!(di==6 && dj==2)) f[t][di][k]+=f[t-1][dj][k]; while(scanf("%d%d", &n, &m)!=EOF){ if(n==0 && m==0) break; LL x=calc(m), y=calc(n-1); printf("%lld\n", x-y); } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:58:36
推荐：
/* 这题推荐使用记忆化搜索，因为要选的两个条件中有重合的数 且用普通dp不好递推，但记搜需要注意边界和时间限制*/ #include<bits/stdc++.h>//by: hansang.Patto d'Acciaio using namespace std; typedef long long LL; const int N=25; LL f[N][2], a[N]; LL dfs(int x, bool b, bool lim){ //若b为1代表上一个数为6 if(x==0) return 1; if(!lim && f[x][ b ]!=-1) return f[x][ b ]; int up=lim? a[x]: 9; //到了上界最大值只能为a[i] LL ans=0; for(int i=0; i<=up; i++) if(i!=4){ if(b && i==2) continue; //上一个数为6则当前i!=2 ans+=dfs(x-1, (i==6), lim && (i==up)); //注意lim } if(!lim) f[x][ b ]=ans; //若lim为1则是上界，统计不完全不能记录 return ans; } LL calc(LL x){ int len=0; while(x>0) a[++len]=x%10, x/=10; return dfs(len, 0, 1); //lim是有没有到上界的标志，初始要为1 } int main(){ //freopen("a.in", "r", stdin); for(int i=0; i<=20; i++) for(int j=0; j<=1; j++) f[i][j]=-1; int n, m; while(scanf("%d%d", &n, &m)!=EOF){ if(n==0 && m==0) break; LL x=calc(m), y=calc(n-1); printf("%lld\n", x-y); } return 0; }
dp://也放一个dp的版本 #include<bits/stdc++.h>//by: hansang.Patto d'Acciaio using namespace std; typedef long long LL; const int N=25; LL f[N][10][10]; int a[N]; LL calc(int x){ int len=0, last1=0, last2=0; LL ans=0, c=1; if(x==0) return 0; while(x>0) a[++len]=x%10, x/=10; for(int i=len; i>=1; i--){ if(last1==4) break; if(last2==6 && last1==2) break; for(int j=(i==len? 1: 0); j<=a[i]-1; j++) if(j!=4 && !(last1==6 && j==2)) for(int k=0; k<=9; k++) if(k!=4) ans+=f[i][j][k]; last2=last1; last1=a[i]; } for(int i=len-1; i>=1; i--) for(int j=1; j<=9; j++) if(j!=4) for(int k=0; k<=9; k++) if(k!=4) ans+=f[i][j][k]; for(int i=1; i<=len; i++) if(a[i]==4 || (i!=1 && (a[i-1]==2 && a[i]==6))) {c=0; break;} return ans+c; } int main(){ //freopen("a.in", "r", stdin); int n, m; memset(f, 0, sizeof(f)); for(int i=0; i<=9; i++) if(i!=4) f[1][i][i]=1; for(int t=2; t<=20; t++) for(int di=0; di<=9; di++) if(di!=4) for(int dj=0; dj<=9; dj++) if(dj!=4) for(int k=0; k<=9; k++) if(k!=4) if(!(di==6 && dj==2)) f[t][di][k]+=f[t-1][dj][k]; while(scanf("%d%d", &n, &m)!=EOF){ if(n==0 && m==0) break; LL x=calc(m), y=calc(n-1); printf("%lld\n", x-y); } return 0; }
- 1
