【ZROI noip10连day2】T1 题解

· · 个人记录

本题解尚未提交代码，不一定正确。

做法

先来考虑一下，已知每种砝码是否出现的情况下怎么判定能否凑出 x。

很容易写出一个指数级的爆搜：以当前重量 x 为参数，枚举砝码从 x 中减掉递归下去，看能否递归到 0。

复杂度：算不出来。预计得分：0 分。

这个爆搜之所以是指数级，是因为重复搜索了很多节点，所以搜完一个节点，就把这个节点的答案记录下来，就优化到 O(m) 了。

每次询问就临时统计一下询问区间每种砝码是否出现，用得到的信息跑记忆化搜索。

复杂度：O(qn+qm)。预计得分：50 分。

题目说了，砝码的数值不会超过 10 种。
而能否凑出一个数，只和这个数的数值以及砝码拥有状态决定。

要凑的数最大是 10^5，而砝码拥有状态有 2^{10} = 1024 种可能性。

可以把每种可能都枚举一下，进行预处理。

每次查询的时候，线段树维护区间每种砝码是否出现，然后用得到的信息直接查表。

复杂度：O(1024m+q \log n)，预计得分：100 分。

Code

正在写。