CF1873F Money Trees

One_JuRuo · 2023-10-01 10:16:54 · 题解

思路

要求最长长度，想到可以二分答案。

那么现在需要考虑如何快速验证答案是否正确。

可以 O(n) 枚举区间左端点，因为有了长度，所以可以直接获得右端点的值，直接验证右端点是否合法。

因为要求区间的每个数都是右边的数的倍数，所以可以提前预处理每个点最远的满足这个条件的右端点，直接判断合不合法。

还要求和要小于某个值，这个直接前缀和预处理即可。

AC code

// LUOGU_RID: 126800277
#include<bits/stdc++.h>
using namespace std;
long long T,n,k,a[200005],h[200005],l,r,mid,ans,rm[200005];
inline bool check(long long x)
{
    for(long long i=1;i<=n-x+1;++i) if(a[i+x-1]-a[i-1]<=k&&rm[i]>=i+x-1) return 1;//合法
    return 0;//没有合法的
}
int main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&k);
        for(long long i=1;i<=n;++i) scanf("%lld",&a[i]),a[i]+=a[i-1];//前缀和预处理
        for(long long i=1;i<=n;++i) scanf("%lld",&h[i]);
        rm[n]=n;
        for(long long i=n-1;i>=1;--i)
            if(h[i]%h[i+1]==0) rm[i]=rm[i+1];
            else rm[i]=i;//预处理最远达到的合法右端点（仅满足整除条件）
        l=0,r=n;//二分
        while(l<=r)
        {
            mid=l+r>>1;
            if(check(mid)) ans=mid,l=mid+1;
            else r=mid-1;
        }
        printf("%lld\n",ans);
    }
}