首页 > 其他分享 >P2602 [ZJOI2010] 数字计数

P2602 [ZJOI2010] 数字计数

时间:2023-01-24 20:14:01浏览次数:62  
标签:ch const 计数 int ll dig ZJOI2010 P2602 define

P2602 [ZJOI2010] 数字计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

数位DP模板题

由于是对0~9进行统计,所以我们只需对每一个数进行数位DP即可

不过对于0和1~9还是有区别的

对于dfs维度:pos,lim,zero,dig,sum (dig表示枚举的数字,sum表示在这当前这个大数字中dig出现的次数)

solution:

统计0:如果都是前导0,那么就算现在枚举0,sum也不能加进去

   如果前面不是前导0,就正常加

统计1~9,正常加数

好像也没啥可将的

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   //vector函数
#define popb pop_back  //vector函数
#define fi first
#define se second
const int N=20;
//const int M=;
//const int inf=0x3f3f3f3f;     //一般为int赋最大值,不用于memset中
//const ll INF=0x3ffffffffffff; //一般为ll赋最大值,不用于memset中
int len,a[N];
ll l,r,dp[N][N][2][2];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
ll dfs(int pos,bool lim,bool zero,int dig,ll sum)
{
    if(pos==len+1) return sum;
    if(dp[pos][sum][lim][zero]!=-1) return dp[pos][sum][lim][zero];
    ll res=0;
    int num=lim?a[pos]:9;
    for(int i=0;i<=num;i++)
    {
        if(dig==0) 
        {
            if(zero) res+=dfs(pos+1,lim && i==num,zero && i==0 ,dig,sum);
            else  res+=dfs(pos+1,lim && i==num,zero && i==0 ,dig,sum+(i==dig) );
        }
        else res+=dfs(pos+1,lim && i==num,zero && i==0 ,dig,sum+ (i==dig) ); // sum + i==dig 是错的,sum+(i==dig)是对的 
    }
    return dp[pos][sum][lim][zero]=res; 
} 
ll solve(ll x,int dig)
{
    len=0;
    memset(dp,-1,sizeof(dp));
    for(;x;x/=10) a[++len]=x%10;
    reverse(a+1,a+len+1);
    return dfs(1,1,1,dig,0);
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
    scanf("%lld%lld",&l,&r);
    for(int i=0;i<=9;i++) printf("%lld ",solve(r,i)-solve(l-1,i));
    return 0;
}

 

标签:ch,const,计数,int,ll,dig,ZJOI2010,P2602,define
From: https://www.cnblogs.com/Willette/p/17066313.html

相关文章

  • 【算法-计数排序和桶排序】Go语言实现
    计数排序新创建一个计数数组,size=Max遍历数组,值是索引。遍历计数数组,依次排列。funcCountSort(arr[]int){ count_arr:=make([]int,10) for_,value:=ra......
  • sql包含逗号的字段 统计数量
    说明:统计psyt类型的rw数量,psyt存储的格式(11,22,33,44)原理:substring_index(a.usualusecurrentstatusid,',',n)  ----截取第n个逗号前的数字substring_in......
  • JVM:运行时数据区-PC寄存器(程序计数器)
    JVM:运行时数据区1.什么是pc寄存器:JVM的pc寄存器也叫程序计数器,是对物理pc寄存器的一种抽象虚拟。用来存储指向一下条指令的地址,即将要执行的指令代码,由执行引擎读取下一......
  • 数字电路实验 07 - | 计数器及其应用
    一、实验目的和任务学会用集成电路构成计数器的方法。掌握中规模集成计数器的使用及功能测试方法。运用集成计数器构成1/N分频器。二、实验原理介绍计数器是数字系统中用得......
  • typora 标题计数
    /**initializecsscounter*/#write{counter-reset:h1}h1{counter-reset:h2}h2{counter-reset:h3}h3{counter-reset:h4}h4{......
  • 338. 比特位计数
    问题描述https://leetcode.cn/problems/counting-bits/description/解题思路这个题目,看上去是一个动态规划问题。用dp[i]代表i中1的个数。但我没想明白怎么写状态转移......
  • 【补档 11th Jan】 2283 判断一个数的数字计数是否等于数位的值(每日一题)
    【补档11thJan】2283判断一个数的数字计数是否等于数位的值(每日一题)​ 给你一个下标从0开始长度为n的字符串num,它只包含数字。如果对于每个0<=i<n的下......
  • 计数选讲
    1.CF1728G[*2700]看到这个一次合法的照明定义为所有的点都至少被一盏灯照亮,其实我们就应该想到容斥了。\(m=16\),那么铁定让我们关于点进行容斥了。容斥有正反两面:强制......
  • 计数 dp 目录
    数え上げテクニック集笔记。引言OI中有三大专题:dp,数据结构,图论。而在这三大专题中,因为dp是从小问题的解法上升至大问题的解法的关键;所以dp,在这三大专题中,优先性是......
  • <Verilog学习>Verilog设计参数化的译码器与编码器,以及设计4位格雷码计数器
    使用Quartus+modelsim完成设计目录1.参数化的译码器分析代码实现Testbench结果2.参数化的编码器分析代码Testbench结果3.4位格雷码计数器分析代码Testbench结果1.参......