为了便于理解，我们从一个题目入手开始讲解。

原题链接：https://atcoder.jp/contests/abc190/tasks/abc190_c

题目描述

We have $N$ dishes numbered $1,2,…,N$ and $M$ conditions numbered $1,2,…,M$.
Condition $i$ is satisfied when both Dish $A_i$ and Dish $B_i$ have (one or more) balls on them.
There are $K$ people numbered $1,2,…,K$. Person $i$ will put a ball on Dish $C_i$ or Dish $D_i$. At most how many conditions will be satisfied?

数据范围

All values in input are integers.
$2 \leq N \leq 100$
$1 \leq M \leq 100$
$1 \leq A_i < B_i \leq N$
$1 \leq K \leq 16$
$1 \leq C_i < D_i \leq N$

输入

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_M$ $B_M$
$K$
$C_1$ $D_1$
$\vdots$
$C_K$ $D_K$

输出

Print the answer.

样例输入

4 4
1 2
1 3
2 4
3 4
3
1 2
1 3
2 3

样例输出

2

题意

简单来说就是有$N$个盘子，有$M$种匹配方式，第$i$种匹配方式即$A_i$和$B_i$盘上有一个或更多球时认为满足条件。此时有$K$个人，第$i$个人可以选择在$C_i$或$D_i$盘上放上一个球，问最多能满足几个条件。

思路

很明显，对于每个人的操作来说都有两个选择：在$C_i$盘上放球或者在$D_i$盘上放球，因此对于$K$个人而言，一共有$2^K$种放球的方式，如果我们要用传统的方式枚举每一种情况会相当麻烦，所以我们需要使用二进制枚举。
代码如下：

//#include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define fast_io()                \
    ios::sync_with_stdio(false); \
    std::cin.tie(0);
#define mod 998244353
typedef long long ll;
typedef long double ld;
using namespace std;

int main()
{
    fast_io();
    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m);
    for (int i = 0; i < m; i++)
        cin >> a[i] >> b[i];
    int k;
    cin >> k;
    vector<int> c(k), d(k);
    for (int i = 0; i < k; i++)
        cin >> c[i] >> d[i];
    int ans = 0;
    for (int i = 0; i < (1 << k); i++)
    {
        int cnt = 0;
        vector<int> p(n);
        for (int j = 0; j < k; j++)
        {
            if (i & (1 << j))
            {
                p[c[j] - 1]++;
            }
            else
            {
                p[d[j] - 1]++;
            }
        }
        for (int t = 0; t < m; t++)
        {
            if (p[a[t] - 1] && p[b[t] - 1])
            {
                cnt++;
            }
        }
        if (cnt > ans)
            ans = cnt;
    }
    cout << ans;
    return 0;
}

这里有两个问题：

1. 为什么是i < (1 << k)？
2. 为什么是i & (1 << j)？

这里就涉及到位运算的知识了。

位运算

• 按位与运算符（&）

参与运算的两个数据按照二进制位的方式进行“与”运算。
即0&0=0; 0&1=0; 1&0=0; 1&1=1。
也就是两位同时为1时，结果才为1。

• 左移运算（<<）

$a << b$就表示把$a$转为二进制后再左移$b$位（在后面添$b$个$0$）。例如$100$的二进制为$1100100$，而$110010000$转成十进制是$400$，那么$100 << 2 = 400$。可以看出，$a << b$的值实际上就是$a$乘以$2$的$b$次方，因为在二进制数后添一个$0$就相当于该数乘以$2$(这样做要求保证高位的$1$不被移出)。

最后给出二进制枚举的通用模板：

for(int i = 0; i < (1<<n); i++) //枚举0~2^n-1中的每个状态
{
    for(int j = 0; j < n; j++) //遍历二进制的每一位
    {
        if(i & (1 << j))//判断第i种状态下的二进制第j位是否存在
        {
            //进行操作
        }
    }
    printf("\n");//一种状态判断结束
}

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/81.html
最后修改时间：2021-01-31 10:57:59
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！