题解：P10512 序列合并

Night_sea_64 · 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;
}