[数据结构与算法]F - Spices「贪心 + 位运算」

F - Spices

题目描述：

输入n，再输入$2^n?1$个价格c[i]，每个物品的价值是i,价格是c[i]，

物品之间可以叠加，叠加后的价值是 $i_x\oplus i_y\oplus ....$

你需要挑选一些物品，使的这些物品之间进行任意方式搭配能构造出 1 到 $2^n?1$的价值的物品，问最少花多少钱可以实现

思路：

贪心

最多只需要n个物品就可以构造出来 1 到 $2^n?1$的所有的价值

（不会证明

所以我们只需要按价格从小到大进行排序，开一个数组判断这个价格是否已经能构造出来了，对于每个物品c，如果当前的价值还不能构造出来，对它异或上所有的已经构造成功的数进行更新，顺便开个计数器，如果用到了n个物品就可以跳出循环了

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
struct ran{
    int x, id;
    bool operator < (const ran &a)const{
        return x < a.x;
    }
}tr[MAX];
bool vis[MAX];

void add(int x){
    vis[x] = 1;
    for(int i = 1; i <= n; ++i){
        if(vis[i])vis[i ^ x] = 1;
    }
}

void work(){
    cin >> n;m = n;
    n = (1 << n) - 1;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i].x;tr[i].id = i;
    }
    sort(tr + 1, tr + 1 + n);
    int tot = 0;
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        if(!vis[tr[i].id]){
            ans += tr[i].x;
            ++tot;
            add(tr[i].id);
            if(tot == n)break;
        }
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}