专栏文章

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

nningyy
P11651题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mimzm12b
此快照首次捕获于
2025/12/01 18:09
3 个月前
此快照最后确认于
2025/12/01 18:09
3 个月前
查看原文
目前最优解。

题意

题目写的很清楚了，求： ⨁1≤i≤j≤n(ai+aj)\bigoplus_{1\le i\le j\le n}\left(a_i+a_j\right)

思路

按位处理。
对于每一位先考虑本位的贡献，这是简单的，然后考虑进位，开一个辅助数组 cc 表示 aa 的前 kk 位（kk 是枚举到的那一位），所以进位的条件就是 ci+cj≥2kc_i+c_j\ge2^k。
排序双指针即可处理，复杂度 O(nlog⁡nlog⁡V)O(n\log n\log V)，其中 VV 为值域。
把排序优化成类似基数排序的东西，复杂度 O(nlog⁡V)O(n\log V)。

代码

CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...