题目比较套路,好久没写题解了,写一下吧~第二题:第二题思路比较清晰,由于区间不重叠,直接给区间排个序,然后枚举每一个区间右端点作为最后选取的线段边界,二分左端点即可。#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 998244353using 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 998244353using 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;}// 200000const 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;}
点赞 17
评论 4
全部评论

相关推荐

勇敢牛牛不怕困难,希望能过初筛
投递韶音科技等公司10个岗位
点赞 评论 收藏
分享
07-07 17:06
已编辑
深圳技术大学 golang
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务