首页 > 代码库 > Bomb
Bomb
题目链接
- 题意:
求1-x中出现连续的49的数有多少个(注意要用long long) - 分析:
计算不包括连续的49或者计算包括连续的49。两种方法都差不多,简单的数位DP
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 == 9) continue; int nxt = 0; if (i == 4) 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); int T; RI(T); FE(kase, 1, T) { LL n; cin >> n; cout << 1 + n - calc(n) << endl; } return 0; }
Bomb
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。