Closer's Space

梦河之上, 一叶扁舟

libreoj#114. k 大异或和


emmm, 题目应该叫k小异或和

传送门

题解:

先求出线性基, 特判有没有零(题目要求非空集), 如果向量满秩, 异或空间没有零 然后用二进制枚举第k小即可

/**
 * @author: adrui
 * @oj-id: libreoj-114
 */
#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
long long a[maxn];
int n, m;

int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        long long v;
        cin >> v;
        for(int j = 50; j >= 0; --j)
            if(v & (1LL << j)){
                if(!a[j]) { a[j] = v; break; }
                else v ^= a[j];
            }
    }
    for(int i = 49; i >= 0; --i)        //化最简形(方便求第k小)
        if(a[i]){
            for(int j = i + 1; j <= 50; ++j)
                if(a[j] & (1LL << i)) a[j] ^= a[i];
        }
    vector<long long> elem;
    for(int i = 0; i <= 50; ++i)
        if(a[i]) elem.push_back(a[i]);  //线性基分量
    int sz = elem.size();

    cin >> m;
    while(m--){
        long long p;
        cin >> p;
        if(sz < n) p -= 1;              //满秩
        if(p >= (1LL << sz)) {          //超出异或空间
            cout << -1 << endl;
            continue;
        }
        long long ans = 0;
        for(int i = 0; i <= 50; ++i)    
            if(p & (1LL << i)) ans ^= elem[i];
        cout << ans << endl;
    }
    return 0;
}

博文最后更新时间:


评论

  • 暂无评论

发表评论

来访统计

访问量:83

评论总数:0