[BZOJ1833][ZJOI2010]count 数字计数 试题描述 给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次. 输入 输入文件中仅包含一行两个整数a.b,含义如上所述. 输出 输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次. 输入示例 输出示例 数据规模及约定 30%的数据中,a<=b<=10^6:100%的数据中,a<=b<=10^12. 题解 数位 dp,许多恶心的边界条件需要考虑. #include

1833: [ZJOI2010]count 数字计数 Time Limit: 3 Sec  Memory Limit: 64 MBSubmit: 2494  Solved: 1101[Submit][Status][Discuss] Description 给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次. Input 输入文件中仅包含一行两个整数a.b,含义如上所述. Output 输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次.

dp(i, j, k)表示共i位, 最高位是j, 数字k出现次数. 预处理出来. 差分答案, 对于0~x的答案, 从低位到高位进行讨论 ------------------------------------------------------------------------------ #include<bits/stdc++.h>   using namespace std;   typedef long long ll;   const int maxn = 16; const in

1833: [ZJOI2010]count 数字计数 Time Limit: 3 Sec  Memory Limit: 64 MBSubmit: 2951  Solved: 1307[Submit][Status][Discuss] Description 给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次. Input 输入文件中仅包含一行两个整数a.b,含义如上所述. Output 输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次.

BZOJ_1833_[ZJOI2010]count 数字计数_数位DP 题意: 给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次. 分析: 数位DP f[i][j][k]表示i位数,以j开头的数中k出现的次数 预处理出来10的幂(在数位DP中经常会用到) f[i][j][k]+=f[i-1][l][k]+(j==k)*10^(i-1) 之后按位枚举,0的情况特殊处理 代码: #include <stdio.h> #include <string.h

BZOJ1833 ZJOI2010 count 数字计数 Description 给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次. Input 输入文件中仅包含一行两个整数a.b,含义如上所述. Output 输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次. Sample Input 1 99 Sample Output 9 20 20 20 20 20 20 20 20 20 HINT 30%的数据中,a<=b<=10^6:

1833: [ZJOI2010]count 数字计数 题目:传送门 题解: 今天是躲不开各种恶心DP了??? %爆靖大佬啊!!! 据说是数位DP裸题...emmm学吧学吧 感觉记忆化搜索特别强: 定义f[i][j][k]表示若前i个位置有k个j的此时的全局方案数,然后就可以记忆化搜索了(具体看代码吧) 代码: #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #inclu

[算法]数位DP [题解] 记忆化搜索 #include<cstdio> #include<algorithm> #include<cstring> #define ll long long using namespace std; ll A[],B[],f[][],a[],p[]; ll dfs(ll* A,ll h,bool limit,bool pre) { ); ]!=-&&!pre) { ;i<=;i++)A[i]+=f[h][i]; ]

Description给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次.Input输入文件中仅包含一行两个整数a.b,含义如上所述.Output输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次.Sample Input1 99Sample Output9 20 20 20 20 20 20 20 20 20HINT 30%的数据中,a<=b<=10^6:100%的数据中,a<=b<=10^12. 首先把这个问题变成f(b

题目大意:求[a,b]间全部的整数中0~9每一个数字出现了几次 令f[i]为i位数(算前导零)中每一个数出现的次数(一定是同样的,所以仅仅记录一个即可了) 有f[i]=f[i-1]*10+10^(i-1) 然后照例十进制拆分 当中计算[0,999...9]的时候要从1~9枚举最高位,然后其余位调用f[i-1]就可以 剩余部分已知位直接乘,未知位调用f[i] #include<cstdio> #include<cstring> #include<iostream> #in

Description 题库链接 问你 \([l,r]\) 区间内所有整数中各个数码出现了多少次. \(1\leq a\leq b\leq 10^{12}\) Solution 数位 \(DP\) . 定义一个函数 \(cal(i)\) 为求 \([1,i)\) 中所有整数各个数码的和.显然答案就是 \(cal(r+1)-cal(l)\) . 考虑如何求 \(cal(x)\) . 先考虑数的位数小于 \(x\) 的情况.假设 \(x\) 的总位数为 \(tot\) .我们可以从 \(1\sim

http://www.lydsy.com/JudgeOnline/problem.php?id=1833 (题目链接) 题意 求在${[a,b]}$范围内整数中,每个数码出现的次数. Solution 数位dp. ${t}$数组取到最大数时表示每一位是多少. ${f[i][j][k]}$表示第${i}$位,这一位上的数为${j}$,数字${k}$的出现次数.转移:$${f[i][j][k]=\sum_{l=0}^9f[i-1][l][k]+10^(i-1)}$$ ${g[i][k]}$表示第${

题目 传送门:QWQ 分析 蒟蒻不会数位dp,又是现学的 用$ dp[i][j][k] $ 表示表示长度为i开头j的所有数字中k的个数 然后预处理出这个数组,再计算答案 代码 #include <bits/stdc++.h> using namespace std; typedef long long ll; ll dp[][][], ans[], b[], sum[]; int solve(ll x,ll d){ ; ll bef=x; ){ b[++len]=x%; } ;i<len

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1833 省选之前来切一道裸的数位dp.. 题意 统计[a,b]中0~9每个数字出现的次数(不算前导零). 我的做法 首先把询问的[a,b]拆成[0,b]减去[0,a-1]的个数. 我们考虑算前导零的情况.此时可以逐位确定数字:如果某一位的数字<给定的数在那位的数字,那么显然后面的数字可以随便取,于是把所有后面随便取的10^k个数字之中的0~9的出现次数统计一下(这个稍微推一推就出来了嘛...

数位DP学傻了,怎么写最后都写不下去了. 这题严格上来说应该不属于数位DP?只是普通DP加上一些统计上的判断吧. 首先复杂度只与数的位数$\omega$有关,所以怎么挥霍都不会超. f[i][j][k]表示所有i位数(可以有前导零),第一位数为j,数字k出现的次数.直接$O(\omega^4)$转移即可. 接下来只需要统计[1,n]中某个数字出现的次数,分两种情况. 1. 第一位是0:这个直接做就好了. 2. 第一位不是0:枚举第一个小于原数的位置,同样直接转移. #include<cstdio

题目: (传送门)[http://www.lydsy.com/JudgeOnline/problem.php?id=1833] 题解: 第一次接触数位dp,真的是恶心. 首先翻阅了很多很多一维dp,因为要处理前缀0,所以根本搞不懂. 查询了dalaolidaxin的博客,又查阅了资料: 初探数位dp 才完全弄懂这个题. 具体的,我们设 f[i][j][k]为考虑所有i位数,最高位为j数,之中k的数目. 我们可以得出方程: \[f[i][j][k] = \sum f[i-1][l][k] (j!=

点此看题面 大致题意: 求在给定的两个正整数\(a\)和\(b\)中的所有整数中,\(0\sim9\)各出现了多少次. 数位\(DP\) 很显然,这是一道数位\(DP\)题. 我们可以用前缀和的思想,分别求出小于等于\(b\)时的答案和小于等于\(a-1\)时的答案,然后将两个答案相减,就可以得出\(a\sim b\)之间的答案了. 对于每一位,若设\(x\)为当前需要小于的数字(即\(b\)或\(a-1\))当前可以填的数字有两种情况: ①前面的数字已经保证当前数字小于\(x\).则这位数字可

题目 给定两个正整数a和b,求在[a,b]中的所有整数中,每个数码(digit)各出现了多少次. 输入格式 输入文件中仅包含一行两个整数a.b,含义如上所述. 输出格式 输出文件中包含一行10个整数,分别表示0-9在[a,b]中出现了多少次. 输入样例 1 99 输出样例 9 20 20 20 20 20 20 20 20 20 提示 30%的数据中,a<=b<=10^6: 100%的数据中,a<=b<=10^12. 题解 你以为我真的会写数位dp? 首先容斥一下,转化为求小于等于

难受啊,怎么又遇到我不会的题了(捂脸) 如题,这是一道数位DP,随便找了个博客居然就是我们大YZ的……果然nb,然后就是改改模版++注释就好的了,直接看注释吧,就是用1~B - 1~A-1而已,枚举全部位然后判一下是不是上限边缘和前导零就OK #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; LL bit[]; ]; LL ]

Description 问 \([L,R]\) 中0-9的个数. Sol 数位DP. 预处理好长度为 \(i\), 最高位为 \(j\) 的数位之和. 然后从上往下计算,不要忘记往下走的同时要把高位的贡献加上去.. Code /************************************************************** Problem: 1833 User: BeiYu Language: C++ Result: Accepted Time:40 ms Memor