2022杭电多校七FSumire（数位DP+实用技巧）

题目链接&＃xff1a;杭电多校7 - Virtual Judge

vjudge上题目显示的有问题&＃xff0c;我下面附上官方题目&＃xff1a;

样例输入&＃xff1a; 

3
2 2 0 1 5
1 4 3 11 45
10 14 11 19 198


样例输出&＃xff1a;

6
19
1049

题意&＃xff1a;多组样例&＃xff0c;每组样例给出五个数k,b,d,l,r&＃xff0c;其中b是代表b进制&＃xff0c;f(i,b,d)代表在b进制下i的数位中出现数字d的个数。求

 分析&＃xff1a;定义f[i][j][1/0][1/0]表示已经统计了前i位有j位是d且当前位有/无限制&＃xff0c;有/无前导0的方案数

一开始我按照普通的数位DP思路求解&＃xff0c;但是总是超时&＃xff0c;然后仔细分析了一下&＃xff0c;发现了原来的数位DP还可以具体根据题目优化一下。

比如这道题&＃xff0c;我一开始是分两种情况来进行动态转移&＃xff1a;

枚举当前填的数字

一种情况是当前有前导0且当前位置填0。

另一种情况就是当前位置填无前导0或者当前位置不填0&＃xff0c;这两个合成一种情况即可。

dfs代码是这样写的&＃xff1a;

long long dfs(int pos,int cnt,int limit,int lead)
{if(pos&＃61;&＃61;0) return (cnt&＃61;&＃61;tt);if(!limit&&!lead&&f[pos][cnt]!&＃61;-1) return f[pos][cnt];int up&＃61;limit?a[pos]:(b-1);long long ans&＃61;0;for(int i&＃61;0;i<&＃61;up;i&＃43;&＃43;){if(lead&&i&＃61;&＃61;0) ans&＃43;&＃61;dfs(pos-1,cnt,limit&&(i&＃61;&＃61;a[pos]),lead);else ans&＃43;&＃61;dfs(pos-1,cnt&＃43;(i&＃61;&＃61;d),limit&&(i&＃61;&＃61;a[pos]),0); }if(!limit&&!lead) f[pos][cnt]&＃61;ans;return ans;
}

后来对这样的代码进行了很多优化发现还是超时&＃xff0c;仔细分析了一下才发现当前位置如果不填d或者up或者0&＃xff0c;那么填其他任何数字都是一样的&＃xff0c;因为只有d才会对最后的答案造成影响&＃xff0c;而up会对下一次可以取的数字造成影响&＃xff0c;而0可以对前导0造成影响&＃xff0c;所以对于一种情况&＃xff0c;如果我们可以在0~up中做出选择&＃xff0c;去掉d、up、0之外的数选哪个都是一样的&＃xff0c;我们可以直接计算一下这样的数字的个数&＃xff0c;然后直接令ans&＃43;可选数字个数*dfs(pos-1&＃xff0c;cnt&＃xff0c;0&＃xff0c;0)即可&＃xff0c;因为选的数既不是上限也不是0&＃xff0c;所以会去掉限制和前导0&＃xff0c;而且由于选的数不是d&＃xff0c;那么也不会对答案造成贡献&＃xff0c;所以我们就可以把很多次重复的计算直接一次算出来&＃xff0c;这样的话就会极大地优化时间&＃xff0c;从而就可以ac&＃xff0c;有同学可能会问&＃xff1a;我们都记忆化了&＃xff0c;算一次和算十次有什么本质区别吗&＃xff0c;算完一次之后再算就直接访问数组就可以了啊&＃xff0c;为什么这样还会节省时间呢&＃xff1f;可以这么想假如说我们刚才讨论的那种不是up和d和0的情况有10000种&＃xff0c;那么我们就需要访问10000次数组&＃xff0c;这样算下来复杂度会高很多&＃xff0c;而我们之前的数位DP题目一般进制数都很少&＃xff0c;或者说一般都是10进制的&＃xff0c;而这道题b的上界是1e9&＃xff0c;这个数还是很大的&＃xff0c;所以我们这种优化对于进制数比较大的问题还是很有用的。

这个技巧近适用于贡献与某位数字有直接关系的题目中。

细节见代码&＃xff1a;

#include
#include
#include
#include
#include