当前位置：首页 > news >正文

HDU5358 First One（尺取法+数学）

news 来源：原创 2024/5/18 20:02:07

题目链接
在这里插入图片描述
1.题目大意：给出一个式子，求所有子序列代入此式的和

2.第一眼可能会想到O(n²)暴力枚举子序列，但是很明显1e5的范围O(n²)过不了。不难发现由于向下取整，那么log₂S(i,j)一定是整数，那么也就是S(i,j)如果在[2^p,2^p+1)区间内答案都是p。我们先来测试一下，数据的极限——1e5个1e5数，最多达到2³³，因为后面还加1，因此前式一共有[0-34]，35种结果，那么问题可以变为我们对这35种结果分别计算后面的区间和即可,因此输入我们要计算前缀和
在这里插入图片描述

3.但是怎么求每个k后面的区间和呢，很容易想到的思路是暴力查找符合S(i,j)范围的子区间，但是这样时间复杂度又到O(n²)了，这时尺取的作用就出现了。我们首先枚举每个起点i，对于该起点找到一段区间[L,R]，使得S(i,L)和S(i,R)都满足上面的不等式范围。那么下面肯定要枚举起点i+1了，不难证明
当起点后移之后，因为单调性，那么后面的区间肯定不小于之前的L，还考虑到当前起点可能大于之前的L，因此取二者中较大的那个。至于R就是取当前L和之前R较大者。最后就是合并区间了，假设最后区间为[L,R]，那么区间和为(i+L)+(i+L+1)+…+(i+R)=(2*i+L+R)*(R-L+1)/2

4.不知道为什么C++会TLE，G++就可以过了

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
ll sum[maxn];
int n;
ll ans;

int test(){
    ll x=1;
    int cnt=0;
    while(x*2<1e10){
        cnt++;
        x*=2;
    }
    return cnt;
}

void solve(int k){
    ll L=1LL<<k-1,R=(1LL<<k)-1;
    if(!k) k=1;         //k=0时要特判，此时区间[0,0]正确，但是最后能乘以0
    int l=1,r=0;
    for(int i=1;i<=n;i++){
        l=max(l,i);
        while(l<=n && sum[l]-sum[i-1]<L) l++;
        r=max(l,r);
        while(r<=n && sum[r]-sum[i-1]<=R && sum[r]-sum[i-1]>=L) r++; //r是闭区间r的下一个，因此后面求区间长度时没有减一
        if(l>r) continue;
        ans+=((2LL*i+l+r-1)*(r-l)/2)*k;  //左闭右开的区间[l,r)
    }
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;
    ll x;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&x);
            sum[i]=sum[i-1]+x;
        }
        ans=0;
        for(int i=0;i<=34;i++){
            solve(i);
        }
        printf("%lld\n",ans);
    }
    return 0;
}