当前位置: 代码迷 >> 综合 >> 洛谷 P3812 线性基
  详细解决方案

洛谷 P3812 线性基

热度:47   发布时间:2024-01-15 06:17:28.0

 展开

题目背景

这是一道模板题。

题目描述

给定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;
}

 

  相关解决方案