题解：AT_abc236_f [ABC236F] Spices

IcyDragon · 2026-08-07 15:04:23 · 题解

思路

贪心，按照 c_i 从小到大排序，然后依次尝试将它们加入线性基，若加入成功，则选择此香料。

:::info[证明] 当一个香料加入线性基成功时，代表它的加入可以提升调配出的辣度的多样性，而且由于我们按照价格排序了，所以它是最便宜的；当一个香料加入线性基失败时，代表它的加入无法提升调配出的辣度的多样性，就不需要购买它了。 :::

代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

typedef unsigned int uint;
typedef long long lld;
struct Basis{
    static const int M = 31;
    uint a[M+1];
    void clear(){
        memset(a,0,sizeof a);
    }
    Basis(){
        clear();
    }
    bool insert(uint x){
        for(int i = M; i >= 0; i--){
            if(x>>i & 1){
                if(a[i]){
                    x ^= a[i];
                }else{
                    a[i] = x;
                    return true;
                }
            }
        }
        return x;
    }
    uint query_max(){
        uint ans = 0;
        for(int i = M; i >= 0; i--){
            ans = max(ans,ans^a[i]);
        }
        return ans;
    }
}b;
struct Node{
    lld v;
    uint id;
}a[100100];

int main(){
    int n;
    lld s = 0;
    cin>>n;
    n = (1<<n)-1;
    for(int i = 1; i <= n; i++){
        cin>>a[i].v;
        a[i].id = i;
    }
    sort(a+1,a+n+1,[](Node a,Node b){
        return a.v < b.v;
    });
    for(int i = 1; i <= n; i++){
        s += a[i].v*b.insert(a[i].id);
    }
    cout<<s;
    return 0;
}