1 条题解
-
0
手机号码
#include <bits/stdc++.h> #define int long long using namespace std; int L, R; int d[15], dlen; // d[dlen]~d[1] int dp[15][2][2][2][10][10]; // dp[pos][f4][f8][f3][pre][prepre] // 返回方案数量 // pos: 填到了哪一位 // limit: 之前有没有顶到上限 // f4/8: 之前有没有出现过 4/8 // f3: 之前是否完成了三连 // pre: 前一位是谁 // prepre: 前两位是谁 int dfs(int pos, bool limit, bool f4, bool f8, bool f3, int pre, int prepre) { // 边界 if (pos == 0) { if (f3) return 1; else return 0; } // 记忆化 if (!limit && dp[pos][f4][f8][f3][pre][prepre] != -1) return dp[pos][f4][f8][f3][pre][prepre]; // 当前这一位怎么选 int up = limit ? d[pos] : 9; int down = (pos == 11) ? 1 : 0; int sum = 0; // 记录所有情况的方案之和 for (int now = down; now <= up; now++) { // 尝试在 pos 这一位填 now if (f4 && now == 8) continue; if (f8 && now == 4) continue; sum += dfs(pos - 1, limit && now == d[pos], f4 || now == 4, f8 || now == 8, f3 || (now == pre && pre == prepre), now, pre); } if (!limit) dp[pos][f4][f8][f3][pre][prepre] = sum; return sum; } // 计算 0~x 不含有不吉利成分的数的数量 int cal(int x) { if (x < 10000000000) return 0; dlen = 0; for (int i = x; i != 0; i /= 10) d[++dlen] = i % 10; return dfs(dlen, true, false, false, false, -1, -1); } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> L >> R; memset(dp, -1, sizeof(dp)); cout << cal(R) - cal(L - 1) << "\n"; return 0; }
- 1
信息
- ID
- 1206
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 19
- 已通过
- 19
- 上传者