夢に僕らで帆を張って
来るべき日のために夜を超え

标签 折半搜索 下的文章

October 24, 2019

CF525E Anya and Cubes

题意给你$n$个数,可以使用$k$次操作,每次操作可以使序列中的一个数$a_i$变为$a_i!$,求选出任意个数使他们和的等于$S$的方案数数据范围:$1 \le n \le 25,0 \le k \le n,1 \le s \le 10^{16}$题解折半搜索注意到$s \le 10^{16}$,因此只有$\le 19$的$a_i$需要考虑阶乘另外,由于选择状态过多,难以记录;所以记录选择...
October 24, 2019

洛谷P3067/USACO12OPEN 平衡的奶牛群Balanced Cow Subsets

题意给出$n$个数,从中选出一些,求选出的数能分成相等的两份的方案数数据范围:$2 \le n \le 20$题解对于每个元素,无非$3$种状态:$0$ 不选$-1$ 左$1$ 右但直接搜索复杂度达到$O(3^n)$考虑折半搜索将组合二进制压缩,前半搜索记录下可能的$sum$,后半搜索从前半中找到相等的$sum$(其实是找$-sum$,但是是等价的),则此种选择方案成立由于$sum$较大,需...