bitset

序

从暑假开始就一直听到 \(bitset\) 优化, 而且好像还挺厉害, 虽然只是常数优化, 但是却非常的好用.

bitset 是啥

\(bitset\) 其实就是一个二进制数, 包含在 \(bitset\) 库里(万能头也有), 声明如下:

bitset <N> B;

表示声明了一个位长为 \(N\) 的 \(bitset\) , 所占用的内存也仅仅是 \(N\) 位, 也就是说, \(bitset\) 的每一位占用仅仅是 \(1\) 位, 与同样是表示 \(01\) 的 \(bool\) 相比, 小了 \(8\) 倍 ( \(bool\) 最小时是 \(1\ bit\), \(bitset\) 一位只要 \(1\ Byte\)).

所以当我们只需要 \(01\) 时, \(bitset\) 是不二之选, 空间复杂度大大减小.

\(bitset\) 不止能优化空间, 还能优化时间, 我们 \(n\) 个 \(bool\) 做位运算, 时间复杂度是 \(O(n)\) , 而一个 \(n\) 位的 \(bitset\) 做位运算, 时间复杂度仅为 \(n / w\) . 这个 \(w\) 是一个常数, 取决于你的计算机位数, 如果你是 \(32\) 位系统, 那就是 \(32\) , \(64\) 位系统就是 \(64\) .

尽管只是常数优化, 但是这个优化已经非常大了, 可以让我们原本复杂度 \(1e9 \sim 1e10\) 左右的代码卡到 \(1e8\) 左右.

bitset 咋用

\(bitset\) 支持的操作:

B = 10; //赋值
B[0]; // 访问某一位

/* 相同大小的 bitset 可以进行运算符操作 */
/* == != & &= | |= ^ ^= ~ << <<= >> >>=  */

B.count();     // 返回 1 的数量
B.size();      // 返回 bitset 的大小
B.any();       // 若有 1, 返回 1
B.none();      // 若无 1, 返回 1
B.all();       // 若全是 1, 返回 1
B.set();       // 全部设为 1
B.set(pos, k); // 将第 pos 位设为 k
B.reset();     // 全部设为 0
B.flip();      // 翻转每一位
B.flip(0);     // 翻转某一位

\(bitset\) 主要是应用于我们的状态仅有 \(01\) 两种时, 就我见过的题来看, 通常是 \(DP\) .

就以今天模拟赛的一道区间 \(DP\) 为例, 详细的讲解一下 \(bitset\) 到底咋用.

题目给出 \(n\) 个人按照 \(1 \sim n\) 的顺序站成一排, , 给出 \(n\) 个人之间 \(pk\) 的胜负关系, 求哪些人最终可以赢.

\(\operatorname{subtask}\ 1(10pts): n \leq 10\) .

\(\operatorname{subtask}\ 2(10pts): n \leq 50\) .

\(\operatorname{subtask}\ 3(20pts): n \leq 120\) .

\(\operatorname{subtask}\ 4(20pts): n \leq 300\) .

\(\operatorname{subtask}\ 5(20pts): n \leq 700\) .

\(\operatorname{subtask}\ 6(20pts): n \leq 2000\) .

时间限制: \(2s\)
空间限制: \(512MB\)

我一上来想成了拓扑排序 + 缩点, 后来发现不行, 然后觉得是个 \(DP\) , 于是开始想 \(DP\) .

想了好久, 感觉是个区间 \(DP\) , 但是暂时没有头绪, 所以我就干脆点, 先把状态设出来, 于是状态就出来了: \(f(i, j, k)\) 表示 \(k\) 在 \([i, j]\) 中能不能赢.

先把状态设出来, 管他会不会转移.

然而状态出来之后, 转移也就自然而然的出来了.

设 \(a[i][j]\) 表示 \(i\) 与 \(j\) \(pk\) 的结果.

我们考虑在区间 \([i, j]\) 中, 什么情况下 \(k\) 才能赢, 于是我们找到了 \(k\) 赢的充要条件: 当且仅当在 \([i, k - 1]\) 中存在能够被 \(k\) 打败的人, 并且这个人能够在 \([i, k - 1]\) 中赢, 也就是 \(a[k][o]\ \And\ f[i][k - 1][o]\) , 右边也是同理, \(a[k][o]\ \And\ f[k + 1][j][o]\) .

因为需要枚举 \(o\) , 所以复杂度 \(O(n^4)\) . 期望得分 \(60pts\) .

\(code:\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
  return x * f;
}

const int N = 705;

int n, a[N][N], f[N][N][N];
char s[N];

int main() {
  n = read();
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    for (int j = 1; j <= n; j++) {
      a[i][j] = s[j] ^ 48;
    }
  }
  for (int i = 1; i <= n; i++) f[i][i][i] = 1;
  for (int i = 1; i < n; i++) {
    f[i][i + 1][i] = a[i][i + 1];
    f[i][i + 1][i + 1] = a[i + 1][i];
  }
  for (int l = 3; l <= n; l++) {
    for (int i = 1, j = l; j <= n; i++, j++) {
      for (int k = i; k <= j; k++) {
        if (k == i) {
          for (int o = i + 1; o <= j; o++) {
            if (a[k][o] && f[i + 1][j][o]) {
              f[i][j][k] = 1;
              break;
            }
          }
        } else if (k == j) {
          for (int o = i; o < j; o++) {
            if (a[k][o] && f[i][j - 1][o]) {
              f[i][j][k] = 1;
              break;
            }
          }
        } else {
          if (f[i][k][k] && f[k][j][k]) f[i][j][k] = 1;
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (f[1][n][i]) printf("%d ", i);
  }
  return 0;
}

在还有十几分钟的时候, 本来我都放弃优化了的, 已经关掉我的 \(Linux\) 去 \(Windows\) 了, 然后突然, 我在给别人讲述我的思路的时候, 他重复了一下我的思路, "也就是说, 只要 \(k\) 能在 \([i, k]\) 中赢, 并且能在 \([k, j]\) 中赢就行是吧." , "woc! 你是天才!" 然后我突然就悟了!!!我说我会 \(n^3\) 的了, 然后想了一会, 好像不是 \(n^3\) , 仔细思索片刻, 确实是 \(n^3\) , 但是由于我太菜了, 有人拿我当蛐蛐, 押宝, 赌我能不能写出来. 由于非常好写, 我直接打开 \(vs\ code\) , 不到 \(2min\) 就写完了, 然后直接提交, 激动片刻, 没过大样例, 但是时间快了很多, 我还在想是不是只是常数优化? 然后打开一看, \(MLE\) , 我直接打开 \(vs\ code\) , 把 \(int\) 的状态改成了 \(bool\) , 然后提交, 漂亮! 过了. 那个人已经走了, 那个瞧我不起的人. 我的心脏怦怦直跳...一路从五楼冲到一楼, 吃饭去了.

\(n^3\) 其实很简单, 状态不变, 我们发现我们其实没必要枚举 \(o\) , 因为我们已经知道了 \(k\) 在 \([i, k]\) 中以及 \([k, j]\) 中能不能赢了, 所以我们就可以 \(O(1)\) 转移了, 只需要特判一下 \(k = i\) 以及 \(k = j\) 的情况就行了.

复杂度 \(O(n^3)\) , 期望得分 \(80pts\) .

\(code:\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) +(ch ^ 48);
  return x * f;
}

const int N = 705;

int n, a[N][N];
bool f[N][N][N];
char s[N];

int main() {
  n = read();
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    for (int j = 1; j <= n; j++) {
      a[i][j] = s[j] ^ 48;
    }
  }
  for (int i = 1; i <= n; i++) f[i][i][i] = 1;
  for (int i = 1; i < n; i++) {
    f[i][i + 1][i] = a[i][i + 1];
    f[i][i + 1][i + 1] = a[i + 1][i];
  }
  for (int l = 3; l <= n; l++) {
    for (int i = 1, j = l; j <= n; i++, j++) {
      for (int k = i + 1; k < j; k++) f[i][j][k] = f[i][k][k] & f[k][j][k];
      for (int k = i + 1; k <= j; k++) {
        f[i][j][i] = a[i][k] & f[i + 1][j][k];
        if (f[i][j][i]) break;
      }
      for (int k = i; k < j; k++) {
        f[i][j][j] = a[j][k] & f[i][j - 1][k];
        if (f[i][j][j]) break;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (f[1][n][i]) printf("%d ", i);
  }
  return 0;
}

接下来考虑正解, 其实正解已经不需要脑子了, 只可惜我当时不会 \(bitset\) , 加之过于激动, 就没想.

我们想一下, 我们的状态存的都只是 \(01\) , 所以我们完全可以开一个 \(bitset\) , 这样首先就解决了我们内存的问题, 因为 \(bool\) 是开不下 \(2000^3\) 的.

然后我们看一下我们的转移: \(f[i][j][k] = f[i][k][k] \And f[k][j][k]\) .

我们发现 \(k\) 是这三个变量的共同值, 我们就可以开两个 \(bitset\) , \(f1[i][j]\) 表示 \(j\) 在 \([i, j]\) 里能不能赢, \(f2[i][j]\) 表示 \(j\) 在 \([j][i]\) 里能不能赢, 这样我们就可以用 \(f1\) 和 \(f2\) 来分别表示 \(f[i][k][k]\) 和 \(f[k][j][k]\) 了, 由于第三维相同, 所以转移可以写成: \(f[i][j] = f1[i] \And f2[j]\) . 然后特判一下 \(k = i\) 和 \(k = j\) 的情况就行了, 顺便处理 \(f1\) 和 \(f2\) .

\(code:\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
  return x * f;
}

const int N = 2005;

int n;
bitset <N> f[N][N], f1[N], f2[N], a[N];
char s[N];

int main() {
  n = read();
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    for (int j = 1; j <= n; j++) {
      a[i][j] = s[j] ^ 48;
    }
  }
  for (int i = 1; i <= n; i++) f[i][i][i] = 1;
  for (int l = 2; l <= n; l++) {
    for (int i = 1, j = l; j <= n; i++, j++) {
      f[i][j] = f1[i] & f2[j];
      if ((f[i + 1][j] & a[i]).any()) f[i][j][i] = f2[j][i] = 1;
      if ((f[i][j - 1] & a[j]).any()) f[i][j][j] = f1[i][j] = 1;
    }
  }
  for (int i = 1; i <= n; i++) {
    if (f[1][n][i]) printf("%d ", i);
  }
  return 0;
}

转移 \(O(n/w)\) , 复杂度 \(O(n^3 / w)\) , 期望得分 \(100pts\) .

总结

其实 \(bitset\) 真的是个好东西, 当我们的操作只需要两个数组进行位运算, 并且状态只有 \(01\) 时, 复杂度可以在常数上有非常大的优化.