hdu5358

尺度法（简单数学）

题目链接 解一 感谢bigbigship

要被打死的预编译...

狗头保命

// 解零 暴力
// 解一
/*
尺度法
保证 tp_sum (inferior,superior]
[枚举]一个区间的[左端点]，对于一个给定的左端点，因为f(i,j)在给定i的情况下单调，
我们可以用尺举发求得一个区间[l,r]，使得区间内的j (l<=j<=r)都瞒住sum(i,j)+1=k;
然后区间(i+j)的和可以表示为 i*(r-l+1) + (r+l)*(r-l+1)/2;[1]
[1]: https://blog.csdn.net/bigbigship/article/details/47343299
*/
// 解二
/*
尺度法
保证 tp_sum (inferior,+inf] 
[log2(inferior)+1] + 1 == [log2(inferior<<1)+1] => 累加
//---
所有区间都满足 inferior=0 => ans = n*(n*n+2*n+1)/2 //算个通项
一但[l,r]满足inferior，则[l,r...n]都满足inferior => ans += (n-r+1)*(r+n)/2+(n-r+1)*l
*/

#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned char uchar;
typedef unsigned int uint;

// #pragma GCC optimize(2)
#define rint register int
#define rchar register char
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define rep_r(i,a,b) for(rint i=a;i<=b;i++)
#define per_r(i,a,b) for(rint i=a;i>=b;i--)
#define maxn 10000
namespace fast{
    inline char GET_CHAR(){//读优卡常 
        static char buf[maxn],*p1=buf,*p2=buf;
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxn,stdin),p1==p2)?EOF:*p1++;
    }
    template<class T>inline void read(T &x){//读优背一下就OK 
        x=0;rchar f=0;rchar ch=GET_CHAR();
        while(ch<'0'||ch>'9')  {f|=(ch=='-');ch=GET_CHAR();}
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=GET_CHAR();}x=f?-x:x;
    }
    template<class T>inline T min(T &a,T &b){return a<b?a:b;}
    template<class T>inline T max(T &a,T &b){return a>b?a:b;}
    template<class T>inline T abs(T &a){return a>=0?a:-a;}
    template<class T>inline T sgn(T &a){return a>=0?+1:-1;}
    template<class T>inline void swap(T &a,T &b){T tp=a;a=b;b=tp;}
    template<class T>inline void write(T x){
        if(x<0){
            putchar('-');
            x=-x;
        }
        if(x>9) 
            write(x/10);
        putchar(x%10|'0');// '1' 049(DEC) 0011'0001(BIN)
    }
};
//---
// #define TIME
// #define DEBUG
// #define B_S
const int MAX_N=1e5+5;
const int MAX_A=1e5;
ull n,A[MAX_N];
ull total;

#ifdef B_S
ull sum[MAX_N];
inline int log2_int(ull x){//register int
    rchar res=0;//register int
    while(x>>=1)res++;
    return res;
}
ull bad_solution(){
    //O(n^2)
    ull ans=0;
    rep_r(i,1,n) rep_r(j,i+1,n)
        ans+=(log2_int(sum[j]-sum[i-1])+1)*(i+j);
    // ans<<=1;
    // cout<<ans<<endl;
    rep_r(i,1,n){
        ans+=(log2_int(A[i])+1)*(i<<1);
    }
    return ans;
}
#endif

#ifndef B_S
ull solution(){
    //O(n*log(n))
    ull ans=0;
    ull inferior=2;
    // 特判 log(2,0)=0
    ans=n*(n*n+2*n+1)/2;//被[1]强制转换和[2]优先级坑了
#ifdef DEBUG
        putchar('*'); fast::write(ans); putchar('\n');
#endif
    while(inferior<=total){
//init
        rint l,r;//1e5
        ull tp_sum;//1e10
        l=r=1;tp_sum=A[r];
        while(r<=n){
            if(tp_sum<inferior){
                tp_sum+=A[++r];
            }else{
                ans+=(n-r+1)*(r+n)/2+(n-r+1)*l;
                tp_sum-=A[l++];
            }
        }
#ifdef DEBUG
        putchar('-'); fast::write(ans); putchar('\n');
#endif
        inferior<<=1;
    }
    return ans;
}
#endif

int main(){
#ifdef TIME
    clock_t start_time=clock();
#endif
    int _;
    fast::read(_);
    while(_--){
//init
        total=0;
        fast::read(n);
        rep_r(i,1,n)
#ifndef DEBUG        
            fast::read(A[i]),
#endif
#ifdef DEBUG
            A[i]=100000,
#endif
#ifdef B_S
            sum[i]=sum[i-1]+A[i];
#endif
#ifndef B_S
            total+=A[i];
#endif
#ifdef DEBUG
        printf("total: ");fast::write(total);putchar('\n');
#endif
#ifdef B_S
        fast::write(bad_solution());putchar('\n');
#endif
#ifndef B_S
        fast::write(solution());putchar('\n');
#endif
    }

#ifdef TIME
    printf("%.2f",(double)(clock()-start_time)/CLOCKS_PER_SEC);
#endif
    return 0;
}

---

本文章使用limfx的vsocde插件快速发布