每日一题6.7(线性基)

495684945

模版  洛谷p3812 https://www.luogu.com.cn/problem/P3812 或 acwing3164 https://www.acwing.com/file_syst ... ex/content/4186098/

变换题  acwing209 https://www.acwing.com/problem/content/description/211/

Fengyj

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){

    int n;
    cin>>n;

    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int k=0;
    auto guass=[&](){
        for(int i=62;i>=0;i--){
            for(int j=k;j<n;j++){
                if(a[j]>>i&1){
                    swap(a[j],a[k]);
                }
            }

            if(!(a[k]>>i&1)) continue;

            for(int j=0;j<n;j++){
                if(j!=k&&(a[j]>>i&1)) a[j]^=a[k];
            }
            k++;
            if(k==n) break;

        }
    };  

    guass();

    int ans=0;
    for(int i=0;i<k;i++) ans^=a[i];

    cout<<ans<<'\n';
    return 0;
}

Fengyj

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){

    int n;
    cin>>n;

    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int k=0;

    vector<int>p(64);

    auto insert=[&](int x){
       for(int i=62;i>=0;i--){
        if(x>>i&1){
            if(p[i]) x^=p[i];
            else{
                p[i]=x;
                break;
            }
        }
        
       }
    };  

    for(int i=0;i<n;i++){
        insert(a[i]);
    }

    int ans=0;
    for(int i=60;i>=0;i--){
        if((ans^p[i])>ans) ans=ans^p[i];
    }

    cout<<ans<<'\n';
    return 0;
}