题解：P11651 [COCI 2024/2025 #4] Xor

ningyy · 2025-11-27 15:54:28 · 题解

目前最优解。

题意

题目写的很清楚了，求：

思路

按位处理。

对于每一位先考虑本位的贡献，这是简单的，然后考虑进位，开一个辅助数组 c 表示 a 的前 k 位（k 是枚举到的那一位），所以进位的条件就是 c_i+c_j\ge2^k。

排序双指针即可处理，复杂度 O(n\log n\log V)，其中 V 为值域。

把排序优化成类似基数排序的东西，复杂度 O(n\log V)。

代码

#include <bits/stdc++.h>
#define int unsigned int
using namespace std;
const int N=3e6+10;
int n,a[N],a0[N],a1[N],n0,n1,c[N];
inline int get(int x,int k){
    return x>>k&1;
}
inline int pre(int x,int k){
    return x&(1<<k)-1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define _name_ "xor"
    #ifdef _name_
        freopen(_name_".in","r",stdin);
        freopen(_name_".out","w",stdout);
    #endif
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=0;
    for(int k=0;k<31;k++){
        int res=0;
        if(n+1&1) for(register int i=1;i<=n;i++) res^=get(a[i],k);
        if(k){
            for(register int i=1;i<=n;i++) c[i]=pre(a[i],k);
            int l=1,r=n,x=1<<k;
            while(l<=r){
                if(c[l]+c[r]>=x) res^=(r-l+1)&1,r--;
                else l++;
            }
        }
        if(res) ans|=(1<<k);
        n1=n0=0;
        for(register int i=1;i<=n;i++)
            if(get(a[i],k)==1) a1[++n1]=a[i];
            else a0[++n0]=a[i];
        merge(a0+1,a0+n0+1,a1+1,a1+n1+1,a+1,[&](int x,int y){
            return pre(x,k+1)<pre(y,k+1);
        });
    }
    cout<<ans;
    return 0;
}