【常用模板】二进制枚举
浏览 113 | 评论 0 | 字数 3388
TTQ
2021年01月31日
  • 为了便于理解,我们从一个题目入手开始讲解。

    原题链接: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 授权协议,转载请注明来源,谢谢!
    评论
    与本文无关评论请发留言板。请不要水评论,谢谢。
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论