小红书7.23提前批笔试2，3题

题目比较套路，好久没写题解了，写一下吧~

第二题:

第二题思路比较清晰，由于区间不重叠，直接给区间排个序，然后枚举每一个区间右端点作为最后选取的线段边界，二分左端点即可。

#include <bits/stdc++.h>
#include <numeric>
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define PII pair<long long, long long>
#define ll long long
#define x first
#define y second
#define mod 998244353
using namespace std;
inline ll gcd(ll a, ll b)
{
   if (b)
    {
      return gcd(b, a % b);
    }
      return a;
}
inline ll qpow(ll a, ll b, ll p)
{
   ll ans = 1;
   a = (a % p + p) % p;
   for (; b; b >>= 1)
    {
       if (b & 1)
         ans = (a * ans) % p;
       a = (a * a) % p;
    }
    return ans;
}
int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int r = exgcd(b, a % b, x, y);
    int tmp = y;
    y = x - a / b * y;
    x = tmp;
    return r;
}
// [0,n]  截取k
// 一共有m个区间
bool cmp(const PII& p1,const PII& p2){
  return p1.second < p2.second;
}
ll n,m,k;
void solve()
{
  cin >> n >> m >> k;
  vector<PII> edges;
  for(int i=1;i<=m;++i){
    ll l1,r1;
    cin >> l1 >> r1;
    edges.push_back({l1,r1});
  }
  sort(edges.begin(),edges.end(),cmp);

  edges.insert(edges.begin(),{-1e9,-1e9});

  vector<ll> pre(m + 1,0);
  for(int i=1;i<=m;++i){
    pre[i] = pre[i-1] + edges[i].second - edges[i].first;
  }

  ll ans = 0;
  for(int i=1;i<=m;++i){
    ll target = edges[i].second - k;
    int l = 1,r = i;
    while(l < r){
      int mid = (l + r) >> 1;
      if(edges[mid].first >= target){
        r = mid;
      }
      else l = mid + 1;
    }
    if(edges[l].first >= target){
      ans = max(ans,pre[i] - pre[l-1] + max(edges[l-1].second - target,0ll));
    }else{
      ans = max(ans,pre[i]);
    }
  }
  cout << ans << endl;
}
int main()
{
    IOS;
    int _ = 1;
    while (_--)
    {
         solve();
    }
     return 0;
}

第三题：

第三题的话由于只多一个是否修改x的状态，不妨定义为f[i][0/1]为前i个元素是否修改过的最大子数组和，转移方程的话见代码:

#include <bits/stdc++.h>
#include <numeric>
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define PII pair<int, int>
#define ll long long
#define x first
#define y second
#define mod 998244353
using namespace std;
inline ll gcd(ll a, ll b)
{
   if (b)
    {
      return gcd(b, a % b);
    }
      return a;
}
inline ll qpow(ll a, ll b, ll p)
{
   ll ans = 1;
   a = (a % p + p) % p;
   for (; b; b >>= 1)
    {
       if (b & 1)
         ans = (a * ans) % p;
       a = (a * a) % p;
    }
    return ans;
}
int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int r = exgcd(b, a % b, x, y);
    int tmp = y;
    y = x - a / b * y;
    x = tmp;
    return r;
}

// 200000
const int N = 200010;
int a[N];
ll f[N][2]; // 0/1表示是否修改过了
int n,x;

void solve()
{
    cin >> n >> x;
    ll ans = -1e18;
    for(int i=1;i<=n;++i){
        cin >> a[i];
    }
    for(int i=0;i<=n;++i){
        f[i][0] = f[i][1] = -1e18;
    }
    f[0][0] = 0;
    for(int i=1;i<=n;++i){
        f[i][0] = max(f[i][0],f[i-1][0] + a[i]);
        f[i][0] = max(f[i][0],1ll * a[i]);      // 从头取
        f[i][1] = max(f[i][1],f[i-1][1] + a[i]);
        f[i][1] = max(f[i][1],f[i-1][0] + x);
        f[i][1] = max(f[i][1],1ll * x);

        ans = max(ans,max(f[i][0],f[i][1]));
    }
    cout << ans << endl;
}
int main()
{
    IOS;
    int _;
    cin >> _;
    while (_--)
    {
         solve();
    }
     return 0;
}