题目大意

有一个长度为n的序列a和长度为m的序列b，最多执行k次操作。对于每个操作：
$$
选择两个索引i (1 \leq i \leq n )和j(1\leq j\leq m),使a_{i}=a_{i} \& b_{j}
$$
求出$ \min \sum_{i=1}^{n}a_{i}$
数据范围$1 \leq n \leq 10^{5}, 1 \leq m \leq 10, 0\leq k \leq nm, 0\leq a_{i}\lt 2^{30},0\leq b_{i} \lt 2^{30}$

题解

对于$ \& $运算，每一个$ a_{i} $只会与每一个$ b_{j} $做一次操作，多次操作没有意义。
注意到$ m $的值很小，因此可以对每一个$ a_{i}$做状压dp预处理出$ dp_{i,j}$代表$ a_{i}$做了$ j$次操作后变成的最小值。复杂度$ O(n2^{m})$为$ 1e8$差不多，可以接受。
同时$ a_{i} \& b_{j} \& b_{k} = a_{i} \&(b_{j} \& b_{k})$因此可以预处理出$ f_{i} $代表在二进制数$ i$的情况下把对于的$ b_{j}$做$ \&$运算的结果。

对于dp

首先预处理$ dp_{i,0}=a_{i}$
$$
dp_{i,j}=\min a_{i} \& f_{k} ( \_ \_ builtin \_ popcount(k)=j)
$$
得到dp数组后，就可以得到每次$ a_{i}$多做一次运算后最多减少的数值，可以将$ dp_{i,j-1}-dp_{i,j}$全部处理出来排序，取前$k$大的数字作为$ \sum_{i=1}^{n} a_{i}$减少的数值，求出最终的最小值。
在实现中为了方便我使用了优先队列.
总的时间复杂度为$O(n2^{m}+nm\log nm)$

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
#define x first
#define y second
#define vv vector
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int,int>
using namespace std;
typedef long long i64;
constexpr i64 inf = 1e18;

void solve(){
    int n, m, k;
    cin>>n>>m>>k;
    vv<i64> a(n + 1, 0);
    vv<i64> b(m + 1, 0);
    vv<vv<i64>> dp(n + 1, vv<i64> (m + 1, inf));
    vv<i64> f((1 << m) + 1, 0);
    i64 ans = 0;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        //先统计总值
        ans += a[i];
        //预处理dp
        dp[i][0] = a[i];
    }
    for(int i = 1; i <= m; i++){
        cin>>b[i];
    }
    //状压预处理
    for(int i = 0; i < (1 << m); i++){
        f[i] = (1 << 31) - 1;
        for(int j = 1; j <= m; j++){
            if(i >> (j-1) \& 1){
                f[i] \&= b[j];
            }
        }
    }
    //状态转移
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < (1 << m); j++){
            dp[i][__builtin_popcount(j)] = min(dp[i][__builtin_popcount(j)], a[i] \& f[j]);
        }
    }
    priority_queue<i64, vv<i64>, greater<>>q;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            q.push(dp[i][j] - dp[i][j-1]);
        }
    }
    while(k--){
        ans += q.top();
        q.pop();
    }
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}