为了便于理解,我们从一个题目入手开始讲解。
原题链接: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;
}
这里有两个问题:
i < (1 << k)
?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 授权协议,转载请注明来源,谢谢!