题意:

给出n个数字,有q个询问,去掉三个数字,在剩下的数字里面选10个,问和能否刚好为87。其中

思路:

的bitset优化的dp居然可以水过…不科学啊…

有另一种做法:

因为删除3个数字,所以对于中间的那个数,表示前i个中选了j个没有选k的和的情况,表示后i个中选j个没有选k的和的情况,对于和的情况仍然用bitset优化。

特殊处理一下当3个数字有相同的情况。

询问的时候把前后拼起来就好了。

预处理复杂度为,询问的复杂度为。这复杂度也不科学。

但是可以学习一下这种思想。

ps.三个好像经常可以做文章啊?

http://pattle.xyz/2018/07/10/BAPC2014-finalE-线段树/

是可以最开始搞定一项,然后维护两项。

这里是枚举中间一项,预处理出前后两项的情况。


遇到类似9&9+9&4+9&3求值,可以按位来算,因为9为1001,所以只有第一位和第四位有贡献,所以对于9和4和3看这两位有没有1,统计一下这些位的1加起来就可以了。