本文共 1497 字，大约阅读时间需要 4 分钟。
给出\(n\)个数，求出子集异或第\(k\)小的值，不存在输出-1。
先用线性基存所有的子集，然后对线性基每一位进行消元，保证只有\(d[i]\)的\(i\)位存在1，那么这样变成了一组基线性基，然后按\(k\)的二进制找地k小。因为线性基不保存0，所以对有0的情况要进行特判。
#include#include #include #include #include #include #include #include #include #include #include #include #define ll long longusing namespace std;const int maxn = 1000 + 5;const int INF = 0x3f3f3f3f;const ll MOD = 1e9 + 7;struct Liner_Basis{ ll d[63], nd[63]; int tot, flag; void init(){ memset(d, 0, sizeof(d)); memset(nd, 0, sizeof(nd)); tot = flag = 0; } bool insert(ll x){ for(int i = 62; i >= 0; i--){ if(x & (1LL << i)){ if(d[i]) x ^= d[i]; else{ d[i] = x; return true; } } } flag = 1; return false; } void rebuild(){ for(int i = 62; i >= 0; i--){ if(d[i] == 0) continue; for(int j = i - 1; j >= 0; j--){ if(d[i] & (1LL << j)) d[i] ^= d[j]; } } for(int i = 0; i <= 62; i++){ if(d[i]) nd[tot++] = d[i]; } } ll kth_min(ll k){ if(flag) k--; if(k == 0) return 0; if(k >= (1LL << tot)) return -1; ll ret = 0; for(int i = 62; i >= 0; i--){ if(k & (1LL << i)){ ret ^= nd[i]; } } return ret; }}lb;int main(){ int T, ca = 1; scanf("%d", &T); while(T--){ int n; ll x; scanf("%d", &n); lb.init(); for(int i = 1; i <= n; i++){ scanf("%lld", &x); lb.insert(x); } lb.rebuild(); int q; scanf("%d", &q); printf("Case #%d:\n", ca++); while(q--){ scanf("%lld", &x); printf("%lld\n", lb.kth_min(x)); } } return 0;}
转载于:https://www.cnblogs.com/KirinSB/p/11236453.html