ZJOI2010数字计数-数位DP

系统管理员 2021-11-22 17:08 190阅读 0赞

### ZJOI2010数字计数 ###

[题目传送][Link 1]

sol:

仍然可以按照记忆化实现的思路来解决此题。

\\(pos,lim,lead\\)的含义不再申明，不了解可以[看这里][Link 2]（含义是一样的）,也可以阅读那里面的那篇链接博文。

此题中只需多记录一个变量\\(cnt\\)，表示计算的数\\(now\\)，在\\(pos\\)位中已经出现了\\(cnt\\)次。

其上的\\(now\\)从0~9枚举，相当于分别计算答案。

为什么要记一个\\(cnt\\)呢。

可以这样理解：当搜索到边界的时候需要返回的值，就是当前所有的位中，\\(now\\)出现的次数，也即\\(cnt\\)。

#include<cmath> #include<string> #include<cstdio> #include<cstring> #include<algorithm> #define RG register #define IL inline #define LL long long #define DB double using namespace std; int len,now,a[15]; LL ans[15],f[15][15]; LL dfs(int pos,int cnt,int lim,int lead) { if(pos>len) return cnt; if(!lim&&f[pos][cnt]!=-1) return f[pos][cnt]; RG LL sum=0; RG int i,up=lim?a[len-pos+1]:9; for(i=0;i<=up;++i) if(lead&&i==0) sum+=dfs(pos+1,0,0,1); else sum+=dfs(pos+1,cnt+(i==now),lim&&i==up,0); if(!lim&&!lead) f[pos][cnt]=sum; return sum; } IL LL getans(LL x) { for(len=0;x;x/=10) a[++len]=x%10; memset(f,-1,sizeof(f)); return dfs(1,0,1,1); } int main() { RG LL l,r; scanf("%lld%lld",&l,&r); for(now=0;now<=9;++now) printf("%lld ",getans(r)-getans(l-1)); return 0; }

转载于:https://www.cnblogs.com/Bhllx/p/11017792.html

[Link 1]: https://www.luogu.org/problemnew/show/P2602
[Link 2]: https://www.cnblogs.com/Bhllx/p/11017650.html

发表评论取消回复

表情：

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

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

相关阅读

相关数位统计DP AcWing 338. 计数问题

数位统计DP AcWing 338. 计数问题原题链接 [AcWing 338. 计数问题][AcWing 338.] 思路对于数字n每位数出现数字x进

男娘i/ 2023年09月28日 13:03/ 0 赞/ 61 阅读

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

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

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

相关 1084 数字游戏 II（数位dp）

1. 问题描述：由于科协里最近真的很流行数字游戏。某人又命名了一种取模数，这种数字必须满足各位数字之和 mod N 为 0。现在大家又要玩游戏了，指定一个整数闭区间 \[a

我会带着你远行/ 2022年09月14日 09:13/ 0 赞/ 146 阅读

相关 1082 数字游戏（数位dp）

1. 问题描述：科协里最近很流行数字游戏。某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 123，446。现在大家决定玩一个游戏，指定一个整数闭区间

绝地灬酷狼/ 2022年09月14日 08:39/ 0 赞/ 109 阅读

相关数位dp总结

数位dp的题目一般问的是某个区间内满足某种性质的数的个数，而且对于数位dp的题目一般有都有比较通用的做法，在考虑问题的时候一般以树的形式来考虑： ![watermark_ty

「爱情、让人受尽委屈。」/ 2022年09月14日 03:06/ 0 赞/ 179 阅读

相关数位DP

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

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

相关【数位DP】C~K的幸运数字

Think: 1知识点：数位DP+记忆化搜索 2思考：（1）：dp数组记录状态应记录\[数位\]\[是否已经含有47\]\[前一位数值\] （2）：dp数组初

淡淡的烟草味﹌/ 2022年06月08日 09:06/ 0 赞/ 128 阅读

相关 SCUT - 289 - 小O的数字 - 数位dp

[https://scut.online/p/289][https_scut.online_p_289] 一个水到飞起的模板数位dp。 include<bits/

秒速五厘米/ 2021年12月09日 05:07/ 0 赞/ 199 阅读

相关数位DP JZOJ 3316. 非回文数字

题目 Description 如果一个字符串从后往前读与从前往后读一致，我们则称之为回文字符串。当一个数字不包含长度大于1的子回文数字时称为非回文数字。例如，162

r囧r小猫/ 2021年11月30日 00:58/ 0 赞/ 234 阅读

相关 ZJOI2010数字计数-数位DP

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

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