题解：P17127 [ICPC 2025 Shanghai R] Gemcrate

Grammar_hbw · 2026-07-19 23:00:20 · 题解

注意到：分三个组以上没有意义。证明：考虑三个组，如果答案的某一个二进制位是 1，那这三个组的异或值在这一位必须同时为 1，那合并为一组是等价的。

如果分一个组，答案就是全局异或，记为 x。

分两组的时候，x 中所有为 1 的位都没有意义。把所有数与上取反的 x 答案不变，但现在任意取数异或都可以作为最后的答案。线性基板子。

:::info[Code Time]

#include <bits/stdc++.h>
using namespace std;
typedef long long li;
const int N=500007;
struct bs{
    li val[61];
    int cnt=0;
    void clear(){
        for(int i=0;i<60;i++) val[i]=0;
        cnt=0;
    }
    void insert(li x){
        for(int i=59;~i;i--) if((x>>i)&1){
            if(val[i]) x^=val[i];
            else {val[i]=x;return;}
        }
    }
    li query(){
        li ans=0;
        for(int i=59;~i;i--) if((ans^val[i])>ans) ans^=val[i];
        return ans;
    }
} hbw; //线性基。我们把三个组合并为（hbw）一个组。
li a[N];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin>>t;
    while(t-->0){
        int n;
        cin>>n;
        li x=0;
        for(int i=1;i<=n;i++) cin>>a[i],x^=a[i];
        hbw.clear(); // hbw 提醒你：多测不清空，WA 见祖宗。
        for(int i=1;i<=n;i++) hbw.insert(a[i]&(~x));
        cout<<max(hbw.query(),x)<<'\n'; // 记得考虑只取一组的1情况。
    }
    return 0;
}

:::