ACdream 1064 完美数（数位dp）

一时失言乱红尘 2022-06-14 01:58 202阅读 0赞

题目链接：  
[点击我打开题目][Link 1]

题意：在\[L,R\]的正整数区间内，要么包含3 要么包含 8 的不同的整数有多少个？

题解：数位dp。  
设：  
dp\[i\]\[0\]表示既没有3也没有8的，  
dp\[i\]\[1\]表示有3但是没有8的，  
dp\[i\]\[2\]表示有8但是没有3的。

代码：

/*
    * this code is made by LzyRapx
    * Problem: 1064
    * Verdict: Accepted
    * Submission Date: 2017-06-07 09:35:40
    * Time: 188MS
    * Memory: 1664KB
    */
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    //dp[i][0]表示既没有3也没有8的，
    //dp[i][1]表示有3但是没有8的，
    //dp[i][2]表示有8但是没有3的
    int dp[11][4];
    int digit[11];
    int check(int s,int dig)
    {
        if(dig==3)return s|1;
        if(dig==8)return s|2;
        return s;
    }
    int solve(int pos,int s,bool limit)
    {
        if(pos==-1)return s==1 || s==2;
        if(!limit && dp[pos][s] != -1) return dp[pos][s];
        int res = 0;
        int ed = limit ? digit[pos]:9;
        for(int i=0;i<=ed;i++)
        {
        
            res += solve(pos-1,check(s,i),limit && i==ed);
        }
        if(!limit) dp[pos][s] = res;
        return res;
    }
    int cal(int x)
    {
        int cnt = 0;
        while(x)
        {
        
            digit[cnt++] = x%10;
            x/=10;
        }
        return solve(cnt-1,0,1);
    }
    int main()
    {
        int t ;
        cin>>t;
        memset(dp,-1,sizeof(dp));
        while(t--)
        {
        
            int l,r; 
            cin>>l>>r;
            cout<<cal(r)-cal(l-1)<<endl;
        }
        return 0;
    
    }

[Link 1]: http://acdream.info/problem?pid=1064

发表评论取消回复

表情：

评论列表（有 0 条评论，202人围观）

还没有评论，来说两句吧...

相关阅读

相关数位DP - 带49的数

目录题目来源题目描述输入描述输出描述用例题目解析算法源码 -------------------- 题目来源 [20200817-数位DP

迷南。/ 2023年09月23日 17:12/ 0 赞/ 131 阅读

相关数位dp小结

数位dp小结关于limit的问题在数位dp中,limit的作用主要有两个。控制枚举的界限，倘若没有界限，每一位的枚举范围都是0-9. 但如果有界限，

桃扇骨/ 2023年07月03日 07:22/ 0 赞/ 20 阅读

相关 1083 Windy数（数位dp）

1. 问题描述： Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 2 的正整数被称为 Windy 数。Windy 想知道，在 A 和 B 之间，包

不念不忘少年蓝@/ 2022年09月14日 08:43/ 0 赞/ 140 阅读

相关数位dp总结

数位dp的题目一般问的是某个区间内满足某种性质的数的个数，而且对于数位dp的题目一般有都有比较通用的做法，在考虑问题的时候一般以树的形式来考虑： ![watermark_ty

「爱情、让人受尽委屈。」/ 2022年09月14日 03:06/ 0 赞/ 226 阅读

相关 uestc 250 windy数【数位dp】

题目：[uestc 250 windy数][uestc 250 windy] 题意： windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的

迈不过友情╰/ 2022年08月13日 13:37/ 0 赞/ 160 阅读

相关 BZOJ 3530 数数【AC自动机+数位dp】

[\[Sdoi2014\]数数][Sdoi2014] 简单数位dp+简单AC自动机反正数位DP是队友写的 AC自动机要记录两个值，一个是是否为一个串的结束，即不合法

骑猪看日落/ 2022年08月09日 01:53/ 0 赞/ 168 阅读

相关 Bomb（数位Dp）

Bomb Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Oth

布满荆棘的人生/ 2022年08月03日 00:09/ 0 赞/ 202 阅读

相关数位DP

Problem Description 据说，QAQ 的幸运数字是含有 "47" （4 和 7 相邻）的数，例如 47, 147, 247, 470, 471, 2047

小灰灰/ 2022年06月15日 00:40/ 0 赞/ 309 阅读

相关 ACdream 1064 完美数（数位dp）

题目链接： [点击我打开题目][Link 1] 题意：在\[L,R\]的正整数区间内，要么包含3 要么包含 8 的不同的整数有多少个？题解：数位dp。设：

一时失言乱红尘/ 2022年06月14日 01:58/ 0 赞/ 202 阅读

相关 ACdream 1154 Lowbit Sum （数位dp）

题目链接： [ACdream 1154][] 题解：数位dp。这题可以加深对 lowbit 的理解啊。你打个表就可以发现规律了。当 n 为偶数时，dp\

Dear 丶/ 2022年06月13日 00:52/ 0 赞/ 139 阅读