题意描述

给定一个数列{ai}\{a_i\}{ai​}，求找到一组i,j (i≠j)i,j~(i\neq j)i,j(i=j)，使aiand⁡aja_i \operatorname{and} a_jai​andaj​最大。

约定记号

设最优解的i=i0i=i_0i=i0​，j=j0j=j_0j=j0​。

也就是当i=i0,j=j0i=i_0,j=j_0i=i0​,j=j0​时，aiand⁡aja_i \operatorname{and} a_jai​andaj​最大。

解题思路

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

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

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

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

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

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

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

Code

#include<bits/stdc++.h>usingnamespacestd;constexprintN=1e6+5;inta[N];intmain(){cin.tie(0)->sync_with_stdio(0);intn,L,R;cin>>n;L=0,R=n-1;for(inti=0;i<n;++i)cin>>a[i];sort(a,a+n);for(intbit=1<<30;bit;bit>>=1){if((a[L]&bit)||!(a[R]&bit))continue;// 这一位全部相同if((a[R]&bit)&&!(a[R-1]&bit)){// 只有1个1intt=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的个数多于1intl=L,r=R,mid;while(l<r){mid=l+r>>1;if(a[mid]&bit)r=mid;elsel=mid+1;}L=l;}if(R-L<=1)break;}assert(L<R);cout<<(a[L]&a[R]);return0;}

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