找最小

给定两个长度为 $n$ 的序列 $a,b$,可以执行任意次交换 $a_i,b_i$ 的操作,最小化两个序列异或和的最大值。

多测,$1 \leq \sum n \leq 10^6$,$0 \leq a_i,b_i < 2^{31}$。

贪心、线性基

使用 $xor_a$ 表示 $a$ 的异或和,使用 $xor_b$ 表示 $b$ 的异或和。交换 $a_i,b_i$ 会让 $xor_a$ 和 $xor_b$ 同时异或上 $a_i \oplus b_i$ 这个值。

获得启发对满足 $c_i = a_i \oplus b_i$ 的序列 $c$ 构造线性基,分类讨论一下 $xor_a$ 和 $xor_b$ 各个位的情况。

  • 第 $i$ 位同为 $0$ 时,这一位应该异或上 $0$。
  • 第 $i$ 位同为 $1$ 时,这一位应该异或上 $1$。
  • 第 $i$ 位不同时,无论如何都有一个数的第 $i$ 位为 $1$。

前两种情况容易用线性基处理,第三种情况不好处理,我想不出来。

于是我询问 zmy123456,他说第三种情况会导致两个数大小不同,找到两个数的最高不同二进制位,枚举这个位为 $1$ 的数是哪个,如果是 $xor_a$ 则只需要最小化 $xor_a$,是 $xor_b$ 时同理。

如果 $xor_a$ 等于 $xor_b$ 则最小化 $xor_a$ 就等于最小化 $xor_b$,容易处理。

本题与线性基模板不同的是存在强制设置一个位为 $1$ 的操作,这种操作是否一定可执行呢?若强制第 $i$ 位为 $1$,当循环到线性基中决定第 $i$ 位的元素时返回值 $x$ 的第 $i$ 位为 $1$ 则无需操作;第 $i$ 位为 $0$ 时则要将 $x$ 异或上 $bis_i$,此时需要 $bis_i$ 不为 $0$。

又问 zmy 一阵子,他说由于线性基能得到的数的二进制最高位一定存在于线性基中,而这个线性基显然能得到 $xor_a \oplus xor_b$,被强制置为 $1$ 的位是 $xor_a \oplus xor_b$ 的二进制最高位,这一位必定存在于线性基中。

总体时间复杂度 $O(n \log V)$。

#include<bits/stdc++.h>
using namespace std;
unsigned int ans,xora,xorb,bis[35],a[1'000'005],b[1'000'005];
int n,pos;
void basis_insert(unsigned int x){
    for(int i=31;~i;i--) if(x>>i&1){
        if(bis[i]) x^=bis[i];
        else{
            for(int j=i-1;~j;j--) if(x>>j&1) x^=bis[j];
            for(int j=31;j>=i+1;j--) if(bis[j]>>i&1) bis[j]^=x;
            return bis[i]=x,void();
        }
    }
}
unsigned int query(unsigned int x,int k){
    for(int i=31;~i;i--){
        if(i==k&&!(x>>i&1)) x^=bis[i];
        if(i!=k&&(x>>i&1)) x^=bis[i];
    }
    return x;
}
void solution(){
    cin>>n,pos=-1,ans=~0u,xora=0u,xorb=0u;
    for(int i=1;i<=n;i++) cin>>a[i],xora^=a[i];
    for(int i=1;i<=n;i++) cin>>b[i],xorb^=b[i];
    memset(bis,0,sizeof(bis));
    for(int i=1;i<=n;i++) basis_insert(a[i]^b[i]);
    for(int i=0;i<=31;i++) if((xora>>i&1)!=(xorb>>i&1)) pos=i;
    ans=min(query(xora,pos),query(xorb,pos));
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}
最后修改:2024 年 10 月 22 日
如果觉得我的文章对你有用,请随意赞赏