题解：AT_arc201_b [ARC201B] Binary Knapsack

Amidst · 2025-12-03 08:57:30 · 题解

思路

简单贪心题。

从低到高考虑每一位。

如果二进制下 W 的当前位为 1，则取最大价值的物品，因为不取会比取了更劣。

我们发现下一位的贡献可以来自这一位，发现在下一位取可以选择取两个这一位物品，所以我们可以按照大小将这一位物品的价值两两合并，放到上一位。

这样做的正确性是显然的：取到第 i 位时，必然有能使其价值最大的物品组合，且这一位的选择不会影响下一位的最优策略。

代码

#include <bits/stdc++.h>
//#include <bits/extc++.h>
#define int long long
#define INLINE inline __attribute__((always_inline))
#define __BEGIN_MULTITEST__ \
    signed T; \
    cin>>T; \
    while(T--) \
    {
#define __END_MULTITEST__ }
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using namespace std;
//using namespace __gnu_cxx;
//using namespace __gnu_pbds;
const int N=2e5+5,L=60;
int n,w;
basic_string<int> vec[L];
signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    __BEGIN_MULTITEST__
    cin>>n>>w;
    for(int i=0;i<L;i++)
        vec[i].clear();
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        vec[x].push_back(y);
    }
    int ans=0;
    for(int i=0;i<L;i++)
    {
        vec[i].push_back(0);
        sort(vec[i].begin(),vec[i].end(),greater<>());
        if(w&(1ll<<i))
        {
            ans+=vec[i][0];
            vec[i].erase(0,1);
        }
        if(i<L-1)
        {
            for(int j=1;j<(int)vec[i].size();j+=2)
                vec[i+1].push_back(vec[i][j]+vec[i][j-1]);
            if(vec[i].size()&1)
                vec[i+1].push_back(vec[i].back());
        }
    }
    cout<<ans<<'\n';
    __END_MULTITEST__
    return 0;
}