[jzoj]1383.奇怪的问题

时间:2023-03-09 01:41:19
[jzoj]1383.奇怪的问题

Link

  https://jzoj.net/senior/#main/show/1383

Problem

  Alice总是会提出很多奇怪的问题,一天他让他的朋友Bob跟他一起研究一个奇怪的问题。问题是:[A,B]中有多少个数满足组成这个数的数字之和为S,另一个问题是[A,B]内满足这一要求最小的数是哪个?
  编程帮Bob解决这个问题。

Solution

30分

  显然可以使用暴力枚举,像我这样的渣渣,考试的时候想到数位DP,设完一个不完整的状态,根本不知道如何统计答案

100分

  聪明的人都知道,若要求区间[l,r]符合条件的数,题目的第一问可以转化成

  Ans(r)-Ans(l-1)

  其中Ans(x)表示1~x中符合条件的数

  我们需要套用数位DP经过风吹雨打都亘古不变的状态

  f[i,j,0/1]表示从高位开始向低位选了i位,目前的和为j,0表示当前前面选的数都等于