解题关键: 求异或最大值. 线性基模板题.
极大线性无关组的概念.
异或的值域相同.
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cstdlib>
- #include<iostream>
- #include<cmath>
- using namespace std;
- typedef long long ll;
- const int MAX_BASE=63;
- ll base[64],a[60],n;
- void getbase(){
- for(int i=1;i<=n;i++){
- for(int j=MAX_BASE;j>=0;j--){
- if(a[i]>>j){
- if(!base[j]){
- base[j]=a[i];
- break;
- }
- a[i]^=base[j];
- }
- }
- }
- }
- ll query_max(){
- ll ans=0;
- for(int i=MAX_BASE;i>=0;i--){
- if((base[i]^ans)>ans){
- ans=base[i]^ans;
- }
- }
- return ans;
- }
- int main(){
- scanf("%lld",&n);
- for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
- getbase();
- ll ans=query_max();
- printf("%lld\n",ans);
- }
[P3812][模板] 线性基
来源: http://www.bubuko.com/infodetail-2948929.html