ACdream 1064 完美数（数位dp）

一时失言乱红尘 2022-06-14 01:58 219阅读 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 条评论，219人围观）

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

相关阅读

相关 51nod1230 幸运数 (数位dp）

[1230 幸运数][1230] ![ok.png][] 题目来源： [HackerRank][] [1230]: http://www.51nod.com/o

柔光的暖阳◎/ 2024年02月18日 18:31/ 0 赞/ 5 阅读

相关数位DP - 带49的数

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

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

相关数位DP - 带3的数

目录题目来源题目描述输入描述输出描述用例题目解析算法源码 -------------------- 题目来源 [数位DP\_哔哩哔哩\_b

雨点打透心脏的1/2处/ 2023年09月23日 17:09/ 0 赞/ 63 阅读

相关 1083 Windy数（数位dp）

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

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

相关 uestc 250 windy数【数位dp】

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

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

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

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

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

相关数位DP

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

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

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

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

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

相关 ACdream 1025 Transform (dp)

题目链接： [ACdream 1025][] 题意：让你求从a转换到b的最少步数，a可以转化到a\+x,x是a的因子。题解： dp题。转换方程很容易推

Myth丶恋晨/ 2022年06月14日 00:50/ 0 赞/ 165 阅读

相关 ACdream 1154 Lowbit Sum （数位dp）

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

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