epee_no_front's Notes
Happy learning! Happy Coding!
Toggle navigation
epee_no_front's Notes
主页
codeforces
人工智能
JAVA
python
Latex&Markdown
计算机系统
关于我
归档
标签
数位DP
数位DP
ACM
2021-01-20 22:49:00
6
0
0
admin
数位DP
ACM
# 数位DP ## 学习计划 2021/1/18 基本知识、思路、例题 2021/1/19 基本例题、习题 2021/1/20 习题、整理 https://blog.csdn.net/tomjobs/article/details/111741760 https://www.lmlphp.com/user/56/article/item/6747/ https://blog.csdn.net/jk211766/article/details/81474632 https://www.luogu.com.cn/blog/virus2017/shuweidp 题单 [HDU2089](http://acm.hdu.edu.cn/showproblem.php?pid=2089)  状态：dp[pos][pre][st] pos：位置 pre：前一位 st：扫到当前位是否已经是满足条件。 [洛谷P2657](https://www.luogu.com.cn/problem/P2657)  状态：dp[pos][pre][st] pos：位置 pre：前一位 st：扫到当前位是否已经不再满足条件。 [洛谷P2602](https://www.luogu.com.cn/problem/P2602)  状态：num，dp[pos][st] num为当前计算的数码 pos：位置 st：扫到当前位数码num已经出现的次数。 [洛谷P3413](https://www.luogu.com.cn/problem/P3413)   ！思路：正难则反！考虑不符合条件的情形：任何一位都不和前两位数字相同。 状态：dp[pos][pre1][pre2][st] pos：位置 pre1：前一位字符 pre2：前前一位字符 st：当前状态是否已经还满足“任何一位都不和前两位数字相同” 其他问题： 由于正常数位DP会采用`part(r) - part(l-1)`，但此处需要实现高精度，那么可以考虑只算`part(r)-part(l)`，再单独判断一下`l`。 由于最后要用`(r-l+1)`减去自己算的才是题目要的答案，而`(r-l+1)`可以先取模再运算。 [洛谷P4127](https://www.luogu.com.cn/problem/P4127)  [参考](https://www.luogu.com.cn/blog/virus2017/p4127) 需要记录扫描到当前位置的数位cur_sum和以及原数st。 如何构造状态进行记忆化： st很大，无法记忆化，因此我们考虑枚举数位和，然后再进入递归求解。 也就是枚举digit_sum，该轮循环进入的dfs求解的是数位和是digit_sum且本身能被digit_sum整除的数的个数。 然后就是不再直接存储st，而是考虑st对digit_sum求模。 递归终止条件是 `if(pos > len) return (st == 0 && cur_sum == digit_sum) ? 1 : 0;` 。 [洛谷P4317](https://www.luogu.com.cn/problem/P4317)  注意是连乘！ 所以我们考虑先枚举`sum(i)`可能的值，设其为`d`，那么我们每次使用数位dp统计1~N中二进制形式中`1`的个数为`d`的数有多少。然后再快速幂计算总的连乘答案即可。 注意：这题的数位DP中别取模，因为求的是答案表达式中的指数。 [洛谷P4124](https://www.luogu.com.cn/problem/P4124)  dp[pos][pre1][pre2][s3][s4][s8]： pos：位置 pre1：前一位字符 pre2：前前一位字符 s3：是否已经有三位相邻数字相同 s4：是否出现过数字4 s8：是否出现过数字4 王队长的题单，明天学习 HDU4734 HDU4507 HDU3709 Codeforces55D Codeforces628D Codeforces914C
上一篇: 无
下一篇:
EDU-102-Div2
0
赞
6 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
皖ICP备20006612号
皖公网安备 34020302000165号
文档导航
admin
epee_no_front's Notes
