洛谷-B3930 [GESP202312 五级] 烹饪问题 题解

题意描述给定一个数列{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​最大。约定记号设最优解的ii0ii_0ii0​jj0jj_0jj0​。也就是当ii0,jj0ii_0,jj_0ii0​,jj0​时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。初始时l1,rnl1,rnl1,rn。先将所有数从小到大排序从高到低检查每一位分讨这一位上的情况逐步缩小最优解所在范围。这位全部相同。答案显然与这一位无关l,rl,rl,r不用改动。这位上有且仅有一个111位于数列末尾。则最优解的这位一定为000将末尾的数这一位改成000并插入排序。当前位为111的数多于111个。则可以确定最优解这一位一定是111。二分出首个这一位为111的位置sss并令l←sl\leftarrow sl←s。最后当[l,r][l,r][l,r]范围缩小到两个数时可以确定i0l,j0ri_0l,j_0ri0​l,j0​r并求出最优解。时间复杂度O(nlog⁡n)O(n \log n)O(nlogn)。Code#includebits/stdc.husingnamespacestd;constexprintN1e65;inta[N];intmain(){cin.tie(0)-sync_with_stdio(0);intn,L,R;cinn;L0,Rn-1;for(inti0;in;i)cina[i];sort(a,an);for(intbit130;bit;bit1){if((a[L]bit)||!(a[R]bit))continue;// 这一位全部相同if((a[R]bit)!(a[R-1]bit)){// 只有1个1intta[R]^bit,i;for(iR-1;iLa[i]t;--i)a[i1]a[i];a[i1]t;}else{// 1的个数多于1intlL,rR,mid;while(lr){midlr1;if(a[mid]bit)rmid;elselmid1;}Ll;}if(R-L1)break;}assert(LR);cout(a[L]a[R]);return0;}Update 2025.6.15修正错误的图片。Update 2025.6.16微调公式。Update 2025.12.6优化语言表达和代码格式。