E.

如果我们枚举的天数天数是

i,j,k三天

我们要减去的是 (i)*d+(j-i)*d+(k-j)*d=k*d

所以我们直接枚举每一天为最后一天，用优先队列存储前i天中最大的m个数

#include<bits/stdc++.h>
using namespace std;
const int N =1e6,mod=1e9+7;
#define int long long
int n,m,k;int a[N],b[N];
void solve(){cin>>n>>m>>k;for(int i=1;i<=n;i++) cin>>a[i];priority_queue<int,vector<int>,greater<int>> q;int res=0;int sum=0;for(int i=1;i<=n;i++){if(a[i]<0) continue;q.push(a[i]);sum+=a[i];while(q.size()>m){sum-=q.top();q.pop();}res=max(res,sum-k*i);}cout<<res<<"\n";
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();return 0;
}

F.思路大概就是枚举第一个魔法处理掉哪些怪物，第二个魔法处理剩下怪物，

可以注意到其实只关心那些怪物血量的总和，所以我们用01背包处理出不同怪物的血量组合的总血量，然后枚举用第一个魔法处理当前怪物，第二个魔法处理剩下怪物

#include<bits/stdc++.h>
using namespace std;
const int N =1100,mod=1e9+7;
int n,w,f;int a[N],b[N];
void solve(){cin>>w>>f;cin>>n;int sum=0;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}vector<int> dp(sum+1);dp[0]=1;for(int i=1;i<=n;i++){for(int j=sum;j>=a[i];j--){dp[j]|=dp[j-a[i]];}}int ans=sum;for(int i=0;i<=sum;i++){if(dp[i]){ans=min(ans,max((i+w-1)/w,(sum-i+f-1)/f));}}cout<<ans<<"\n";
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();return 0;
}

G.

首先手玩一下只有两个数

[6,9]->>>[8,10]->>[10,11]->>[12,12]

其实挺明显，就是让相邻的两个数差值拉平成一样，因为每次相邻的数差距只会减少1

且重复就删去，所以一定可以追上

换句话就是最后的数是最大的数+相邻数的差值的最大值

#include<bits/stdc++.h>
using namespace std;
const int N =1e6,mod=1e9+7;
#define int long long
int n,m,k;int a[N],b[N];void solve() {int n;std::cin >> n;std::vector<int> a(n + 1), b;std::multiset<int> s, d;for (int i = 1; i <= n; i ++) std::cin >> a[i], s.insert(a[i]);b = a;std::sort(b.begin() + 1, b.end());for (int i = 2; i <= n; i ++) d.insert(b[i] - b[i - 1]);int q;std::cin >> q;while (q --) {int pos, x;std::cin >> pos >> x;if (n == 1) {std::cout << x << " ";continue;}int last = a[pos];a[pos] = x;auto it = s.lower_bound(last);if (it != s.end() && next(it) != s.end())d.erase(d.lower_bound(*(next(it)) - *it));if (it != s.begin())d.erase(d.lower_bound(*it - *(prev(it))));if (it != s.end() && it != s.begin() && next(it) != s.end())d.insert(*(next(it)) - *(prev(it)));s.erase(it);s.insert(x);it = s.lower_bound(x);if (it != s.end() && next(it) != s.end())d.insert(*(next(it)) - *it);if (it != s.begin())d.insert(*it - *(prev(it)));if (it != s.end() && it != s.begin() && next(it) != s.end())d.erase(d.lower_bound(*(next(it)) - *(prev(it))));std::cout << (*s.rbegin() + *d.rbegin()) << " ";}std::cout << "\n";
}
signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();return 0;
}