题目描述

难度分:$1789$

输入$n(1 \leq n \leq 10^5)$、$k(0 \leq k \lt 2^{30})$和$n$个$pair(a_i,b_i)$，其中$0 \leq ai \lt 2^{30}$，$1 \leq b_i \leq 10^9$。

从中选择一些$pair$，满足所有$a_i$的OR$\leq k$，并且$b_i$ 之和越大越好。

输出$b_i$之和的最大值。

输入样例$1$

3 5
3 3
4 4
2 5

输出样例$1$

8

输入样例$2$

3 5
3 3
4 4
2 5

输出样例$2$

8

输入样例$3$

3 5
3 3
4 4
2 5

输出样例$3$

8

算法

按位贪心

这种牵涉到位运算的一般都要拆位，关键要想到拆位的目的，这题我还想了挺长时间的。

考虑选出来的那些数按位或的结果是多少，从最高位开始考虑（本题最高位最大是$29$）。假设最开始所有数对都是待选状态，考虑到第$b$位时：

1. 如果$k$在当前位是$1$，要想选出来的所有元素按位或在这一位是$1$，就必须要至少保留一个$a_i$在当前位是$1$的数对，只要现在的待选数对中有这样的数对就全部选上，这样就能使得$b_i$之和最大，直接到下一位$b-1$上考虑。也可以让这一位是$0$，通过这样来保证按位或的结果$\lt k$，那后面的位就不需要挨个考虑了，因为让当前位为$0$已经可以满足所有$a_i$的按位或结果$\leq k$，直接把现在所有待选数对中满足$a_i$在当前位为$0$的$b_i$加起来就是这个策略下的答案。
2. 如果$k$在当前位是$0$，那么所有$b_i$按位或的结果在这一位也必须是$0$。把待选数对中满足$a_i$在当前位是$1$的数对删除，只留下当前位是$0$的数对到下一位$b-1$去考虑。

如果$b \lt 0$，说明从最低位已经考虑完了。把当前的待选数对中所有$b_i$加起来就是当前策略下的答案。维护所有策略下$b_i$累加和的最大值即可。

复杂度分析

时间复杂度

遍历$30$个位，在极端情况下每个位需要进行$O(n)$级别的数组遍历。因此，时间复杂度为$O(nlog_2U)$。

空间复杂度

递归实现按位考虑的过程，那么空间复杂度就是递归深度，为$O(30)$。输入的$n$个数对不计入空间复杂度，因此额外空间复杂度为$O(log_2U)$，其中$U$为所有数对中$a_i$的最大值。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

int n, k;
LL ans;

bool check(int b, vector<array<int, 2>>& tup) {
    for(int i = 0; i < tup.size(); i++) {
        if(tup[i][0]>>b&1) return true;
    }
    return false;
}

void dfs(int b, vector<array<int, 2>>& tup) {
    if(b == -1) {
        LL sum = 0;
        for(int i = 0; i < tup.size(); i++) {
            sum += tup[i][1];
        }
        ans = max(ans, sum);
        return;
    }
    int bit = k>>b&1;
    if(bit == 1) {
        if(check(b, tup)) {
            // 当前位保持1
            dfs(b - 1, tup);
        }
        // 当前位是0，那直接所有数都选上
        LL sum = 0;
        for(int i = 0; i < tup.size(); i++) {
            if(tup[i][0]>>b&1) continue;
            sum += tup[i][1];
        }
        ans = max(ans, sum);
    }else {
        // 当前位是0，只能选择剩余的数中这一位是0的数
        vector<array<int, 2>> nxt;
        for(auto&pir: tup) {
            if(pir[0]>>b&1) continue;
            nxt.push_back(pir);
        }
        dfs(b - 1, nxt);
    }
}

int main() {
    scanf("%d%d", &n, &k);
    vector<array<int, 2>> tup;
    for(int i = 1; i <= n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        tup.push_back({a, b});
    }
    ans = 0;
    dfs(29, tup);
    printf("%lld\n", ans);
    return 0;
}