今晚 Atcoder AWC 题解
2026-02-10 07:57:38
发布于：浙江
5阅读
0回复
0点赞
AWC请前往我的发布内容中查看更多内容
A
em...直接给代码
#include<bits/stdc++.h>
using namespace std;
int main(){
long long k;
cin>>k;
cout<<k+1;
return 0;
}
时间复杂度:
B
Null
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,l,r,p[200005],mx=-1,id=-1;
cin>>n>>l>>r;
for(int i=1;i<=n;i++)cin>>p[i];
for(int i=1;i<=n;i++){
if(p[i]>=l&&p[i]<=r){
if(p[i]>mx){
mx=p[i];
id=i;
}
}
}
cout<<id;
return 0;
}
时间复杂度:
C
也就这样
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
long long a[200005],s=0;
cin>>n>>k;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
for(int i=0;i<n;i++)s+=a[i];
for(int i=n-1;i>=0&&k>0;i--,k--)s-=a[i];
cout<<s;
return 0;
}
时间复杂度:
D
最后一个选择的城镇是 j，总花费为 cost 时的最大利润，大概就是查找一下吧
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n,m,k;
cin>>n>>m>>k;
vector<int>a(n+1),b(n+1);
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
vector<vector<ll>>dp(n+1,vector<ll>(m+1,-1));
dp[0][0]=0;
for(int i=1;i<=n;i++){
auto ndp=dp;
for(int j=0;j<=n;j++){
for(int c=0;c<=m;c++){
if(dp[j][c]<0)continue;
int nc=c+b[i];
if(nc<=m){
if(j==0)ndp[i][nc]=max(ndp[i][nc],dp[j][c]+a[i]);
else if(i-j<=k)ndp[i][nc]=max(ndp[i][nc],dp[j][c]+a[i]);
}
}
}
dp=move(ndp);
}
ll ans=0;
for(int j=0;j<=n;j++)for(int c=0;c<=m;c++)ans=max(ans,dp[j][c]);
cout<<ans;
return 0;
}
E:
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
vector<int>h(n);
for(int i=0;i<n;i++)cin>>h[i];
deque<int>mn,mx;
int ans=-2e9;
for(int i=0;i<n;i++){
while(!mn.empty()&&mn.front()<=i-k)mn.pop_front();
while(!mx.empty()&&mx.front()<=i-k)mx.pop_front();
while(!mn.empty()&&h[mn.back()]>=h[i])mn.pop_back();
while(!mx.empty()&&h[mx.back()]<=h[i])mx.pop_back();
mn.push_back(i);
mx.push_back(i);
if(i>=k-1){
ans=max(ans,h[mx.front()]-h[mn.front()]);
}
}
cout<<ans;
return 0;
}
嗯，写完了
有帮助，赞一个