题解：按位或

lichenxi111 · 2024-10-04 16:23:49 · 题解

思路

对于二进制，每次 \times 2 操作即为左移一位。

发现对于结果，二进制最高位为 0 一定更优，所以结果的最高位不会高于 a_{i} 的最高位。

那我们可以先求出不进行操作的答案，从最高位开始向低位枚举，如果这一位为 1，尝试能否将这一位变为 0。

我们发现如果想让这一位变为 0，根据按位或，必须让所有数的这一位都为 0，且为了让答案更优，不能改变更高位的已经确定的状态。所以枚举每一个数，并计算多少次操作可以让这个数的这一位变为 0 且操作过程中不能改变更高位的状态。最后如果可用操作数足够，那么这一位可以为 0，记录答案。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+100;
int n,m;
int a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0) , cout.tie(0);
    cin>>n;
    int mx=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        mx=max(mx,__lg(a[i]));
    }
    cin>>m;
    int ans=1ll<<mx,tt;
    for(int j=mx-1;j>=0;j--)
    {
        int cnt=0,tmp=1ll<<60;
        tmp--;
        for(int i=0;i<j;i++)tmp^=(1ll<<i);
        for(int i=1;i<=n;i++)
        {
            tt=a[i];
            while((((tt&tmp)|ans)!=ans)&&cnt<=m)
            {
                if(__lg(tt)>mx)cnt=m+1;
                cnt++;
                tt<<=1;
            }
        }
        if(cnt>m)ans|=1ll<<j;
    }
    cout<<ans;
}