展开
题目背景
这是一道模板题。
题目描述
给定n个整数(数字可能重复),求在这些数中选取任意个,使得他们的异或和最大。
输入格式
第一行一个数n,表示元素个数
接下来一行n个数
输出格式
仅一行,表示答案。
输入输出样例
输入 #1复制
2
1 1
输出 #1复制
1
说明/提示
1 \leq n \leq 50, 0 \leq S_i \leq 2 ^ {50}1≤n≤50,0≤Si?≤250
感谢这位博主的文章
全面解析的博客(原理)好文章
线性基模板题
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1005;struct L_B
{LL d[65], p[65];int cnt;void init(){memset(d,0,sizeof(d));memset(p,0,sizeof(p));cnt = 0;//线性基大小 ,子集异或和的种类为2^cnt} // 1e18以内的数都适用.bool Insert(LL val){for (int i = 60 ; i >= 0 ; i --){if (val & (1LL << i)){if (!d[i]){d[i]=val;break;}val^=d[i];}}if(val>0) cnt++;return val > 0;// 可判断val是否存在于线性基当中.}LL query_max(){LL res = 0;for (int i = 60 ; i >= 0 ; i --){if ((res^d[i]) > res)res ^= d[i];}return res;}LL query_min() // 应该预先判断能否是0的情况..QAQ{for (int i = 0 ; i <= 60 ; i ++){if (d[i])return d[i];}return 0;}void rebuild() // 用于求第k小值.需要先进行独立预处理{for (int i = 60 ; i >= 0 ; i --){for (int j = i-1 ; j >= 0 ; j --){if (d[i] & (1LL<<j))d[i] ^= d[j];}}cnt=0;for (int i = 0 ; i <= 60 ; i ++){if (d[i])p[cnt++]=d[i];}}LL kthquery(LL k) // 注意判断原序列异或出0的情况, 此时应该将k -- 在进行后面的操作.{LL res = 0;if (k >= (1LL << cnt))return -1;for (int i = 60 ; i >= 0 ; i --){if (k & (1LL<<i))res ^= p[i];}return res;}void Merge(const L_B &b) // 把b这个线性基插入到当前这个线性基中.{for (int i = 60 ; i >= 0 ; i --)if (b.d[i])Insert(b.d[i]);}
}lb;
LL a[N];
int main()
{int n;scanf("%d",&n);lb.init();for(int i=1;i<=n;i++){scanf("%lld",&a[i]);lb.Insert(a[i]);}cout<<lb.query_max()<<endl;return 0;
}