专栏文章

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

xxiaoniu142857
B3930题解参与者 6已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miqmctiz
此快照首次捕获于
2025/12/04 07:09
3 个月前
此快照最后确认于
2025/12/04 07:09
3 个月前
查看原文
看到各路大神都在用贪心，我就来发一个另类做法吧 (●'◡'●)。

题意描述

给定一个数列 {ai}i=1n\{a_i\}_{i=1}^n，求找到一组 i,j (i≠j)i,j~(i\neq j)，使 ai&aja_i \& a_j 最大。

约定记号

约定最优解的 ii 取值为 i0i_0，jj 取值为 j0j_0。
即当 i=i0,j=j0i=i_0,j=j_0 时，ai&aja_i \& a_j 最大。

解题思路

我们可以从高到低枚举每一位，逐步缩小寻找最优解的范围。
设当前寻找最优解的范围是 [l,r][l,r]，即目前可以钦定 i0,j0∈[l,r]i_0,j_0\in [l,r]。
初始时，l=1,r=nl=1,r=n。
先将所有数升序排序，考虑排序后这位上的情况，分讨一下。
  1. 这位全部相同
    答案与这一位无关，可以直接跳过，l,rl,r 不用改动。
  1. 这位上有且仅有一个 11，位于数列末尾
    则最优解的这位一定为 00，将末尾的数这一位置 00，重新排序。
    因为只修改了末尾一个数，可以 O(n)O(n) 插入排序，而 l,rl,r 不用改动。
  1. 这一位上先是一段 00，然后是一段 11
    先二分分界点，设首个这位为 11 的数是 asa_s。
    可以确定 i0,j0∈[s,r]i_0,j_0\in [s,r]，则令 l←sl\leftarrow s，缩小求解区间。
最后，当 [l,r][l,r] 范围缩小到两个数，即 r=l+1r=l+1，则可以确定 i0=l,j0=ri_0=l,j_0=r，求出最优解。

时间复杂度分析

首先需要对所有数排序，复杂度 O(nlog⁡n)O(n \log n)。
后面缩小区间的操作最多进行 3131 次，最坏每次插入排序有 O(n)O(n) 的时间复杂度，则这一步复杂度为 O(n)O(n)，常数有亿点点大。
所以总时间复杂度为 O(nlog⁡n)O(n \log n)，瓶颈在排序。

Code

注意代码下标是从 00 开始的。
CPP
#include <cstdio>
#include <algorithm>
using namespace std;
char buf[1<<20],*p1,*p2;
int a[1000000];
inline char gc()  // 快速读字符
{
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==buf?EOF:*p1++;
}
inline void read(int &x)  // 快读
{
    int c;
    while((c=gc())<'0'||c>'9');
    for(x=c^48;(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^48));
}
int main()
{
	int n,st,ed;
	read(n);
    st=0,ed=n-1;  // 当前寻找最优解的范围
	for(int i=0;i<n;++i)
    {
        read(a[i]);
    }
    sort(a,a+n);
    for(int bit=1<<30;bit;bit>>=1)  // 从高到低按位枚举，bit标识当前位
    {
        if((a[st]&bit)||!(a[ed]&bit))  // 这位上全部相同，跳过
        {                              // 即最小的数这位为1，或最大的数这位为0
            continue;
        }
        if((a[ed]&bit)&&!(a[ed-1]&bit))  // 只有最后一个数这位为1
        {
            int t=a[ed]^=bit,i;
            for(i=ed-1;i>=st&&a[i]>t;--i)  // 单轮插入排序
            {
                a[i+1]=a[i];
            }
            a[i+1]=t;
        }
        else
        {
            int l=st,r=ed,mid;
            while(l<r)  // 二分0段和1段的分界点，找到第一个这位为1的数
            {
                mid=(l+r)>>1;
                if(a[mid]&bit) r=mid;
                else l=mid+1;
            }
            st=l;  // 缩小范围
        }
        if(ed-st<=1)  // 范围缩小到2个数以内，找到答案
        {
            break;
        }
    }
    printf("%d",a[st]&a[ed]);
	return 0;
}
完结撒花 ★,°:.☆(￣▽￣)/$:.°★。
Update 2025.6.15：修正错误的图片。
Update 2025.6.16：微调公式。

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...