3630. 划分数组得到最大异或运算和与运算之和

思路讲解

【线性基【力扣周赛 460】】 https://www.bilibili.com/video/BV1pm8vzAEXx/?share_source=copy_web&vd_source=6ca0bc05e7d6f39b07c1afd464edae37

AC代码

https://leetcode.cn/problems/partition-array-for-maximum-xor-and-and/submissions/649067731/

源代码

class Solution {
public:
    using ll =long long ;
    struct LB{
        using ll =long long ;
        ll n;vector<ll> b;
        LB(ll n=62){
            this->n=n;
            b.assign(n+5,0);
        }
        void insert(ll x){
            for(int i=n;i>=0;--i){
                if(x>>i&1){
                    if(b[i]){
                        x^=b[i];
                    }else{
                        b[i]=x;
                        return;
                    }
                }
            }
        }
        ll findmx(){
            ll res=0;
            for(int i=n;i>=0;--i){
                if((res^b[i]) > res){
                    res^=b[i];
                }
            }
            return res;
        }
    };
    long long maximizeXorAndXor(vector<int>& nums) {
        ll N=nums.size();
        ll ans=0;
        // 暴力枚举是否是子集B
        for(int s=0;s<(1<<N);++s){
            bitset<22> bi(s);
            ll ands=-1,xors=0;
            for(int i=0;i<N;++i){
                if(bi[i]){
                    // 是子集B，计算与的和
                    ands&=nums[i];
                }else{
                    xors^=nums[i];
                }
            }
            if(ands==-1) ands=0;
            ll lans=ands+xors;
            // 出现奇数次的1在这个xors里面体现为1
            LB lb;
            for(int i=0;i<N;++i){
                if(!bi[i]) lb.insert(nums[i]&(~xors));
            }
            lans+=lb.findmx()*2;
            ans=max(ans,lans);
        }
        return ans;
    }
};

心路历程（WA，TLE，MLE……）