7.23小红书笔试ak

T1:直接模拟 或者上等差数列求和公式都可以

void solve(int u){
    cin>>n>>k;
    ll res=0;
    for(int i=1;i<=n;i++){
        res+=1ll*i*k;
    }
    cout<<res<<endl;
}

T2:贪心+二分

先按照左端点排序，枚举第i个区间 贪心的思想：肯定先把第i个区间的数全选了，然后再往左枚举 去二分找到能选的一个最大的区间下标

void solve(int u){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>w[i].x>>w[i].y;
        w[i].x++;
    }
    sort(w+1,w+m+1);
    for(int i=1;i<=m;i++){
        int len=w[i].y-w[i].x+1;
        s[i]=s[i-1]+len;
    }
    int res=0;
    for(int i=1;i<=m;i++){
        int len1=s[i]-s[i-1];
        if(len1>=k){
            cout<<k<<endl;
            return;
        }
        int target=w[i].x-k+len1;
        int l=1,r=i-1;
        while(l<r){
            int mid=l+r>>1;
            if(w[mid].y>=target)r=mid;
            else l=mid+1;
        }
        if(w[r].y>=target){
            int len2=s[i-1]-s[r]+w[r].y-max(target,w[r].x)+1;
            res=max(res,len1+len2);
        }

    }
    cout<<res<<endl;
}

T3:经典前后缀分解：首先考虑不替换x 就是LeetCode53最大子数组和

替换的话 枚举替换第i个位置,把整个区间拆分成左右两个部分 最大和就是x+max(0,left)+max(0,right)

right可以使用dp预处理

void solve(int u){
    cin>>n>>x;
    for(int i=0;i<n;i++){
        cin>>w[i];
    }
    ll res=-1e18;
    memset(g,-0x3f,sizeof g);
    for(int i=n-1;i>=0;i--){
        g[i]=max(g[i+1],0ll)+w[i];
        res=max(res,g[i]);
    }
    ll s=0;
    for(int i=0;i<n;i++){
        s=max(0ll,s);
        res=max(res,s+x+max(0ll,g[i+1]));
        s+=w[i];
    }
    cout<<res<<endl;
}