01 背包冲过4e8？？不如学学 bitset

· · 题解

前言

我质疑题解区大部分 01 背包解法的复杂度正确性。01 背包做法时间复杂度为 O(n^2)\approx 4\times 10^8，在不开 O2 的情况下大都产生了 TLE 的结果，能过全靠 O2 玄学优化。

于是，我在此提出一种思路、代码均比 01 背包简单且思路相似的做法，最坏点仅用时 9ms。撰写此文章时在最优解第一页，此外还是疑似最短解法。提交记录

思路

我们要解决的第一个问题是“让同学不抗议”。这意味着每对“实力相当的同学”要么同时被选，要么同时不选。如果把“实力相当”的关系看作无向边，同学看作结点，那么我们将得到一个无向图，其中处在同一个连通块内的同学要么同时被选，要么同时不选。

此处我们只关心同学之间的连通关系，故可以用并查集维护。根据题意，接下来我们要选中若干个连通块，使得它们的大小之和与 m 尽可能接近。

我们不妨把连通块的大小列为数组 a_{1\cdots x}（x 为连通块的个数），考虑 DP。

我们令 f_i=0/1 表示能否选择若干个连通块，使得它们的大小之和为 i。初始时 f_0=1，其余位置 f_i=0。

如果我们新加入一个大小为 a 的连通块，那么我们有 f_i\leftarrow f_i\ \text{OR}\ f_{i-a}，其中 \text{OR} 表示逻辑或运算。由于 f 的范围是 [0,n]，最坏情况下有 n 个连通块，所以时间复杂度是 O(n^2) 的。

诶那这不是和 01 背包一样坏吗？不要着急，让我们引入 bitset。我们注意到如果我们把 f 当做一个数字，每一个 f_i 当作这个数字的一个二进制位（f_0 为最低位），那么我们的转移实际上相当于让 f 在二进制下左移 a 位再对 f 做按位或。bitset 就是用来实现这样的功能的。

我们知道对一个整数做位运算可以看作常数时间，但是这个整数 f 非常之大，大小达到了 2^{2000}，因此我们不能把它当做常数来考虑。一般情况下我们有共识认为单次运算的复杂度是 \frac{\text{len}}{w}，其中 \text{len} 为 bitset 的大小，w=32/64，为计算机的位数。

综上，用 bitset 实现的 DP 时间复杂度为 O\left(\frac{n^2}{w}\right)\approx1.25\times 10^7(w=32)，可以轻松通过此题。由于 bitset 的位运算写法和整数的位运算写法差不多，写起来十分方便。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 20001;
int n,m,k,f[N],a,b,sz[N],ans;
int find(int x){return x == f[x] ? x : f[x] = find(f[x]);}
bitset<N> g;
int main(){
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> k;
  for(int i = 1;i <= n;i ++) f[i] = i,sz[i] = 1;
  for(int i = 1;i <= k;i ++){
    cin >> a >> b;
    a = find(a),b = find(b);
    if(a != b) sz[a] += sz[b],f[b] = a;//合并两个实力相当的同学所在的并查集
  }
  g[0] = 1;//初始化边界条件
  for(int i = 1;i <= n;i ++) if(i == find(i)) g |= g << sz[i];//DP，对于每一个并查集做一次位运算
  for(int i = 1;i <= n;i ++) if(g[i] && abs(i - m) < abs(ans - m)) ans = i;//找到和 m 最接近的可达的和 i
  printf("%d\n",ans);
  return 0;
}

其他解法——对于 01 背包做法的进一步优化

我们可以把相同大小的连通块合并为一类物品，做多重背包。

由于连通块大小之和为 n，最坏情况下各个连通块的大小依次为 1,2,3,\cdots，由于有总和限制可知连通块的种类数至多为 O(\sqrt{n})。在此题条件下，使用二进制优化和单调队列优化的多重背包时间复杂度均为 O(n\sqrt{n})。（这是因为多重背包的 \log 复杂度来自同种物品的分割，但是在这里划分出同样大小的连通块对复杂度的影响显然没有不同种类的连通块的影响大，因此可以忽略不计）