题意:
给出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加起来就可以了。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!