C. Boboniu and Bit Operations
题意
给出n个数ai 和m个数bi (n,m<200) (ai,bi<2^9)
令ci=ai&bj i∈[1,n],每个bj可以被多个ai选中
求最小的c1|c2|c3|…|cn
题解
位运算 相关 想到枚举每一位
由于最后求c1|c2|..|cn 只要有一个ci的第i位为1那么最后答案这一位也有1
于是从最高位枚举到最低位
对于某位二进制 找到ai&bj 不为1的bj保留下来
若对于某个ai找不到ai&bj使的这一位为0那么最后答案中必定有这位二进制产生的贡献
枚举完这一位二进制后 每个ai都有对应的bj被保留下来
到下一位二进制 对于某个ai从被保留下来的bj中选择不会有此位ai&bj为1的 bj保留下来
依次逐位操作筛选得到答案
但这样想过程比较复杂虽然复杂度为O(9nm)
对于最终答案的范围<2^9=512 的条件下
完全可以选择枚举最终答案 然后对于每个答案ans判定是否合法
即是否所有(ai&bj)|ans=ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=2e2+5;
const double PI=acos(-1);
ll a[Max],b[Max];
bool vis[Max][Max];
int main() {
Turnoff;
int n,m;cin>>n>>m;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<m;i++)cin>>b[i];
ll ans=0;
for(int i=8;i>=0;i--){
ll bits=(1ll<<i);
vector<int>get[n+5];bool flag=0;
for(int j=0;j<n;j++){
deque<int>temp;
for(int k=0;k<m;k++){
if(vis[j][k])continue;
if(bits&(a[j]&b[k]))continue;
temp.push_back(k);
}
if(temp.empty()){
flag=1;
break;
}
for(int k=0;k<m;k++){
if(temp.front()==k){
temp.pop_front();
continue;
}
get[j].push_back(k);
}
}
if(flag)ans+=bits;
else{
for(int j=0;j<n;j++){
for(auto num:get[j]){
vis[j][num]=1;
}
}
}
}
cout<<ans<<endl;
}
|