首页 > 代码库 > LibreOJ #114. k 大异或和
LibreOJ #114. k 大异或和
二次联通门 : LibreOJ #114. k 大异或和
/* LibreOJ #114. k 大异或和 WA了很多遍 为什么呢。。。 一开始读入原数的时候写的是for(;N--;) 而重新构造线性基的时候要用到N。。。所以GG 对于找第k大异或和 只需把原来的线性基重新构造 构造规则为 若i<j, aj的第j位是1,就把aj异或上ai 查询的时候将k二进制拆分,对于1的位,就异或上对应的线性基。 最终得出的答案就是k小值。 */ #include <cstring> #include <cstdio> inline void read (long long &now) { register char word = getchar (); bool temp = false; for (now = 0; word < ‘0‘ || word > ‘9‘; word = getchar ()) if (word == ‘-‘) temp = true; for (; word >= ‘0‘ && word <= ‘9‘; now = now * 10 + word - ‘0‘, word = getchar ()); if (temp) now = -now; } long long N, M; class Linear_Base_Type { static const int _L = 52; private : long long number[_L + 2]; long long data[_L + 2]; int Count; public : Linear_Base_Type () { memset (data, 0, sizeof data); memset (number, 0, sizeof number); Count = 0; } inline void Insert (register long long key) { for (register int i = _L; i >= 0; i --) if (key & (1LL << i)) { if (number[i] == 0) { number[i] = key; break; } key ^= number[i]; } return ; } void Re_Build () { for (register int i = 1, j; i <= _L; i ++) for (j = 0; j < i; j ++) if ((1LL << j) & number[i]) number[i] ^= number[j]; for (register int i = 0; i <= _L; i ++) if (number[i]) data[Count ++] = number[i]; } inline long long Query_kth (register long long k) { long long res = 0; if (Count != N) -- k; if (k >= (1LL << Count)) return -1; for (register int i = 0; i <= _L; i ++) if (k & (1LL << i)) res ^= data[i]; return res; } }; Linear_Base_Type Make; int main (int argc, char *argv[]) { long long x; read (N); for (int i = 1; i <= N; i ++) { read (x); Make.Insert (x); } read (M); for (Make.Re_Build (); M --; ) { read (x); printf ("%lld\n", Make.Query_kth (x)); } return 0; }
LibreOJ #114. k 大异或和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。