自动搬运

查看原文

来自洛谷，原作者为

	Night_sea_64 距离省选还有 +inf 天。

搬运于2025-08-24 22:58:44，当前版本为作者最后更新于2024-05-19 20:27:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先我们知道，如果有两个正整数 $x,y$ 满足 $x\operatorname{and}y=y$ 且 $x\neq y$，即 $y$ 是 $1$ 的位上 $x$ 也是 $1$，剩下的位上 $x$ 也有 $1$，那么答案为 $x$ 肯定比答案为 $y$ 更不容易达到，并且更优。

这种情况下，可以想出一种类似二分答案但又不是的方法：因为我们需要答案最大，所以从高到低位都检验一下这一位能不能是 $1$。

检验方法是假设我们要达到答案为 $t$，从左边开始记录依次记录数的或值 $s$，如果 $s\operatorname{and}t=t$ 时段数 $+1$，$s$ 清零。如果段数 $\ge n-k$ 就说明能成功。

这是因为合并后的每一个数都对应合并前的一个连续段的或值，而合并 $k$ 次，连续段数就是 $n-k$。如果这些或值的与值要达到 $t$，那么 $t$ 的每一个为 $1$ 的位，在这些或值中必须全部为 $1$。

#include<iostream>
using namespace std;
int n,m,k,a[200010];
int lg(int x)
{
    int cnt=0;
    while(x)x>>=1,cnt++;
    return cnt-1;
}
bool chk(int x)
{
    int sum=0,cnt=0;
    for(int i=1;i<=n;i++)
    {
        sum|=a[i];
        if((sum&x)==x)sum=0,cnt++;
    }
    return cnt>=k;
}
int main()
{
    cin>>n>>k;
    k=n-k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        m=max(m,lg(a[i]));
    }
    int now=0;
    for(int i=m;i>=0;i--)
    {
        now+=(1<<i);
        if(!chk(now))now-=(1<<i);
    }
    cout<<now<<endl;
    return 0;
}