1 条题解
-
0
题目分析
20 分
暴力搜索不是 的位置的值,然后用组合数计算一下加上 的方案数,复杂度是拆分数级别的。
40 分
写一个简单 dp 就行,复杂度 。
本质上是要求 。
考虑在二进制下使用数位 dp 解决问题,如果从高位向低位 dp,很难满足两数之和在 之间这个限制。
在此之前先解决一个问题,如何从低位到高位比较大小?(判断一个数是否大于等于一个已知的数 )
可以用一个 来维护, 表示在这个数最低的前 位时大于等于 最低的的前 位。
现在新增一位,如果这个数新增的这一位大于 新增的这一位,那么 一定为 。
如果相等,则 的值不变,即看最低的前 位比较结果。
如果 这个数新增的这一位小于 新增的这一位,那么 一定为 。
于是就可以从低位向高位 dp,枚举当前这一位填不填,有没有进位,就可以做到 的复杂度。
正解
其实跟 差不多,无非是有没有进位变成了进位是多少,每次转移枚举 中有多少个数当前二进制位为 。
时间复杂度 。
- 1
信息
- ID
- 59
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者