Boboniu and Bit Operations

发表于 更新于 分类于 ，

    给出长度为n的数组a，长度为m的数组b。（$n,m<=200, 0<=a_i,b_i<2^9$）

    现在对于每个$a_i$，需要从b中寻找一个数$b_j$，使得$c_i = a_i\&b_j$

    我们需要求出最小的$c_1 | c_2 | \cdots | c_n$

Boboniu and Bit Operations

Created by LXC on Tue May 2 01:22:09 2023

https://codeforces.com/problemset/problem/1395/C

ranting: 1600

tag: bitmasks, brute force, dp, greedy

题意

给出长度为n的数组a，长度为m的数组b。（$n,m<=200, 0<=a_i,b_i<2^9$）

现在对于每个$a_i$，需要从b中寻找一个数$b_j$，使得$c_i = a_i&b_j$

我们需要求出最小的$c_1 | c_2 | \cdots | c_n$

题解

数据范围很小直接dp

设$f_{i,j}$ 为前i组数中（共有n组数，每组数中有m个数，每组数中必须且只能选一个）选出的数的或和能否是j（$j<2^9$），$f_{i,j}=0/1$代表否/是。

显然$f_{1,a_1&b_i} = 1, i \in [1,m]$

对于$f_{i,j}=1$，则有$f_{i+1, j|a_{i+1}&b_k}, k \in [1,m]$

时间复杂度$O(nms)$，n为a的大小，m为b的大小，s为数组数值范围。

代码

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>
#define SINGLE_INPUT
#define ll long long
#define N 605
#define MOD 998244353
using namespace std;

int a[N], b[N], f[N][N];

void sol() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i];
    for (int j = 1; j <= m; j++) {
        f[1][a[1] & b[j]] = 1;
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 1 << 9; j++) {
            if (f[i][j] == 1) {
                for (int k = 1; k <= m; k++) {
                    f[i + 1][j | a[i + 1] & b[k]] = 1;
                }
            }
        }
    }
    for (int i = 0; i < 1 << 9; i++) {
        if (f[n][i] == 1) {
            cout << i << "\n";
            return;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}