『题解』Luogu U184421 退钱

仙山有茗 · 2021-10-07 08:35:40 · 个人记录

该题目背景充分描述了 \sout{€€£} 现状

题目大意

给你一个 n*n 的矩阵，询问 k 次，每次给出一个区间，如果这个区间总和 sum \le m ，输出 Oh,no!，否则输出 Good!。

30pts

直接打暴力，对于每次询问，暴力求 sum： sum=\sum\limits^{x2}_{i=x1}\sum\limits^{y2}_{i=y1}a_{i,j}，然后判断并输出。 注意，题目保证了前 60\% 的数据中 x1,y1 \le x2,y2 所以不需要判断坐标顺序。 代码：

#include <iostream>
using namespace std;
int a[105][105];

int main(){
    int n,m,k;
    int x1,y1,x2,y2;
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> a[i][j];
        }
    }
    cin >> k >> m;
    while(k--){
        int sum=0;
        cin >> x1 >> y1 >> x2 >> y2;
//      不需要判断
        for(int i=x1; i<=x2; i++){
            for(int j=y1; j<=y2; j++){
                sum+=a[i][j];
            }
        }
        if(sum<=m){
            puts("Oh,no!");
        }else{
            puts("Good!");
        }
    }
    return 0;
}

60pts

这里算是给会正解的 OIer 们的良心分了，我把前 60\% 都设成了 x1,y1 \le x2,y2，因为有人不会注意坐标顺序，总得和暴力有点区别吧。

正解就是二维前缀和，可以参考我的博客： 前缀和与差分。

在本题中，坐标 x1,y1 分别等于图中的 i,j，x2,y2 分别等于 i+x,j+y 大家应该很容易想到。

如果大家本来就会二位前缀和但是没注意细节，就会拿 60pts。

代码：

#include <iostream>
using namespace std;
int a[105][105],f[105][105];

int main(){
    int n,m,k;
    int x1,y1,x2,y2;
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> a[i][j];
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
        }
    }
    cin >> k >> m;
    while(k--){
        cin >> x1 >> y1 >> x2 >> y2;
        // 这里的判断你忘掉了，所以60pts。
        if(f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]+f[x1-1][y1-1]<=m){
            puts("Oh,no!");
        }else{
            puts("Good!");
        }
    }
    return 0;
}

100pts

把 60pts 分的代码输入坐标后加入判断坐标顺序代码即可 100pts ：

if(x1>x2) swap(x1,x2);
if(y1>y2) swap(y1,y2);

最后是 AC 代码：

#include <iostream>
using namespace std;
int a[105][105],f[105][105];

int main(){
    int n,m,k;
    int x1,y1,x2,y2;
    cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> a[i][j];
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j];
        }
    }
    cin >> k >> m;
    while(k--){
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1>x2) swap(x1,x2);
        if(y1>y2) swap(y1,y2);
        if(f[x2][y2]-f[x1-1][y2]-f[x2][y1-1]+f[x1-1][y1-1]<=m){
            puts("Oh,no!");
        }else{
            puts("Good!");
        }
    }
    return 0;
}