题解 A-D

A.只需要对奇数和偶数分别讨论切的数量即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
const int mod=998244353;
const int M0D=1e9+7;
const int N=1e1+6;
void solve(){
	    double n;
    int k;
    cin>>n>>k;
    if(k%2==0)
    cout<<fixed<<setprecision(2)<<n*n/((k/2+1)*(k/2+1))<<endl;
    else
    cout<<fixed<<setprecision(2)<<n*n/((k/2+1)*(k/2+2))<<endl;

}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T=1;
	//cin>>T;
	while(T--) solve();
	return 0;
}

B.由于大于m的不可以再去增加，所以只需要对小于m的计算出累加差值，然后将大于m的看有多少个可以降为m就可以了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
int main(){
       ios::sync_with_stdio(false);
       cin.tie(0);
       cout.tie(0) ;
       int n,m;
       cin>>n>>m;
       vector<ll>a(n+1);
       ll ans=0;
       int res=0;
       for(int i=1;i<=n;i++){
              cin>>a[i];
              if(a[i]<=m){
                     ans=ans+m-a[i];
                     res++;
              }
       }
       vector<int>b;
       for(int i=1;i<=n;i++){
              if(a[i]>m){
                     b.push_back(a[i]-m);
              }
       }
       sort(b.begin(),b.end());
       for(int i=0;i<b.size();i++){
              if(ans>=b[i]){
                     res++;
                     ans=ans-b[i];
                     b[i]=0;
              }else{
                     break;
              }
       }
       cout<<res;
    return 0;
}

C.对于第i个区间，前i-1个区间已经跳完了，必定存在于第i-1个区间跳完的可跳到区间，和当前区间求交集，如果存在交集，把可跳区间变为交集区间，否则当前x不可行，显而易见答案单调，考虑二分。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long 
#define endl "\n"
int main(){
       ios::sync_with_stdio(false);
       cin.tie(0);
       cout.tie(0) ; 
    int t=1；
    while(t--){
       int n;
       cin>>n;
       vector<pair<ll,ll>>a(n+1);
       for(int i=1;i<=n;i++){
           int l,r;
           cin>>l>>r;
           a[i]={l,r};
       }

       ll l=0,r=1e9;
       auto camp=[&](pair<ll,ll>a,pair<ll,ll>b){
              if(a.first==b.first) return a.second<b.second;
              return a.first<b.first;
       };
       function<bool(int)> check=[&](ll x){
            ll rl=0,rr=0;
            vector<pair<ll,ll>>v;
            for(int i=1;i<=n;i++){
              rl-=x;
              rr+=x;
              v.push_back({rl,rr});
              v.push_back({a[i].first,a[i].second});
              sort(v.begin(),v.end(),camp);
             // cout<<x<<" "<<rl<<" "<<rr<<endl;
              if(v[1].first>v[0].second){
                     //无交集
                     return false;
              }
              //更新交集区间
              rl=max(v[0].first,v[1].first);
              rr=min(v[0].second,v[1].second);
              
              v.clear();
            }
            return true;
       };
      /// cout<<l<<" "<<r<<endl;
       while(l<r){
              ll mid=(l+r)>>1;
              if(check(mid)) r=mid;
              else l=mid+1;
       }
       cout<<l<<endl;
    }
    return 0;
}

D.由于传送门只能用一次，所以只要正着dp和反着dp各做一遍，注意边界，然后分别对两个传送门已经相加比较，以及和不使用传送门比较即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
const int N=1e3+5;
#define INF 0x3f3f3f3f3f3f3f3f
ll a[N][N];
ll f1[N][N],f2[N][N];
struct Z{
    int l,r;
};
Z z[6];
void solve(){
     int n,m;
     cin>>n>>m;
     for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
     }
     //前缀
     for(int j=1;j<=m;j++)
        f1[1][j]=f1[1][j-1]+a[1][j];
     for(int i=1;i<=n;i++)
        f1[i][1]=f1[i-1][1]+a[i][1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(i==1||j==1) continue;
            f1[i][j]=max(f1[i-1][j],f1[i][j-1])+a[i][j];
        }
    //后缀
    for(int j=m;j>=1;j--)
        f2[n][j]=f2[n][j+1]+a[n][j];
    for(int i=n;i>=1;i--)
        f2[i][m]=f2[i+1][m]+a[i][m];
    for(int i=n;i>=1;i--)
        for(int j=m;j>=1;j--){
            if(i==n||j==m) continue;
            f2[i][j]=max(f2[i+1][j],f2[i][j+1])+a[i][j];
    }
    //
    int t;
    cin>>t;
    while(t--){
    int k;
    cin>>k;
    for(int i=1;i<=k;i++){
        cin>>z[i].l>>z[i].r;
    }
    ll ans=-INF;
    for(int i=1;i<=k;i++)
        for(int j=i+1;j<=k;j++){
            ans=max(ans,f1[z[i].l][z[i].r]+f2[z[j].l][z[j].r]);
            ans=max(ans,f2[z[i].l][z[i].r]+f1[z[j].l][z[j].r]);
            ans=max(ans,f1[n][m]);
        }
    cout<<ans<<endl;
}
      
            
}
const int mod=998244353;
int main(){
       ios::sync_with_stdio(false);
       cin.tie(0);
       cout.tie(0);
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}