题目大意
求 [l,r] 内满足以下条件的数的个数:
- 有三个及以上连着的相同数字
- 4 和 8 不同时存在
1×1010⩽l,r<1×1011
题目链接
【CQOI 2016】手机号码
题解
数位 DP。
计算小于等于一个数的答案,最终答案相减。
DP 时,记 f(n,limit,last,equal,last,has4,has8) 为还剩 n 位(从高位开始)、当前位最大值为 limit 、上一位为 last 、上一位与再上一位是否相等、是否有 4 、是否有 8 时的答案。转移时,枚举每一位,如果同时有 4 和 8 就跳过,否则去考虑下一位。代码中,limit=10 表示这一位与接下来的位都没有限制。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| #include <cstdio> #include <cstring> #include <algorithm> const int LEN = 11; const long long MIN = 1e10; int a[LEN]; long long f[LEN][11][10][2][2][2][2]; bool calced[LEN][11][10][2][2][2][2]; long long dp(int n, int limit, int last, bool equal, bool flag, bool has4, bool has8) { long long &curr = f[n][limit][last][equal][flag][has4][has8]; if (calced[n][limit][last][equal][flag][has4][has8]) return curr; calced[n][limit][last][equal][flag][has4][has8] = true; curr = 0; if (n == 1) { for (int i = 0; i <= std::min(limit, 9); i++) { if ((has4 && has8) || (i == 4 && has8) || (i == 8 && has4)) continue; if (flag || (equal && i == last)) curr++; } } else { int next = a[LEN - n + 1]; for (int i = 0; i <= std::min(limit, 9); i++) { if ((has4 && has8) || (i == 4 && has8) || (i == 8 && has4)) continue; int temp = i < limit || limit == 10 ? 10 : next; curr += dp(n - 1, temp, i, i == last, flag || (equal && i == last), has4 || (i == 4), has8 || (i == 8)); } } return curr; } long long calc(long long x) { if (x < MIN) return 0; for (int i = LEN - 1; ~i; i--) a[i] = x % 10, x /= 10; memset(calced, false, sizeof (calced)); long long res = 0; for (int i = 1; i <= a[0]; i++) { int limit = i == a[0] ? a[1] : 10; res += dp(LEN - 1, limit, i, false, false, i == 4, i == 8); } return res; } int main() { long long l, r; scanf("%lld %lld", &l, &r); printf("%lld\n", calc(r) - calc(l - 1)); return 0; }
|