B3930 [GESP202312 五级] 烹饪问题 题解

· · 题解

题意描述

给定一个数列 \{a_i\}，求找到一组 i,j~(i\neq j)，使 a_i \operatorname{and} a_j 最大。

约定记号

设最优解的 i=i_0，j=j_0。

也就是当 i=i_0,j=j_0 时，a_i \operatorname{and} a_j 最大。

解题思路

设当前寻找最优解的范围是 [l,r]，也就是说目前可以确定 l\le i_0,j_0\le r。初始时 l=1,r=n。

先将所有数从小到大排序，从高到低检查每一位，分讨这一位上的情况，逐步缩小最优解所在范围。

  1. 这位全部相同。
    答案显然与这一位无关，l,r 不用改动。

  1. 这位上有且仅有一个 1，位于数列末尾。
    则最优解的这位一定为 0，将末尾的数这一位改成 0 并插入排序。

  1. 当前位为 1 的数多于 1 个。
    则可以确定最优解这一位一定是 1。二分出首个这一位为 1 的位置 s 并令 l\leftarrow s。

最后，当 [l,r] 范围缩小到两个数时，可以确定 i_0=l,j_0=r 并求出最优解。

时间复杂度 O(n \log n)。

Code

#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e6+5;
int a[N];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,L,R;
    cin>>n;
    L=0,R=n-1;
    for(int i=0;i<n;++i) cin>>a[i];
    sort(a,a+n);
    for(int bit=1<<30;bit;bit>>=1){
        if((a[L]&bit)||!(a[R]&bit)) continue;  // 这一位全部相同
        if((a[R]&bit)&&!(a[R-1]&bit)){  // 只有1个1
            int t=a[R]^=bit,i;
            for(i=R-1;i>=L&&a[i]>t;--i) a[i+1]=a[i];
            a[i+1]=t;
        }else{  // 1的个数多于1
            int l=L,r=R,mid;
            while(l<r){
                mid=l+r>>1;
                if(a[mid]&bit) r=mid;
                else l=mid+1;
            }
            L=l;
        }
        if(R-L<=1) break;
    }
    assert(L<R);
    cout<<(a[L]&a[R]);
    return 0;
}

Update 2025.6.15：修正错误的图片。
Update 2025.6.16：微调公式。
Update 2025.12.6：优化语言表达和代码格式。