题解 | 小苯的序列合并

void solve(){
    int n;cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    int xor_sum=0;
    for(int i=1;i<=n;i++)xor_sum^=a[i];
    int l_sum=0;
    int final_ans=xor_sum;
    for(int i=1;i<=n;i++){
        l_sum^=a[i];
        final_ans=max(final_ans,l_sum&(xor_sum^l_sum));
    }   
    cout<<final_ans<<endl;
}

这题我们可以将所有异或起来的一堆数分成一组，那么实际上最终答案就是所有组的异或和 进行与操作的值，假如我们已经发现了最优解，那么所有组的异或和，在二进制的角度上都是最终答案的超集，只有这样进行与操作时才能得到最终答案；

所以假如最优解有奇数个组，我们直接将所有组异或起来，得到的值一定还是最优解的超集，因为最终答案会被异或奇数次；

假如有偶数个组，我们可以发现，可以将最优解的前(N-1)个组异或起来后再和最后一个值进行与操作得到的还是最终答案，所以我们就可以将这个最优解的前N-1个组放在同一组，最优解就可以化简成只有两组的情况；

总结后可以发现，最终答案由一个组组成或者两个组组成，那么我们只要遍历所有两个组的情况和一个组的情况，就一定会经过最优解，得到最终答案

时间复杂度O(n)