共有 $n$ 件物品,每件物品有价值 $v_i$ 与重量 $w_i$ 两个属性。但特别地,所选物品的总重量并不是每件物品的重量和,而是所有所选物品的重量进行按位或运算的结果。

请你计算,在所选物品总重量不超过 $m$ 的情况下,所选物品的最大价值之和是多少(价值之和正常定义为所选物品价值的加和)。

输入格式

第一行包括一个正整数 $T (1≤T≤10^4)$, 表示用例组数。

每组用例的第一行包括两个整数 $n, m (1≤n≤10^5, 0≤m≤10^8)$,含义如题面所述。接下来的 $n$ 行,每行包括两个整数 $v_i, w_i (0≤v_i ≤10^8 ,0≤w_i ≤10^8)$,含义如题面所述。

保证所有用例的 $\Sigma n ≤ 10^5$。

输出格式

对每组样例,输出一个正整数,表示所选物品的最大价值之和。

数据范围: $1 \leq n, T \leq 10^5$ $0 \leq m, v_i, w_i \leq 10^8$

输入样例:

3
4 11
1 8
1 4
1 5
1 1
4 11
5 8
1 4
1 5
1 1
4 0
2 0
0 0
3 0
4 1

输出样例:

3
6
5

题目分析

显然,我们不能用 01背包 的方式来计算,因为在遍历容量的过程中,我们不确定是否会变成完全背包。

代码实现

#include <iostream>
using namespace std;
using LL = long long;
const int N = 1e5 + 10;

int t, n, m, v[N], w[N];
LL check(int val) {
    LL res = 0;
    for(int i = 1; i <= n; ++i)
        if((val & w[i]) == w[i]) res += v[i];
    return res;
}
LL solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    LL ans = check(m);
    for(int i = m; i; i -= i & -i) ans = max(ans, check(i - 1));
    return ans;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) cout << solve() << '\n';
    return 0;
}
分类: Bitwise-operation

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status