题解：B4157 [厦门小学生 C++ 2023] 数据核心

· · 题解

在写这道题之前请先学会二维前缀和。
本篇题解不会讲解任何有关前缀和的知识，不会请出门左转。

Solution

20pts

这是最简单的做法。对于每一次询问，暴力枚举右下角，接着再暴力求出这个区间内的和，时间复杂度 O(Qn^2m^2)。
由于过于简单，代码就不给了。

80pts

用上二维前缀和，对于每一次询问枚举右下角，O(1) 直接求出区间内的和，取最大值即可。
时间复杂度 O(Qnm)。
参考代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
unordered_map<int,int> a[100005],qzh[100005],anss[100005];
int n,m,Q,x,y;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    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++)
        for(int j = 1;j<=m;j++)
            qzh[i][j]=qzh[i-1][j]+qzh[i][j-1]-qzh[i-1][j-1]+a[i][j];
    cin>>Q;
    while(Q--){
        int ans=-1e18;
        cin>>x>>y;
        if(anss[x][y]){
            cout<<anss[x][y]<<'\n';
            continue;
        }
        for(int i = x;i<=n;i++){
            for(int j = y;j<=m;j++){
                ans=max(ans,qzh[i][j]-qzh[x-1][j]-qzh[i][y-1]+qzh[x-1][y-1]);
            }
        }
        cout<<ans<<'\n';
        anss[x][y]=ans;
    }
    return 0;
}
/*
这里的80分做法不太正经，因为用上了unordered_map，所以很浪费时间，加上一个记忆化才能卡到80。。。
建议使用vector来解决 
*/

100pts

考虑提前预处理好答案数组。
原本暴力预处理要四重循环，我们考虑只用三重循环来解决。
剩下的一重跑哪里去了？很简单，我们枚举的矩阵是宽为 1 的不就好了？那要怎样操作呢？这样为什么是正确的呢？
先说一下是怎样枚举的。外面两重循环，一重是 l 从 1 到 n，另一重是 r 从 l 到 n，里面那一重是 i 从 m 到 1。
这是对于这样操作的一点解释：
这里有点像最大子段和。
当然，如果 n 取到 10^5，O(Q+n^2m) 的时间复杂度肯定是炸掉的。但是同理，如果 n 太大我们可以选择 m，只是操作倒过来了而已。
时间复杂度 O(Q+nm\sqrt{nm})。可以通过此题。

AC code

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,Q,x,y,last;
#define f(x,y,xx,yy) qzh[xx][yy]-qzh[xx][y-1]-qzh[x-1][yy]+qzh[x-1][y-1]
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    vector<int> a[n+5],qzh[n+5],ans[n+5];
    for(int i = 0;i<=n+1;i++) 
        for(int j = 0;j<=m+1;j++) 
            a[i].push_back(0),
            ans[i].push_back(-1e15),
            qzh[i].push_back(0);
    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++)
        for(int j = 1;j<=m;j++)
            qzh[i][j]=qzh[i-1][j]+qzh[i][j-1]-qzh[i-1][j-1]+a[i][j];
    if(n<=m)
        for(int l = 1;l<=n;l++)
            for(int r = l;r<=n;r++){
                last=0;
                for(int i = m;i>=1;i--)
                    ans[l][i]=max(ans[l][i],f(l,i,r,i)+max(0ll,last)),last=f(l,i,r,i)+max(0ll,last);
            }
    else
        for(int l = 1;l<=m;l++)
            for(int r = l;r<=m;r++){
                last=0;
                for(int i = n;i>=1;i--)
                    ans[i][l]=max(ans[i][l],f(i,l,i,r)+max(0ll,last)),last=f(i,l,i,r)+max(0ll,last);
            }
    cin>>Q;
    while(Q--)
        cin>>x>>y,
        cout<<ans[x][y]<<'\n';
    return 0;
}