CF1878E Iva & Pav

One_JuRuo · 2023-10-06 18:58:56 · 题解

思路

要求从一个点开始最远可以选择那个点使得两点之间的数字的与大于等于 k，最开始想到的是提前预处理出每个点往后若干位的与，因为与只可能变小不可能变大，所以可以二分找到最远的位置，但是这样无论时间还是空间都会爆掉，所以我们考虑优化一下这个办法。

既然不能把每个点的后面的位置的与全部算出来，那么我们可以只算一部分，所以想到了 ST 表。

至于无解，如果当前位置的数本身就比 k 小就一定无解，否则就一定有解。

想到了 ST 表和二分，这道题应该就不难了。

AC code

#include<bits/stdc++.h>
using namespace std;
int T,n,a[200005],q,l,k,st[200005][35],lo[200005],L,R,mid,ans,le;
int main()
{
    for(int i=2;i<=200000;++i) lo[i]=lo[i/2]+1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%d",&a[i]),st[i][0]=a[i];
        for(int i=1;i<=30;++i) for(int j=1;j+(1<<i)-1<=n;++j) st[j][i]=st[j][i-1]&st[j+(1<<(i-1))][i-1];//ST表预处理
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d%d",&l,&k);
            if(a[l]<k){printf("-1 ");continue;}//判无解
            L=l,R=n;
            while(L<=R)//二分找最远位置
            {
                mid=L+R>>1,le=lo[mid-l+1];
                if((st[l][le]&st[mid-(1<<le)+1][le])>=k) ans=mid,L=mid+1;//与重复一个数不会造成影响，所以这里ST表范围重复不影响
                else R=mid-1;
            }
            printf("%d ",ans);
        }
        puts("");
    }
    return 0;
}