XOR Inverse

zacharyzhong · 2023-09-27 16:40:00 · 题解

这题，就是一道和这题一样的暴力题！

                  ——Zachary_zhong

C1 题意

首先，想要A(shou)C(wan)这题，想法很简单，不就是把x从1枚举到 2^{32}-1 吗，然后把整个数组都异或一遍，再统计数组中的逆序对就可以了，但复杂度 O(2^{32}nlog_n) ，很显然，这是连样例都过不去的

C2 细化

然后，我们考虑优化，发现可以把原来的 O(2^{32}-1) 优化到 O(31) ，就是因为可以考虑按位异或这个值，你是永远不会发现异或到后面然后又发现前面不异或是最优的，所以我们可以暴力，首先从最高位(int的最高数字位,要开long long)枚举到最低位(注意，必须是从高到低)，如果答案加上这个值更优，更新答案，否则不更新。时间复杂度 \approx O(nlog_n) 大约 5*10^8 左右，卡卡常直接过

C3 Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[500009],ans,tmp[500009],b[500009];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void my_sort(int l,int r)
{
    int mid=(l+r)/2,nl=l,nr=mid+1,tmpp=l;
    if(l==r) return;
    else
        my_sort(l,mid),
        my_sort(mid+1,r);
    while(nl<=mid&&nr<=r)
        if(a[nl]<=a[nr])
            tmp[tmpp++]=a[nl++];
    else
        tmp[tmpp++]=a[nr++],ans+=mid-nl+1;
    while(nl<=mid)
        tmp[tmpp++]=a[nl++];
    while(nr<=r)
        tmp[tmpp++]=a[nr++];
    for(int i=l;i<=r;i++)
        a[i]=tmp[i];
}
inline void fy()
{
    for(int i=1;i<=n;i++)
        a[i]=b[i];
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),b[i]=a[i];
    int minn=INT_MAX,num=0;
    my_sort(1,n);minn=ans;
    fy();
    for(int i=31;i>=0;i--)
    {
        ans=0;num+=(1ll<<i);
        for(int j=1;j<=n;j++)
            a[j]=a[j]^num;
        my_sort(1,n);
        fy();
        if(ans<minn) minn=ans;
        else num-=(1ll<<i);
    }
    cout<<minn<<' '<<num<<endl;
    return 0;
}

C4 后记

交这题的时候CF炸了，结果题目评测时一遍过，另外，这题必须卡常，我平均每个测试点有 1500ms+ 。