学做烘焙的网站,宝塔建设网站域名进不去,重庆建站网站建设平台,校园网站设计Acwing 1085. 不要62
题意#xff1a;
问[n,m]这些数中有多少数不包含4#xff0c;且不包含连续的62
题解#xff1a;
经典数位dp#xff0c;分析过程以前的数位dp博客有写 Acwing 1082. 数字游戏
代码#xff1a;
#includebits/stdc.h
#define debug(a,b) …Acwing 1085. 不要62
题意
问[n,m]这些数中有多少数不包含4且不包含连续的62
题解
经典数位dp分析过程以前的数位dp博客有写 Acwing 1082. 数字游戏
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn20;
int f[maxn][maxn];
void init(){for(int i0;i9;i)if(i!4)f[1][i]1;for(int i2;imaxn;i){for(int j0;j9;j){for(int k0;k9;k){if(j6k2)continue;if(j4||k4)continue;f[i][j]f[i-1][k];}}}
}
int solve(int x){if(!x)return 1;vectorintvec;int tot0;int last0;while(x)vec.push_back(x%10),x/10;for(int ivec.size()-1;i0;i--){int nvec[i];for(int j0;jn;j){if(j4)continue;if(last6j2)continue;totf[i1][j];}if(n4)break;if(last6n2)break;lastn;if(!i)tot;}return tot;
}
int main()
{int n,m;init();while(cinnm){if(n0m0)break;coutsolve(m)-solve(n-1)endl;}return 0;
}
