F - Spices(线性基)

F - Spices(线性基)

结论是$[1,2^n-1]$ 最多选$n$个数即可表示$[1,2^n-1]$ ，原理就是线性基。

因为要求$value$最小，所以按照价值排序，然后模拟线性基即可。

时间复杂度：$O(n{2}^n)$

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::vector<std::pair<int, int>> a((1 << n) - 1);
    for (int i = 0; i < (1 << n) - 1; i++) {
    
        int x;
        std::cin >> x;
        a[i] = {
    x, i + 1};
    }
    
    std::sort(a.begin(), a.end());
    
    i64 ans = 0;
    
    std::vector<int> t(n);
    for (auto [v, x] : a) {
    
        for (int i = 0; i < n; i++) {
    
            if (x >> i & 1) {
    
                if (t[i] == 0) {
    
                    ans += v;
                    t[i] = x;
                    break;
                }
                x ^= t[i];
            }
        }
    }
    
    std::cout << ans << "\n";
    
    return 0;
}