寒假集训营题解2

欢宴的独奏家‌

2026-02-10 15:21:50

发布于：浙江

0阅读

0回复

0点赞

子矩阵和：

#include <bits/stdc++.h>
using namespace std;
int n,m,q,a[1010][1010],pre[1010][1010];
int main(){
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
}
}
while(q--){
int x1,x2,y1,y2;
cin>>x1>>y1>>x2>>y2;
cout<<pre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]+pre[x1-1][y1-1]<<endl;
}
return 0;
}

子矩阵最大和：

#include <bits/stdc++.h>
using namespace std;
int n,a[130][130],pre[130][130];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];

    }
}
int x1,y1,x2,y2;
int mx=-1e9;
for(int x1=1;x1<=n;x1++){ 
    for(int y1=1;y1<=n;y1++){
        for(int x2=x1;x2<=n;x2++){
            for(int y2=y1;y2<=n;y2++){
                mx=max(mx,pre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]+pre[x1-1][y1-1]);
            }
        }
    }
}
cout<<mx;
return 0;

}

矩阵中的最大得分：

#include <bits/stdc++.h>
using namespace std;
int n,m,a[1010][1010],pre[1010][1010];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
pre[i][0]=1e9;
}
for(int j=1;j<=m;j++){
pre[0][j]=1e9;
}
int ans=-1e9;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
pre[i][j]=min(pre[i-1][j],pre[i][j-1]);
ans=max(ans,a[i][j]-pre[i][j]);
pre[i][j]=min(pre[i][j],a[i][j]);
}
}
cout<<ans;
return 0;
}

最小平均差：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n;
long long a[N],pre[N],s[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
pre[i]+=pre[i-1]+a[i];
}
for(int i=n;i>=1;i--){
s[i]+=s[i+1]+a[i];
}
long long ans=1e9,id=0;
for(int i=1;i<=n;i++){
long long l=pre[i],r=s[i+1];
if(l>0) l/=i;
if(r>0) r/=n-i;
long long res=abs(l-r);
if(ans>res){
ans=res;
id=i-1;
}
}
cout<<id;
return 0;
}

得到更多分数的最少关卡数目：

#include <bits/stdc++.h>
using namespace std;
int n;
int a[200010],pre[200010],s[200010];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+(a[i]?1:-1);
}
for(int i=n;i>=1;i--){
s[i]=s[i+1]+(a[i]?1:-1);
}
for(int i=1;i<n;i++){
if(pre[i]>s[i+1]){
cout<<i;
return 0;
}
}
cout<<"-1";
return 0;
}

接雨水：

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
long long a[N],n,mx1[N],mx2[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
mx1[i]=max(mx1[i-1],a[i]);
}
for(int i=n;i>=1;i--){
mx2[i]=max(mx2[i+1],a[i]);
}
long long ans=0;
for(int i=2;i<n;i++){
ans+=max(0ll,min(mx1[i-1],mx2[i+1])-a[i]);
}
cout<<ans;
return 0;
}