【砝码称重】

题目描述

有一天,小航在小天那里无意中发现了一个天平!这个天平很奇怪,有 n 个完好的砝码,但是没有游码。小航为他的发现兴奋不已!于是他准备去称一称 WG 的东西。他准备好了 m 种物品去称。神奇的是,小航一早就知道这 m 种物品的重量,他现在是想看看这个天平能不能称出这些物品出来。小航把这个问题丢给了你。

输入格式

第一行为两个数,n 和 m 。
第二行为 n 个数,表示这 n 个砝码的重量。
第三行为 m 个数,表示这 m 个物品的重量。

输出格式

输出 m 行,对于第 i 行,如果第 i 个物品能被称出,输出 “YES” 否则输出“NO”。

样例数据 1

输入

4 2
1 2 4 8
15 16

输出

YES
NO

备注

【数据范围】
30% 数据,n<=10;
50% 数据为随机数据;
100% 数据保证:1<=n<=24, 1<=m<=10。所有重量的绝对值在 1014 以内。直接DFS的话能拿50分,不过这道题坑的地方在于两边都可以放砝码,所以每次就有不变or放左边or放右边三种选项了,直接DFS的话复杂度是324 明显要超时,所以先DFS一遍[1,n/2]的砝码可能搭出来的所有情况,存在一个数组里,再用另一半DFS,看是否能在另一半找到某一种方式与数组里放的方式加在一起等于重量,有就返回true。话说二分查找+sort真是慢哭最慢的点要800+ms,而GJY神犇的set只用了400+ms。更厉害是的萎靡的YJQ的哈希,只用几十ms,可惜只能过8个点,遇到负数就TLE。

下面是我的代码:

哎,WA了16次,瞬间感受到了自己的蒟蒻

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*