小红书笔试AK7.23

第一题签到

第二题，题目讲的有点模糊，很容易让人读不懂题，大致就是给你多个不重叠的区间，然后你需要选择一个长度为k的连续区间，使其中被标记的空间数量最大。解法：二分搜索

第三题，题目意思大致就是给定一个数组与一个数字val，你可以任意的讲数组中的一个值替换成val，求最大连续子数组和。解法：dp，存储数组中每个下标的状态，0代表到这个位置还没有替换，1代表已经替换过一次，从而推导状态转移方程。

题目挺有意思的，整体难度不大，就是第二题题目描述不是很清楚。

//第一题
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    ll n,k;
    cin>>n>>k;
    ll ans=n*(n+1)/2;
    ans=ans*k;
    cout<<ans<<endl;
}

//第三题
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
const int N = 2e5+5;
ll k[N];
ll dp[N][2];
int main(){
    int T;
    cin>>T;
    while(T--){
        memset(dp,0,sizeof(dp));
        ll n,val;
        ll ans=-10000000009;
        cin>>n>>val;
        for(int i=0;i<n;i++){
            cin>>k[i];
        }
        dp[0][0]=k[0];
        dp[0][1]=val;
        ans=max(ans,dp[0][1]);
        ans=max(ans,dp[0][0]);

        for(int i=1;i<n;i++){
            dp[i][1]=max(max(dp[i-1][1]+k[i],k[i]),max(dp[i-1][0]+val,val));
            dp[i][0]=max(dp[i-1][0]+k[i],k[i]);
            ans=max(ans,dp[i][1]);
            ans=max(ans,dp[i][0]);
        }
        cout<<ans<<endl;
    }
}


//第二题
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1e5+5;
struct kk{
    ll bepos;
    ll enpos;
    ll val;
    ll sum;
}Mess[N];
bool cmp(kk a,kk b){
    return a.bepos<b.bepos;
}
ll erfen(ll low,ll high,ll aim){
    ll mid=(low+high)/2;
    while(low<high){
        ll x=Mess[mid].enpos;
        if(x>=aim){
            high=mid;
        }else{
            low=mid+1;
        }
        mid=(low+high)/2;
    }
    return high;
}
int main(){
    ll n,m,k;
    cin>>n>>m>>k;
    Mess[0].sum=0;
    for(int i=1;i<=m;i++){
        cin>>Mess[i].bepos>>Mess[i].enpos;
        Mess[i].val=Mess[i].enpos-Mess[i].bepos;
        Mess[i].sum=Mess[i-1].sum+Mess[i].val;
    }
    Mess[m+1].bepos=n+1;
    Mess[m+1].enpos=n+1;
    Mess[m+1].sum=Mess[m].sum;
    sort(Mess+1,Mess+1+m,cmp);
    // for(int i=1;i<=m+1;i++){
    //     cout<<Mess[i].bepos<<' '<<Mess[i].enpos<<endl;
    // }
    ll ans=0;
    for(int i=1;i<=m;i++){
        ll vals=0;
        int be=Mess[i].bepos;
        int en=Mess[i].bepos+k;
        // cout<<be<<' '<<en<<"  message"<<endl;
        if(en>=n){
            vals=Mess[m].sum-Mess[i-1].sum;
        }else{
            int nextindex=erfen(i,m+1,en);
            vals=Mess[nextindex-1].sum-Mess[i-1].sum;
            if(en>Mess[nextindex].bepos){
                vals+=en-Mess[nextindex].bepos;
            }
            // cout<<"index: "<<nextindex<<endl;
            // cout<<nextindex<<endl;
        }
        ans=max(ans,vals);

    }
    cout<<ans<<endl;
}