「01」二进制与二进制状态压缩

位运算真值表

A (输入)	B (输入)	A & B (AND)	A \| B (OR)	A ^ B (XOR)
0	0	0	0	0
0	1	0	1	1
1	0	0	1	1
1	1	1	1	0

总结

与 (AND) 运算：全 1 为 1，其余为 0。只有当两个输入位都为 1 时，结果才为 1。
或 (OR) 运算：全 0 为 0，其余为 1。只有当两个输入位都为 0 时，结果才为 0。
异或 (XOR)：不同为 1，相同为 0。当两个输入位的值不相等时，结果才为 1。

异或运算可以视为不进位的加法。

二进制状态压缩

利用计算机中整数的二进制位来表示一个有限集合中元素的状态。

比如说，一个班级 $5$ 名同学，我们可以用一个 $5$ 位的二进制数来表示这 $5$ 名同学的到场情况。二进制的第 $0$ 位对应第 $0$ 名同学，第 $1$ 位对应第 $1$ 名同学， $\cdots$ ，第 $4$ 位对应第 $4$ 名同学，那么，二进制数 $01100$ 便表示第 $2$ ， $3$ 两名同学在场的状态。

假设第一天的到场情况对应的二进制数 $s_1 = 00111$ ，第二天的到场情况对应的二进制数为 $s_2=10101$ 。那么， $s_1 \& s_2$ 便表示这两天都到场的同学， $s_1 \mid s_2$ 表示这两天中至少有一天到场的同学， $s_1 \wedge s_2$ 表示恰好有一天到场的同学。

常用操作

操作	运算
取第 $k$ 位	$(n \gg k) \& 1$
取第 $0 \sim k-1$ 位	$n \& ( (1 \ll k) - 1 )$
第 $k$ 位取反	$n \wedge (1 \ll k)$
第 $k$ 位赋值 $1$	$n \mid (1 \ll k)$
第 $k$ 位赋值 $0$	$n \& ( \sim (1 \ll k ) )$

lowbit 运算

$\text{lowbit}(x) = x \& (-x)$

详细见树状数组一节。

bitset

bitset 可以看作一个多位的二进制数，每 32 位占用 4 个字节。

定义与初始化

使用bitset类型需 #include<bitset>
可以用string和整数初始化（整数转化成对应的二进制）

bitset<14> bit (string("1101"));
cout << bit << endl;           // 00000000001101
bit = 13;            
cout << bit << endl;           // 00000000001101
cout << sizeof(bit) << endl;   // 4
cout << bit.size() << endl;    // 14

基本运算

bitset支持所有位运算, 即可视为两个二进制数进行计算

常用方法

// 对于一个叫做bit的bitset：
bit.size()       // 返回大小（位数）
bit.count()      // 返回1的个数
bit.any()        // 返回是否有1
bit.none()       // 返回是否没有1
bit.set()        // 全都变成1
bit.set(p)       // 将第p位变成1（bitset是从第0位开始的！） 
bit.set(p, x)    // 将第p位变成x
bit.reset()      // 全都变成0
bit.reset(p)     // 将第p位变成0
bit.flip()       // 全都取反
bit.flip(p)      // 将第p位取反
bit.to_ulong()   // 返回它转换为unsigned long的结果，如果超出范围则报错
bit.to_ullong()  // 返回它转换为unsigned long long的结果，如果超出范围则报错
bit.to_string()  // 返回它转换为string的结果

相关题目

例1. 起床困难综合症

起床困难综合症

一个 boss 的防御战线由 $n$ 扇防御门组成，其中第 $i$ 扇防御门的属性包括一个运算 $op_i$ 和一个参数 $t_i$ ，运算一定是 OR、XOR、AND 中的一种，参数是非负整数。若在未通过这扇防御门时攻击力为 $x$ ，则通过这扇防御门后攻击力将变为 $x\ op_i\ t_i$ 。最终 boss 受到的伤害为玩家的初始攻击力 $x_0$ 依次经过所有 $n$ 扇防御门后得到的攻击力。由于水平有限，玩家的初始攻击力只能是 $[0, m]$ 之间的一个整数。玩家希望通过选择合适的初始攻击力，使他的攻击能造成最大的伤害，求这个伤害值。

数据范围： $n \le 10^5$ , $m, t_i \le 10^9$ 。

暴力计算的话，枚举 $[0, m]$ 内的每一个数，计算伤害值，伤害值的最大值即为答案。时间复杂度 $O(nm)$ 。

注意到位运算的一个特点是 每一位的运算结果是独立的，不影响其他位。故我们可以预处理第 $k$ 位是 $0$ 或 $1$ 的运算结果，对于当前枚举的攻击力 $x_0$ ，我们可以根据其第 $k$ 位是 $0$ 还是 $1$ 快速得到经过 $n$ 次位运算的结果，时间复杂度 $O(30m)$ 。

我们的问题是在初始攻击力不超过 $m$ 的前提下，运算的结果尽可能大。因此，我们可以直接考虑初始攻击力 $x_0$ 的第 $k$ 位是取 $0$ 还是 $1$ 。目标是在攻击力不超过 $m$ 的前提下，每一位运算的结果尽可能得到 $1$ 。

对于攻击力 $x_0$ 每一位的运算结果一共可能出现四种情况：

$0 \rightarrow 0$ , $1 \rightarrow 0$
$0 \rightarrow 0$ , $1 \rightarrow 1$
$0 \rightarrow 1$ , $1 \rightarrow 0$
$0 \rightarrow 1$ , $1 \rightarrow 1$

对于 1，3，4 这三种情况，我们都应该令 $x_0$ 的当前位取 $0$ 。

对于第 $2$ 种情况， $x_0$ 的当前位取 $1$ 不超过 $m$ 则可取 $1$ ，否则只能取 $0$ 。

最后，我们应该从高位到低位，依次确定 $x_0$ 的每一位。这是因为有可能因为低位得到了 $1$ 造成高位不能得到 $1$ ，这样不如优先考虑高位，让高位极可能得到 $1$ 。

参考代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n,m, num[N];
char op[N]; 

int calc(int x, int bit) { // x ==0, 或 1，bit表示 bit 位 
    for (int i = 1; i <= n; i++) {
        if (op[i] == 'A') x &= ((num[i] >> bit) & 1);
        if (op[i] == 'O') x |= ((num[i] >> bit) & 1);
        if (op[i] == 'X') x ^= ((num[i] >> bit) & 1);
    }
    return x;
}

int main(){    
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string str;
        cin >> str >> num[i];
        op[i] = str[0];
    }
    
    int st = 0, ans = 0;
    for (int bit = 29; bit >= 0; bit--) {
        int ans0 = 0, ans1 = 1;
        ans0 = calc(0, bit);
        ans1 = calc(1, bit);
        if (ans0 == 0 && ans1 == 1 && (st | (1 << bit)) <= m) {
            st |= (1 << bit);
            ans |= (1 << bit);
        } else {
            ans |= (ans0 << bit);
        }
    }
    cout << ans << endl;
}

例2. The Pilots Brothers' Refrigerator

The Pilots Brothers' Refrigerator

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 $16$ 个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。只有当所有把手都打开时，冰箱才会打开。把手可以表示为一个 $4 \times 4$ 的矩阵，您可以改变任何一个位置 $[i,j]$ 上把手的状态。但是，这也会使得第 $i$ 行和第 $j$ 列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

对于每一个位置，因为该边该位置的状态两次的话，相当于没有改变，因此，针对每个位置，最多有一次操作。并且操作顺序不影响结果。

我们将 $4\times 4$ 的矩阵和一个 $16$ 位的二进制数对应起来，矩阵的 $i$ 行 $j$ 列对应二进制数的 $4i+j$ 位（行和列从 $0$ 开始）。反之，二进制数的第 $k$ 位对应的是矩阵的 $k/4$ 行 $k\%4$ 列。

现在，我们枚举区间 $[1, 2^{16})$ 内所有的数，枚举的数的二进制表示中第 $k$ 位是 $1$ 表示改变了位置 $(k/4, k\%4)$ 。最后，题目要求按照整体从上到下优先级越低，同行从左到右优先级越低，进行排序, 输出优先级最高的方案。因此，我们在枚举的时候，先枚举优先级高的操作，即枚举二进制数的时候按从小到大的顺序进行枚举。

参考代码

#include <bits/stdc++.h>
using namespace std;

int mp[4][4];
int tmp[4][4];
bool op(int stat) {
    memcpy(tmp, mp, sizeof mp);
    for (int bit = 0; bit < 16; bit++) {
        if ((stat >> bit) & 1) {
            int row = bit / 4, col = bit % 4;
            for (int i = 0; i < 4; i++) {
                tmp[row][i] = !tmp[row][i];
                tmp[i][col] = !tmp[i][col];
            }
            tmp[row][col] = !tmp[row][col];
        }
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (!tmp[i][j]) {
                return false;
            }
        }
    }
    return true;
}

int count(int x) {
    int tot = 0;
    for (int bit = 0; bit < 16; bit++) {
        if ((x >> bit) & 1) tot++;
    }
    return tot;
}

int main() {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            char ch; cin >> ch;
            if (ch == '-') mp[i][j] = 1;
            else mp[i][j] = 0;
        }
    }

    int min_op = 9999;
    int ans = 0;
    for (int stat = 1; stat < (1 << 16); stat++) {
        bool res = op(stat);
        int t = count(stat);
        if (res && t < min_op) {
            min_op = t;
            ans = stat;
        }
    }
    cout << min_op << endl;
    for (int bit = 0; bit < 16; bit++) {
        if ((ans >> bit) & 1) {
            cout << bit / 4 + 1 << " " << bit % 4 + 1 << endl;
        }
    }
}

例3. 费解的开关

费解的开关

在一个 $5 \times 5$ 的 $01$ 矩阵中，点击任意一个位置，该位置以及它上、下、左、右四个相邻的位置中的数字都会变化（ $0$ 变成 $1$ ， $1$ 变成 $0$ ），问：最少需要多少次点击可以把一个给定的 $01$ 矩阵变成全 $0$ 矩阵？

注意开关问题的两个基本性质：

每个位置最多操作一次
操作顺序不影响结果

对于本题，我们可以发现，在对矩阵的第一行进行了点击了以后，第二行如何点击便确定了。这是因为我们的目标是使得所有的位置变为全 $0$ ，所以第二行我们能够点击的位置只能是现在第一行中为 $1$ 的位置的下一个位置，这样才能把第一行变为全 $0$ ，依此类推，第三行，第四行，第五行的操作都已经确定。由次，我们得到本题的处理步骤：

枚举第一行的操作，然后按照上面的描述进行第二行， $\cdots$ ，第五行的操作，最后，若第五行的格子全为 $0$ ，则说明本次操作是合法的。

参考代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

//  以状态stat开始操作，计算是否能在 6 步以内完成
int a[10][10], b[10][10];
int n;
void press(int i, int j)  // 按下位置(i, j)的灯
{
    b[i][j - 1] = !b[i][j - 1];
    b[i][j + 1] = !b[i][j + 1];
    b[i - 1][j] = !b[i - 1][j];
    b[i + 1][j] = !b[i + 1][j];
    b[i][j] = !b[i][j];

}

int calc(int stat)  //
{
    memcpy(b, a, sizeof b);

    int tot = 0;
    for (int i = 0; i < 5; i++)
        if ((stat >> i) & 1) {
            tot++;
            press(1, i + 1);
        }

    for (int i = 1; i <= 4; i++)  // 枚举第一层到第四层的状态，
    {
        for (int j = 1; j <= 5; j++) {
            if (!b[i][j]) {
                tot++;
                if (tot > 6)
                    return -1;
                press(i + 1, j);
            }
        }
    }

    for (int i = 1; i <= 5; i++)
        if (!b[5][i])
            return -1;
    return tot;
}

int main() {
    cin >> n;
    char str[10];
    while (n--) {
        for (int i = 1; i <= 5; i++) {
            cin >> str;
            for (int j = 0; j < 5; j++) a[i][j + 1] = str[j] - '0';
        }

        int ans = 100;
        for (int i = 0; i < (1 << 5); i++) {
            int t = calc(i);
            if (t != -1)
                ans = min(ans, t);
        }
        if (ans != 100)
            cout << ans << endl;
        else
            cout << -1 << endl;
    }
}

例4. Party Lamps 派对灯

Party Lamps 派对灯

在 IOI98 的节日宴会上，我们有 $n$ 盏彩色灯，他们分别从 $1 \sim n$ 被标上号码。这些灯都连接到四个按钮：

按钮 $1$ ：当按下此按钮，将改变所有的灯：本来亮着的灯就熄灭，本来是关着的灯被点亮。
按钮 $2$ ：当按下此按钮，将改变所有奇数号的灯。
按钮 $3$ ：当按下此按钮，将改变所有偶数号的灯。
按钮 $4$ ：当按下此按钮，将改变所有序号是 $3k+1 \ (k \in [0,+\infty) \cap \mathbb Z)$ 的灯。例如： $1,4,7,10 \dots$

一个计数器 $c$ 记录按钮被按下的次数。当宴会开始，所有的灯都亮着，此时计数器 $c$ 为 $0$ 。

你将得到计数器 $c$ 上的数值和经过若干操作后某些灯的状态。写一个程序去找出所有灯最后可能的与所给出信息相符的状态，并且没有重复。 $10 \le n \le 100$ ， $0 \le c \le 10^4$ 。

注意到开关问题的两个特点：

与操作顺序无关
每个位置最多按一次，按两次相当于没有按

那么，对于本题的按钮 1，2，3 来说，因为按钮 1 的效果相当于按钮 2 加上按钮 3 的效果，所有，无论按了多次次按钮 1，总可以转化为按了按钮 2 和按钮 3 相同的次数，所以对这 3 个按钮的操作总可以转化为对按钮 2 和 3 的操作，而按按钮偶数次相当于没有按，按奇数次相当于按了 1 次，故对按钮 1，2，3 的操作等于了按了按钮 2 一次，或按了按钮 3 一次，或同时按了按钮2，3 一次，而同时按了按钮 2，3 又相当于按了按钮 1。因此，对于按钮 1，2，3 来说，要么都没有按，要么按了其中某个键一次，再结合按钮 4 要么不按，要么按一次，那么无论实际按了多少次，得到的结果只会出现 8 种情况，与下面罗列的情况一致：

一次都没有按
按了一次按钮 1
按了一次按钮 2
按了一次按钮 3
按了一次按钮 4
按了两次按钮，分别为按钮 1 和按钮 4
按了两次按钮，分别为按钮 2 和按钮 4
按了两次按钮，分别为按钮 3 和按钮 4

考虑给出的 $c$ 值可能按了哪些按钮，相当于简化后的哪些情况？

c = 0
即一次都没有按
c = 1
可能是按了一次按钮 1 或 2 或 3 或 4。
c = 2
可以是按了一个键两次，这相当于一次都没有按。
可以是按了按钮 1 和按钮 2 各一次，这相当于按了一次按钮 3。
可以是按了按钮 1 和按钮 3 各一次，这相当于按了一次按钮 2。
可以是按了按钮 2 和按钮 3 个一次，这相当于按了一次按钮 1。
可以是按了按钮 1 和 4
可以是按了按钮 2 和 4
可以是按了按钮 3 和 4
c = 3
可以是按了按钮 1， 2， 3，这相当于一次都没有按。
可以是按了某个按钮 3 次，这相当于按了一次按钮 1，或按钮2，或按钮3，或按钮4。
也可以是按了按钮 1，2，4，相当于按了按钮 3， 4。
也可以是按了按钮 1，3，4，相当于按了按钮 2， 4。
也可以是按了按钮 2，3，4，相当于按了按钮 1， 4。
因此，在 $c = 3$ 的时候，已经可以覆盖了所有可能的 $8$ 种情况。
c = 4
我们在 c = 2 的基础上随意按一个键两次，就相当按了 4 次按钮，因此，c = 4 可以包含所有 c = 2 的情况。同时，我们可以按按钮1，2，3，4，这相当于按了按钮 4。所有， $c = 4$ 可以覆盖所有可能的情况。
c = 5 以及 c 更大的情况
这些都可以转化为 $c - 2$ 的情况，所有，都可以覆盖所有的情况。

综上，我们只需分 $c = 0$ , $c = 1$ , $c = 2$ , $c > 2$ 四种情况讨论即可。

另外，操作第一个按钮会使得彩灯具有长度为 $1$ 的周期，操作按钮 2， 3 会使得彩灯具有长度为 $2$ 的周期，操作按钮 4 会使得彩灯具有长度为 $3$ 的周期，那么，最终，彩灯总会具有长度为 $6$ 的周期。我们只需处理前 $6$ 各位置可能出现的情况即可。

在实现种，我们预处理可能的 $8$ 种情况，因此题目要求输出按照大小顺序排序，故对这 $8$ 种情况也按照对应的二进制数从小大进行了排序。

参考代码

#include <bits/stdc++.h>
using namespace std;

// 按字典序排序
const int result[8][6] = {
  {0, 0, 0, 0, 0, 0}, // 按 1
  {0, 0, 0, 1, 1, 1}, // 按 34
  {1, 0, 1, 0, 1, 0}, // 按 2
  {1, 0, 1, 1, 0, 1}, // 按 4
  {0, 1, 0, 0, 1, 0}, // 按 14
  {0, 1, 0, 1, 0, 1}, // 按 3
  {1, 1, 1, 0, 0, 0}, // 按 24 
  {1, 1, 1, 1, 1, 1}, // 按 0 次
};

int main() {
  int n, c; cin >> n >> c;
  vector<int> on, off;
  int x;
  while (cin >> x && x != -1) on.push_back(x);
  while (cin >> x && x != -1) off.push_back(x);

  vector<int> t;
  if (c == 0) t = {7};
  if (c == 1) t = {0, 2, 3, 5};
  if (c == 2) t = {0, 1, 2, 4, 5, 6, 7};
  if (c > 2) t = {0, 1, 2, 3, 4, 5, 6, 7};
  
  bool answerExist = false;
  for (auto x : t) {
    bool flag = true;
    for (auto y : on) {
      if (result[x][y % 6] != 1) flag = false;
    }
    for (auto y : off) {
      if (result[x][y % 6] != 0) flag = false;
    }
    if (flag) {
      answerExist = true;
      for (int i = 1; i <= n; i++) cout << result[x][i % 6];
      cout << endl;
    }
  }
  if (!answerExist) cout << "IMPOSSIBLE";
}

位运算真值表​

总结​

二进制状态压缩​

常用操作​

lowbit 运算​

bitset​

定义与初始化​

基本运算​

常用方法​

相关题目​

例1. 起床困难综合症​

例2. The Pilots Brothers' Refrigerator​

例3. 费解的开关​

例4. Party Lamps 派对灯​

位运算真值表

总结

二进制状态压缩

常用操作

lowbit 运算

bitset

定义与初始化

基本运算

常用方法

相关题目

例1. 起床困难综合症

例2. The Pilots Brothers' Refrigerator

例3. 费解的开关

例4. Party Lamps 派对灯