Codeforces C. Boboniu and Bit Operations（按位或者状压）

本文主要是介绍Codeforces C. Boboniu and Bit Operations（按位或者状压），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Boboniu likes bit operations. He wants to play a game with you.

Boboniu gives you two sequences of non-negative integers 𝑎1,𝑎2,…,𝑎𝑛 and 𝑏1,𝑏2,…,𝑏𝑚.

For each 𝑖 (1≤𝑖≤𝑛), you’re asked to choose a 𝑗 (1≤𝑗≤𝑚) and let 𝑐𝑖=𝑎𝑖&𝑏𝑗, where & denotes the bitwise AND operation. Note that you can pick the same 𝑗 for different 𝑖’s.

Find the minimum possible 𝑐1|𝑐2|…|𝑐𝑛, where | denotes the bitwise OR operation.

Input
The first line contains two integers 𝑛 and 𝑚 (1≤𝑛,𝑚≤200).

The next line contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 (0≤𝑎𝑖<29).

The next line contains 𝑚 integers 𝑏1,𝑏2,…,𝑏𝑚 (0≤𝑏𝑖<29).

Output
Print one integer: the minimum possible 𝑐1|𝑐2|…|𝑐𝑛.

Examples
inputCopy
4 2
2 6 4 0
2 4
outputCopy
2
inputCopy
7 6
1 9 1 9 8 1 0
1 1 4 5 1 4
outputCopy
0
inputCopy
8 5
179 261 432 162 82 43 10 38
379 357 202 184 197
outputCopy
147
Note
For the first example, we have 𝑐1=𝑎1&𝑏2=0, 𝑐2=𝑎2&𝑏1=2, 𝑐3=𝑎3&𝑏1=0, 𝑐4=𝑎4&𝑏1=0.Thus 𝑐1|𝑐2|𝑐3|𝑐4=2, and this is the minimal answer we can get.

题意：
c[i]=a[i]&b[j]，j可以任意取。
求c[1]|c[2]|…|c[n-1]|c[n]的最小值

思路：
看错数据范围了，看成了 $10^9$ 。如果是题意的 $2^9$ ，那就可以直接状压，枚举c[n]能变成多少个数，最后取最小的即可。因为最多500个数，所以复杂度为O(n^2*500)。

但是也可以直接按位搞，这个方法甚至可以应对1e18。

就是先考虑二进制最高位1，如果有一个c[i]不得不取二进制第i位为1，则这一个二进制位必须要。否则把所有二进制第i位为1的数筛掉，这一位可以不取。复杂度为O(n^2*log(n))

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <string>
#include <set>typedef long long ll;
using namespace std;const int maxn = 205;
int a[maxn],b[maxn];
vector<int>C[maxn];
int n,m;void Clear(int pos,int n) {for(int i = 1;i <= n;i++) {vector<int>tmp;for(int j = 0;j < C[i].size();j++) {int v = C[i][j];if((v & (1 << pos)) == 0) {tmp.push_back(v);}}C[i].clear();C[i] = tmp;}
}int main() {scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);}for(int i = 1;i <= m;i++) {scanf("%d",&b[i]);}for(int i = 1;i <= n;i++) {for(int j = 1;j <= m;j++) {C[i].push_back(a[i] & b[j]);}}ll ans = 0;for(int i = 30;i >= 0;i--) {int cnt = 0;for(int j = 1;j <= n;j++) {int flag = 0;vector<int>tmp;for(int k = 0;k < C[j].size();k++) { //只要有一个第i位为0，则合理int v = C[j][k];if((v & (1 << i)) == 0) flag = 1;}if(flag) cnt++;}if(cnt == n) { //全部都可以抽出第i位为0，则所有第i位为1的数删掉Clear(i,n);} else {ans |= (1 << i); //抽不出来，则必须算上第i位。}}printf("%lld\n",ans);return 0;
}