周赛的最后一题太难啦,我居然学了一整个下午的数位DP,我真的好蠢好蠢。

上一次做这道题还是大一,搜了一下记录真是感慨万千TAT。当时一路刷着水题,遇到了这题过不了,搜了题解又懒得看,于是一直扔在这里。如果当时再努力一点点,现在会不会轻松许多TAT。

少壮不努力,老大徒伤悲。

2089. 不要62

Problem Description

杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input

输入的都是整数对n、m(0<n≤m<1000000),如果遇到都是0的整数对,则输入结束。

Output

对于每个整数对,输出一个不含有不吉利数字的统计个数,该数值占一行位置。

Sample Input

1 100
0 0

Sample Output

80

题意

给出 ab ,求区间 [a, b] 内不含有 4 且不含有 62 的数字的数量。

思路

【转化问题】

若将区间 [0, x] 的答案记为 f(x),那么区间 [a, b] 的答案应为 f(b) - f(a-1)

【状态表示】

需要两个数组,一个是 digit[MAXN],用来从低位向高位存储每个位上的数字。
另一个就是 dp[MAXN][2],初始化为 -1

  • dp[len][0] 表示不含 462 的前提下,剩余长度为 len ,首位不为 6 的个数。
  • dp[len][1] 表示不含 462 的前提下,剩余长度为 len ,首位为 6 的个数。

其中 MAXN 是十进制数的最大位数,这题取 8 就ok。

【记忆化搜索】

这题应该还可以用朴素的DP来做,然而我看zz周赛最后一题的代码用的记忆化搜索,于是去学了记忆化搜索,似乎记忆化搜索更好理解一些。

所谓“记忆化”,要搞清楚是要记什么。我花了一下午才搞清楚qwq。记忆化的内容就是dp数组。dp[x][b]在这个过程中是要被求很多遍的,所以第一次求出来之后就将结果记录在dp数组里,下次求到的时候,就能直接返回结果了。

我感觉代码其实很好懂,只是有一些小细节很让我困扰,有朝一日我也成为了写中文注释的人。

// len=当前要求的数字的长度,例如如果要求的是f(100),初始传入len=3
// state=前一位是否为6,初始值为false
// fp=是否为临界值,以f(100)为例,临界值的定义是:len=3, fpmax=100; len=2, fpmax=99; len=1, fpmax=9。
int dfs(int len, bool state, bool fp) {
    // 一位且不为4的数字dfs的结果,直接返回1
    if(len == 0) return 1; 
    // !fp之后再解释qwq。dp数组不为-1说明求过了,直接返回。
    if(!fp && dp[len][state] != -1) return dp[len][state];

    // fpmax就是临界值的大小,例如如果要求的是f(100),fpmax=1
    // 但是当这一位选择0时,下一位fpmax=9
    int ret = 0, fpmax = fp ? digit[len] : 9;
    // 遍历当前位 [0, ...fpmax]
    for(int i=0; i<=fpmax; i++) {
        // 如果这一位为4,或者前一位为6并请求这一位为2,那么跳过
        if(i == 4 || (state && i == 2)) continue;
        // 否则的继续dfs答案,三个参数很easy
        ret += dfs(len-1, i==6, fp && i==fpmax);
    }
    // 记忆化,这个!fp也下面解释qwq
    if(!fp) dp[len][state] = ret;
    return ret;
}

好了现在该解释困扰我一下午的!fp了……其实从定义理解就很好,例如刚才写到的:

它应该存储的是一个完整的长度为len的数字的所有可能中符合要求的情况。

例如 dp[2][0] ,它就应该存储区间 [10, 99] 中所有不包含 462 ,首位不为 6 的个数。

如果不写!fp,那么比如说现在要求 f(111) ,那么枚举第一位,第一位为 0 的时候没有问题。如果第一位为 1,那么剩下的其实是求区间 [1, 11] 中满足要求的情况,但是不写!fp会直接返回 [10, 99] 的答案。

代码

#include <bits/stdc++.h>
using namespace std;

int dp[8][2];
int digit[8];

int dfs(int len, bool state, bool fp) {
    if(len == 0) return 1;
    if(!fp && dp[len][state] != -1) return dp[len][state];

    int ret = 0, fpmax = fp ? digit[len] : 9;
    for(int i=0; i<=fpmax; i++) {
        if(i == 4 || (state && i == 2)) continue;
        ret += dfs(len-1, i==6, fp && i==fpmax);
    }

    if(!fp) dp[len][state] = ret;
    return ret;
}

int f(int n) {
    int len = 0;
    while(n) {
        digit[++len] = n % 10;
        n /= 10;
    }
    return dfs(len, false, true);
}

int main() {
    // freopen("in.txt", "r", stdin);
    int a, b;
    memset(dp, -1, sizeof(dp));
    while(scanf("%d %d", &a, &b), a||b) printf("%d\n", f(b)-f(a-1));
    return 0;
}
最后修改:2020 年 03 月 29 日 09 : 16 PM
如果觉得我的文章对你有用,请随意赞赏