BZOJ 4521 - [Cqoi2016]手机号码

#数位dp
Published on 2016-04-27

题目地址

题目描述

人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素，从号段中选取含有某些特征的号码单独出售。为了便于前期规划，运营商希望开发一个工具来自动统计号段中满足特征的号码数量。
工具需要检测的号码特征有两个：号码中要出现至少 33 个相邻的相同数字，号码中不能同时出现 88 和 44。号码必须同时包含两个特征才满足条件。满足条件的号码例如：1300098872113000988721 、2333333333323333333333、1444410100014444101000。而不满足条件的号码例如：10154000801015400080、1001001202210010012022。
手机号码一定是 1111 位数，且不含前导的 00。工具接收两个数 LL 和 RR，自动统计出 [L,R][L,R] 区间
内所有满足条件的号码数量。LL 和 RR 也是 1111 位的手机号码。

分析

明显的数位DP，如果我们设 F(i)F(i) 为 [10000000000,i][10000000000, i] 中满足的个数，judge(i)judge(i) 为 ii 是否满足，那么 [l,r][l, r] 中满足的手机号个数就是：

F(r)−F(l)+judge(l)F(r) - F(l) + judge(l)

求 FF，使用数位DP，状态为:

f[i][j][k][satisfy][four][eight][flag]f[i][j][k][satisfy][four][eight][flag]

表示处理到 ii 位，当前位上是 jj，jj 已经出现了 kk 次，是否满足连续出现 33 个 satisfysatisfy，是否出现过 44 fourfour，是否出现过 88 eighteight，前面的位数是否贴着数的上界 flagflag，的状态总数。
那么使用刷表转移即可。
单次 DP 复杂度：O(104∗24)O(10^4 * 2^4)

代码

//  Created by Sengxian on 4/27/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 4521 数位dp
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <vector>
#include <string>
using namespace std;

typedef long long ll;
const int maxn = 11, maxd = 10;
ll dp[maxn][maxd][maxn][2][2][2][2];
string l, r;

ll Dp(const string &s) {
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= s[0] - '0'; ++i)
        dp[0][i][1][0][i == 4][i == 8][i == s[0] - '0'] = 1;
    for (int i = 0; i < maxn - 1; ++i) //第几位
        for (int j = 0; j < maxd; ++j) //这一位上的数是几
            for (int k = 1; k <= i + 1; ++k) //已经重复了几次
                for (int f = k >= 3; f < 2; ++f) //是否已经满足重复
                    for (int a = 0; a < 2; ++a) //4是否出现
                        for (int b = 0; b < 2; ++b) //8是否出现
                            for (int t = 0; t < 2; ++t) { //是否贴上界
                                int lim = t == 1 ? s[i + 1] - '0' : maxd - 1;
                                for (int d = 0; d <= lim; ++d) {
                                    int _k = d == j ? k + 1 : 1;
                                    dp[i + 1][d][_k][f | (_k >= 3)][a | (d == 4)][b | (d == 8)][t && d == lim] += dp[i][j][k][f][a][b][t];
                                }
                            }
    ll ans = 0;
    for (int j = 0; j < maxd; ++j) //这一位
        for (int k = 0; k < maxn; ++k) //已经重复了几次
                for (int a = 0; a < 2; ++a) //4是否出现
                    for (int b = 0; b < 2; ++b) //8是否出现
                        for (int t = 0; t < 2; ++t)  //是否贴上界
                            if (a + b <= 1) ans += dp[maxn - 1][j][k][1][a][b][t];
    return ans;
}

bool judge(const string &s) {
    bool four = false, eight = false, three = false;
    int cnt = 0, last = -1;
    for (int i = 0; i < s.length(); ++i) {
        int d = s[i] - '0';
        if (d == last) cnt++;
        else cnt = 1, last = d;
        four |= d == 4;
        eight |= d == 8;
        three |= cnt >= 3;
    }
    return (four + eight <= 1) && three;
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("test.in", "r", stdin);
    #endif
    cin >> l >> r;
    cout << Dp(r) - Dp(l) + judge(l) << endl;
    return 0;
}
BZOJ 2303 - [Apio2011]方格染色