hdu 3652 数位dp

妖狐艹你老母 2022-08-05 10:22 162阅读 0赞

直接套的模板

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=100010;
    
    int bit[20];
    int dp[22][22][3];
    
    int dfs(int pos,int mod,int lim,int flag)
    {
        if(pos==0) return mod==0 && flag==2;
    
        if(!lim && dp[pos][mod][flag]!=-1) return dp[pos][mod][flag];
        int mx=lim? bit[pos] : 9;
        int cnt=0;
    
        for(int i=0;i<=mx;i++)
        {
            int t=flag;
            if(flag==1 && i==3) flag=2;
            else if(flag==1 && i!=1) flag=0;
            else if(flag==0 && i==1) flag=1;
            int tmp=(mod*10+i)%13;
            cnt += dfs(pos-1,tmp,lim && i==mx,flag);
            flag=t;
        }
    
        if(!lim) return dp[pos][mod][flag]=cnt;
        return cnt;
    }
    
    int solve(int n)
    {
        mem(bit,0);
        mem(dp,-1);
        int tmp=n;
        int cnt=1;
        while(tmp)
        {
            bit[cnt++]=tmp%10;
            tmp/=10;
        }
        return dfs(cnt-1,0,1,0);
    }
    
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
    
            printf("%d\n",solve(n));
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 3652-B-number【数位DP】

题意：让你求\[1, n\] 中包含子串“13” ，并且能够被13整除的数量。思路：dp\[i\]\[j\]\[k\]\[t\] ,表示第i位前缀为j且模数为k时的答案，

桃扇骨/ 2023年06月01日 11:19/ 0 赞/ 9 阅读

相关 HDU 5787 数位dp

K-wolf Number Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (

港控/mmm°/ 2022年09月25日 05:16/ 0 赞/ 140 阅读

相关 HDU 2089-不要62(数位DP)

不要62 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

蔚落/ 2022年08月22日 13:22/ 0 赞/ 151 阅读

相关 hdu 3555 bomb 数位dp

基础数位dp，作为入门题目；题意很明确，找出1-n范围内不含49的数字。n的范围为1~n^63-1. dp\[i\]\[0\]长度为i的数不含49的数的个数

╰+哭是因爲堅強的太久メ/ 2022年08月13日 17:58/ 0 赞/ 161 阅读

相关 hdu 3652 数位dp

直接套的模板 include<bitset> include<map> include<vector> include<cstdio>

妖狐艹你老母/ 2022年08月05日 10:22/ 0 赞/ 163 阅读

相关 HDU-3709 Balanced Number(数位DP)

超、凢脫俗/ 2022年06月09日 00:27/ 0 赞/ 175 阅读

相关【数位DP】B-number HDU - 3652

Think: 1知识点：数位DP 2题意：输入r，判断\[1, r\]区间内有多少个“wqb-number”，“wqb-number”的定义为数位内含有13且可以被13

朱雀/ 2022年06月08日 13:56/ 0 赞/ 163 阅读

相关【数位DP】Bomb HDU - 3555

Think: 1知识点：数位DP 2题意：询问区间\[1, n\]内有多少个数的数位中含有49(eg:49,149,249,1491等) [Bomb HDU - 35

àì夳堔傛蜴生んèń/ 2022年06月08日 07:16/ 0 赞/ 165 阅读

相关 hdu 4722（动态规划-数位dp）

问题描述: If we sum up every digit of a number and the result can be exactly divided by 10,

川长思鸟来/ 2022年05月31日 12:25/ 0 赞/ 224 阅读

相关【hdu2089】不要62 [数位dp]

![1591261-20190611115344981-1062772141.jpg][]就搞不懂为什么我多预处理了几位就会炸然后放mzoj上还非要预处理8位真的要叫我去

红太狼/ 2021年11月17日 15:44/ 0 赞/ 282 阅读