洛谷 P2602 [ZJOI2010]数字计数

冷不防 2023-06-04 07:59 62阅读 0赞

![1596060-20190721202628330-676586515.png][]

***又是一道数位DP，不过做题多了也就发现套路了，这道题注意对前导0的判断以及dp状态的设计——dp\[i\]\[j\] 当前的位数，统计的数字之和。***

#include<cstdio>
    #include<cstring> 
    using namespace std;
    const int maxn=1e6+7;
    const int N=550;
    long long dp[N][N];
    int aaa[maxn];
    long long a,b;
    long long dfs(int pos,int sum,int num,bool lead,bool limit){
        if(pos==-1) return sum;
        if(!limit&&dp[pos][sum]!=-1&&lead) return dp[pos][sum];
        int up=limit?aaa[pos]:9;
        long long tmp=0;
        for(int i=0;i<=up;i++){
            tmp+=dfs(pos-1,sum+((lead||i)&&(i==num)),num,lead||i,limit&&i==aaa[pos]);
        }
        if(!limit&&lead) dp[pos][sum]=tmp;
        return tmp;
    }
    long long work(long long x,int now){
        int pos=0;
        while(x){
            aaa[pos++]=x%10;
            x/=10;
        }
        memset(dp,-1,sizeof(dp));
        return dfs(pos-1,0,now,0,1);
    }
    int main(){
        scanf("%lld%lld",&a,&b);
        for(int i=0;i<=9;i++){
            printf("%lld ",work(b,i)-work(a-1,i));
        } 
        printf("\n");
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11222567.html

[1596060-20190721202628330-676586515.png]: /images/20230601/bb07a5e1ec484adcab03b7f4f6aed4fb.png

发表评论取消回复

表情：

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

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

相关阅读

相关洛谷 P1169 [ZJOI2007]棋盘制作

题意给定一个n\m的01矩阵，寻找最大的，相邻值不相同的子矩阵与子方阵。 \\(n,m\\leq 2,000\\) 分析朴素的做法是枚举两个点来确定矩阵，再

喜欢ヅ旅行/ 2023年08月17日 17:49/ 0 赞/ 130 阅读

相关洛谷P2602 [ZJOI2010]数字计数(数位dp)

数字计数 [题目传送门][Link 1] 解题思路用\\(dp\[i\]\[j\]\[k\]\\)来表示长度为\\(i\\)且以\\(j\\)为开头的数里\\(

水深无声/ 2023年08月17日 17:21/ 0 赞/ 111 阅读

相关洛谷 P2602 [ZJOI2010]数字计数

![1596060-20190721202628330-676586515.png][] 又是一道数位DP，不过做题多了也就发现套路了，这道题注意对前导0的判断以及dp状态的

冷不防/ 2023年06月04日 07:59/ 0 赞/ 63 阅读

相关【洛谷入门3】循环结构 P1980 计数问题

P1980 \[NOIP2013 普及组\] 计数问题题目描述试计算在区间 1到 n的所有整数中，数字x(0 ≤ x ≤ 9)共出现了多少次？例如，在 1到11中

谁践踏了优雅/ 2023年01月08日 11:28/ 0 赞/ 296 阅读

相关洛谷P1307 数字反转

题目背景猪猪hanke得到了一只鸡题目描述猪猪Hanke特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke吃鸡很特别，为什么特别呢？因为他有10种配料（芥

ゝ一纸荒年。/ 2022年05月31日 00:55/ 0 赞/ 188 阅读

相关洛谷P1216数字三角形

题目描述观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 7

冷不防/ 2022年04月15日 05:05/ 0 赞/ 207 阅读

相关洛谷 P4071 [SDOI2016]排列计数

![1596060-20190612191650302-584562041.png][] ![1596060-20190612191710278-1020740109.png

Bertha 。/ 2022年01月12日 13:33/ 0 赞/ 191 阅读

相关 ZJOI2010数字计数-数位DP

ZJOI2010数字计数 [题目传送][Link 1] sol: 仍然可以按照记忆化实现的思路来解决此题。 \\(pos,lim,lead\\)的含义不再申明，不了

系统管理员/ 2021年11月22日 17:08/ 0 赞/ 261 阅读

相关洛谷 P2034 选择数字

洛谷 P2034 选择数字 Description 给定一行n个非负整数a\[1\]..a\[n\]。现在你可以选择其中若干个数，但不能有超过k个连续的数字被

小咪咪/ 2021年11月10日 02:28/ 0 赞/ 240 阅读

相关洛谷P4047 [JSOI2010]部落划分题解

洛谷P4047 \[JSOI2010\]部落划分题解题目描述聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总

矫情吗；*/ 2021年09月29日 23:40/ 0 赞/ 333 阅读