题解：P16721 终章

· · 题解

题目传送门

思路

注意到题目中用的异或，所以操作是在二进制上的。\ 要使答案尽可能的大，即使二进制中第一个 1 出现的尽可能早。

又因为两个 1 是可以抵消的，所以当某一位的 1 的个数为奇数时，这一位才有可能得以保留。

简单分讨。

  1. 数列中最先出现的 1 的数位 1 的总个数为奇数。
  2. 数列中最先出现的 1 的数位 1 的总个数为偶数。

情况 1：

我们不能删去这一位为 1 的数。

因此这些数是不能改变的，把它们加入字典树中。\ 对于剩下的数，有且仅有一个和字典树中的数配对后是可以在这一位产生 1 的，所以我们计算出每个数与字典树中任意一个数配对后可能产生的最小值。

由于我们可以删去其中一个这一位为 0 的数，所以答案即是我们计算出最小值序列中的次小值。

情况 2：

与上一种情况相反，必须删去这一位为 1 的数。

因为只能删一个数，所以这一位为 0 的数是不能改变的，用与上面同理的方法计算答案。

代码

#define fop(i,l,r) for(int i=l;i<=r;i++)
#define foo(i,r,l) for(int i=r;i>=l;i--)
int n,k=-1,cnt=1,f[21],a[400005];map<int,int>mp[5000005];
void add(int x){
    int st=1;foo(i,20,0){
        int now=!(!(x&(1<<i)));
        if(!mp[st][now])mp[st][now]=++cnt;
        st=mp[st][now];
    }
}int query(int x){
    int st=1,res=0;foo(i,20,0){
        int now=!(!(x&(1<<i)));
        if(!mp[st][now])res+=(1<<i),st=mp[st][!now];
        else st=mp[st][now];
    }return res;
}signed main(){
    int fl=1;rd(n);fop(i,1,2*n+1){
        rd(a[i]);int x=a[i];foo(j,20,0){if(x&(1<<j))f[j]++,x=x-(1<<j);}
        if(i>1&&a[i]!=a[i-1])fl=0;
    }foo(i,20,0)if(f[i]!=0){k=i;break;}
    if(fl)wt(0);
    else if(f[k]%2){
        fop(i,1,2*n+1)if(a[i]&(1<<k))add(a[i]);
        int mi=inf,mix=inf;fop(i,1,2*n+1)if(!(a[i]&(1<<k))){
            mix=min(mix,query(a[i]));
            if(mix<mi)swap(mix,mi);
        }wt(mix);return 0;
    }else{
        fop(i,1,2*n+1)if(!(a[i]&(1<<k)))add(a[i]);
        int mi=inf,mix=inf;fop(i,1,2*n+1)if(a[i]&(1<<k)){
            mix=min(mix,query(a[i]));
            if(mix<mi)swap(mix,mi);
        }wt(mix);return 0;
    }
}