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

看到异或，我们首先应该想按位讨论。

那么我们就可以把某一位和它后面的位抽出来，去找它们加起来之后这一位为1的数有多少。

因此我们令

b_{i,k}

表示

a_i \bmod (2^{k+1}-1)

的结果，就能得到它的后

k

位。

首先我们对这个序列排序，接下来我们就可以分类讨论需要加起来的两个数：第

k

位都是

0

；一个是

0

，另一个是

1

；两个都是

1

。

其实不难发现，对于第

k

位相同的情况，我们需要让后面进位；对于第

k

位不同的情况，我们需要让后面不进位。所以双指针找一下进位的分界点就可以。

这题没卡双

\log

。所以我们可以愉快地使用

O(n\log n\log v)

的时间复杂度通过本题。其实每次排序之后我们可以从当前位为

0/1

的分界点分出两个序列，然后再根据这些数的更高一位的值归并，就能优化到

O(n\log v)

。

CPP

#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define fi first
#define se second
#define lb lower_bound
#define fr front()
#define pii pair<int,int>
using namespace std;

int n,a[500005],b[500005];

signed main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int ans=0;
    for(int k=30;k>=0;k--){
        int res=0;
        for(int i=1;i<=n;i++){
            b[i]=a[i]&((1ll<<(k+1))-1);
        }
        sort(b+1,b+n+1);
        int pos=n+1;
        for(int i=1;i<=n;i++){
            if(b[i]&(1ll<<k)){pos=i;break;}
        }
        // for(int i=1;i<=n;i++)cout<<b[i]<<" ";
        // cout<<"\n";
        //cout<<k<<" "<<pos<<" ";
        for(int l=1;l<pos;l++){
            if((2*b[l])&(1ll<<k)){
                for(int i=l,j=l;i<pos;i++){
                    while(((b[j]+b[i])&(1ll<<k))&&j>=1)j--;
                    res+=i-j;
                }
                break;
            }
        }
        //cout<<res<<"\n";
        for(int i=pos,j=pos-1;i<=n;i++){
            while(((b[j]+(b[i]^(1<<k)))&(1ll<<k))&&j>=1)j--;
            res+=j;
        }
        //cout<<res<<"\n";
        for(int l=pos;l<=n;l++){
            if((2*(b[l]^(1ll<<k)))&(1ll<<k)){
                for(int i=l,j=l;i<=n;i++){
                    while((((b[j]^(1<<k))+(b[i]^(1<<k)))&(1ll<<k))&&j>=pos)j--;
                    res+=i-j;
                }
                break;
            }
        }
        //cout<<res<<"\n";
        ans+=(res%2)*(1ll<<k);
    }
    cout<<ans;
}

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

文章操作

相关推荐

评论

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