首页 > 代码库 > 不要62
不要62
题目链接
- 题意:
求出a到b之间 1)不含有连续的62 2)不含有4
的数的个数 - 分析:
两种状态,记录62。4直接判断即可
LL f[100][2], bits[100]; LL dfs(int pos, int s, bool lmt) { if (pos == -1) return 1; if (!lmt && ~f[pos][s]) return f[pos][s]; int u = lmt ? bits[pos] : 9; LL ret = 0; for (int i = 0; i <= u; i++) { if ((s == 1 && i == 2) || i == 4) continue; int nxt = 0; if (i == 6) nxt = 1; ret += dfs(pos - 1, nxt, lmt && i == u); } return lmt ? ret : f[pos][s] = ret; } LL calc(LL n) { CLR(f, -1); LL len = 0; while (n) { bits[len++] = n % 10; n /= 10; } return dfs(len - 1, 0, true); } int main() { //freopen("0.txt", "r", stdin); LL a, b; while (cin >> a >> b && a) cout << calc(b) - calc(a - 1) << endl; return 0; }
不要62
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。