题解:AWC 0005
前提
难得的一命通关，无罚时。
A
ll n, a[N], k, sum;
int main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]%k==0) sum+=a[i];}cout<<sum;
}
B
ll n, a[N], k, m, sum;
int main(){cin>>n>>m>>k;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]<k) sum++;}for(int i=1;i<=m;i++){ll x, y;cin>>x>>y;if(a[x]<k&&y>=k){sum--;}if(a[x]>=k&&y<k){sum++;}a[x]=y;}cout<<sum;
}
C
ll n, a[N], k, sum, b[N];
int main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];b[i]=a[i];}for(int i=1;i<n;i++){if(b[i+1]<b[i]-k){b[i+1]=b[i]-k;}}for(int i=n-1;i>=1;i--){if(b[i]<b[i+1]-k){b[i]=b[i+1]-k;}}for(int i=1;i<=n;i++){sum+=b[i]-a[i];}cout<<sum;
}
D
思路
二分答案。
代码
ll n, a[N], k;
bool check(ll mid){ll sum=0, w=0;for(int i=1;i<=n;i++){sum+=a[i];if(sum>=mid){sum=0;w++;}}return w>=k;
}
int main(){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}ll l=-1, r=1e16;while(l+1!=r){ll mid=l+r>>1;if(check(mid)){l=mid;}else r=mid;}cout<<l;
}
E
思路
一个区间问题，用个st表或线段树都可以。
代码
int n, q;
ll f[N<<2];
void build(int i,int l,int r){if(l==r){cin>>f[i];return;}int mid=l+r>>1;build(ls,l,mid);build(rs,mid+1,r);f[i]=max(f[ls],f[rs]);
}
ll ask(int i,int l,int r,int x,int y){if(l>y||r<x){return 0;}if(l>=x&&r<=y){return f[i];}int mid=l+r>>1;return max(ask(ls,l,mid,x,y),ask(rs,mid+1,r,x,y));
}
int main(){cin>>n>>q;build(1,1,n);for(int i=1;i<=q;i++){ll l, r;cin>>l>>r;cout<<ask(1,1,n,l,r)<<'\n';}
}
后续
因为肯定无法天天打，所以以后这个AWC题解都不会怎么出。
本文来自 NoiPLE ，转载请注明原文链接：https://www.cnblogs.com/noiple-dequeee/p/19613392