CF1721D

jrxxx · 2022-09-04 21:35:52 · 题解

提供一个实现较为简洁的两 \log 做法。

思路

按位贪心。

若要某一位上答案为 1，对于交换后的 \{a_i\},\{b_i\} 需满足：\forall i\in[1,n]， a_i 与 b_i 在这一位上 0/1 取值不同。

若这一位答案能取 1，在这之后，为了保证这一位上的异或值不受影响，a_i 和 b_i 都只能和在这一位上取值相同的数交换。

也就是说，将某一位上确定取 1 之后，需要将 \{a_i\},\{b_i\} 按这一位上的 0/1 取值分裂开，后续的判断递归进入每一个子集合，所有子集合答案取到时整体答案才能取到。

实现

思路很简单，但是代码一看就很细节。

这时候，我们拿出了万能的 \text{sort}。

将 \{a_i\} 从小到大排序，\{b_i\} 从大到小排序。

判断能否取 1 直接遍历，看看是不是每一个位置上 a_i,b_i 这一位取值都不同。

若能取 1，贡献给答案。接下来在每一个子集合，发现它们的下一位已经有序了（因为 \text{sort} 后按二进制位从高到低的优先级有序）。

若取 0，这一位上取值不影响后续集合划分，将 \{a_i\},\{b_i\} 在这一位上推平（0/1 都可以），重新 \text{sort} 消去这一位上取值对集合划分的影响。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7,V=30;
int a[N],b[N];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int T,n,i,j,ans;
    for(cin>>T;T--;)
    {
        cin>>n;
        for(i=1;i<=n;++i) cin>>a[i];
        for(i=1;i<=n;++i) cin>>b[i];
        sort(a+1,a+n+1,less<int>());
        sort(b+1,b+n+1,greater<int>());
        ans=0;
        for(i=V;~i;--i)
        {
            for(j=1;j<=n;++j)
                if((a[j]&(1<<i))==(b[j]&(1<<i)))
                    break;
            if(j>n) ans|=1<<i;//贡献给答案
            else 
            {
                for(j=1;j<=n;++j)//推平成1
                    a[j]|=(1<<i),b[j]|=(1<<i);
                sort(a+1,a+n+1,less<int>());//重新排序，抹去这一位上原有对集合划分的影响
                sort(b+1,b+n+1,greater<int>());
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}