题意
给定 $m$ 和一个长度为 $n$ 数列 $a$
一种方案为从 $a$ 中选择 $k (0 \leq k \leq n)$ 个数字出来（在一个方案中，每一位只能选择一次）
一种合法的方案为选择的所有数字加起来不超过 $m$
$n \leq 40$
标签： 搜索
AtCoder Regular Contest 084 D Small Multiple
题意
要求 $ x = ak(a \in N) $，定义 $f(x)$ 为 $x$ 在十进制下每一位数字的和
思路
一开始肯定想的是大力枚举，但是很快就可以发现大力枚举可以被卡掉，因为另一个数字可以非常大
然后就考虑缩小另一个数字的范围
一开始的思路顺着质因数分解走的，但是想了半天没有想出来
考后发现顺着质因数的过于复杂，我们可以直接考虑 $x \bmod k$ 意义下的情况
从 $ x $ 到 $ x + 1 $，答案显然增加 1
但是如果 x 一直加 1 会加到 10 ，这个情况答案在事实上没有增加 1
我们可以发现只有其在某一步变成 10 倍才会发生这种事件，那么再加一条边
从 $x$ 到 $10x$，答案不增加
这样就构成了一条图，从 $0$ 到 $1$ 的最短路就是所求答案
Continue reading “AtCoder Regular Contest 084 D Small Multiple”