bitset优化dp_牛客博客

传送门:https://ac.nowcoder.com/acm/contest/132/C?&headNav=www

$dp(i)代表i是否能被构成$ ,类似于:分组背包，每组必选的dp。那么朴素复杂度为： $\text{[math]}$

发现dp其实上是一个bool数组，我们将其代替成bitset.然后对于一个确定的xi. 它对背包容量的转移就是位运算的左移.再开一个滚动数组直接dp即可。

传送门：https://atcoder.jp/contests/agc020/tasks/agc020_c

题目大意：给你一个序列，他的子集的和有 2^n - 1 个。对它们排序以后问中位数是多少?(一定是奇数)

题目思路:

首先显然一点，这是一个01背包，我们需要dp它.

$dp(i)代表是否能够构成i,转移显然$ 用bitset优化为： $O(\frac{n^3}{64} )$

$\text{[math]}$

$显然必定有一个和 \leq \frac{sum}{2} ，有一个和 \geq \frac{sum}{2} .而全集无法配对.所以中位数一定 \geq \frac{sum}{2}.$

$\text{[math]}$

$所以[大于等于的] 一定多于 [小于等于的]了。所以中位数一定 \geq \frac{sum}{2}.$

关注到n很小，可以暴力预处理。令 f[x][y][z]代表题目的答案。对于每一个x , y , z暴力跑一次01背包.

$\text{[math]}$ 用bitset优化即可.

优化点：

1.bitset优化

2.输入输出优化

3.排列组合优化：对于 (i,j,k)的全排列，本质答案是一样的.所以循环变量 i , j , k 从它们前一个变量开始。然后统一赋值即可。快6倍

n <= 2000 , sum(a) <= 1e6

题目思路：

朴素思路是：发现总和很小。用dp[i]代表i能被构造出多少次。考虑到最后进行的是异或和。所以dp[i]只需要存储0
或者 1. 所以上bitset优化。转移方程为： $dp = dp \oplus (dp << a[i])$

$复杂度:O(\frac{n*v}{64} )$

思路: 当 n >= 1000 时，我们用bitset优化传递闭包的最内层循环.如下图所示:

当我们发现有一个点 i 与插点 k 有连边时，设k的出点集合为S，那么所有属于S的点都能够从i到达。

所以 i本轮松弛的结果是： $G\bigcup S$

bitset优化dp