首页 > 代码库 > [LOJ#114]k 大异或和
[LOJ#114]k 大异或和
[LOJ#114]k 大异或和
试题描述
这是一道模板题。
给由 n 个数组成的一个可重集 S,每次给定一个数 k,求一个集合 T?S,使得集合 T 在 S 的所有非空子集的不同的异或和中,其异或和 T1 xor T2 xor … xor T|T| 是第 k 小的。
输入
第一行一个数 n。
第二行 n 个数,表示集合 S。
第三行一个数 m,表示询问次数。
第四行 m 个数,表示每一次询问的 k。
第二行 n 个数,表示集合 S。
第三行一个数 m,表示询问次数。
第四行 m 个数,表示每一次询问的 k。
输出
输出 m 行,对应每一次询问的答案,第 k 小的异或和。如果集合 S 的所有非空子集中,不同的异或和数量不足 k,输出 -1。
输入示例
3 1 2 3 5 1 2 3 4 5
输出示例
0 1 2 3 -1
数据规模及约定
1≤n,m≤10?5??,0≤S?i??≤2?50??
题解
对线性基进行高斯消元,离散后对 k 进行二进制拆分。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> using namespace std; #define LL long long const int BufferSize = 1 << 16; char buffer[BufferSize], *Head, *Tail; inline char Getchar() { if(Head == Tail) { int l = fread(buffer, 1, BufferSize, stdin); Tail = (Head = buffer) + l; } return *Head++; } LL read() { LL x = 0, f = 1; char c = Getchar(); while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = Getchar(); } while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = Getchar(); } return x * f; } #define maxn 55 int n, cnt; LL bit[maxn], cb[maxn]; bool has0; int main() { n = read(); for(int i = 1; i <= n; i++) { LL a = read(); for(int j = maxn - 1; j; j--) if(a >> j-1 & 1) { if(!bit[j]){ bit[j] = a; break; } a ^= bit[j]; } if(!a) has0 = 1; } for(int i = maxn - 1; i; i--) for(int j = i - 1; j; j--) if(bit[i] >> j-1 & 1) bit[i] ^= bit[j]; for(int i = 1; i < maxn; i++) if(bit[i]) cb[cnt++] = bit[i]; int q = read(); while(q--) { LL k = read() - has0, ans = 0; if(k > (1ll << cnt) - 1){ puts("-1"); continue; } for(int i = cnt - 1; i >= 0; i--) if(k >> i & 1) ans ^= cb[i]; printf("%lld\n", ans); } return 0; }
[LOJ#114]k 大异或和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。