数位DP,要求的数往往极大,常用试填法。
- 求区间[l,r]内满足某某条件的数有多少个。
可以用[1,r]的答案-[1,l-1]的答案。往往在记忆化是要记录以下几点:
1)从高到低填到第几位
2)是否卡着限制
3)是否有前导0
4)题目中的特殊要求
例1,例2,例3都是这种题。 - 满足某某条件的第k小的数
首先预处理从低到高第i位,对要求的满足为j的情况有几种。然后每一位进行试填,设当前位填这个数后,后面的数还有cnt中可能,若cnt<n,则n-=cnt,不能填这个数,接着枚举,否则便填这个数。
例1,例2是这种题 - 求一些要求每个满足的数量,若直接做不好做,而要求的数量少,好枚举,又可以枚举满足哪个要求来搜索则可以这么做。例