C/C++教程

Codeforces Round #745 (Div. 2) C. Portal 二维前缀和简单总结

本文主要是介绍Codeforces Round #745 (Div. 2) C. Portal 二维前缀和简单总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

https://codeforces.com/contest/1581/problem/C
题目意思是问在给定的 01 01 01矩阵中,横向长度至少为 5 5 5,纵向长度至少为 4 4 4,把这样一个矩形的四周除了四个顶点其他部分都变成 1 1 1,矩形内部全都变成 0 0 0,问最少需要多少次操作,每次操作可以把一个位置的 1 1 1变成 0 0 0,或者把一个位置的 0 0 0变成 1 1 1

  • 题目意思读懂以后,我们应该能够形成一个思路,就是找到所有的这样符合条件的矩形,看需要进行多少次操作,取其中最小的操作数即可,一个矩形需要进行的操作数量应该是他内部矩形的 1 1 1的数量加上边上除了顶点之外的 0 0 0的数量,如何高效操作呢?这里简单介绍一下二维前缀和
    在这里插入图片描述
  • 我们使用一个数组 f [ i ] [ j ] f[i][j] f[i][j]存储二维前缀和,表示以 ( 1 , 1 ) (1,1) (1,1)为左上角顶点,以 ( i , j ) (i,j) (i,j)为右下角顶点,的矩形内部所有元素的和(包括边缘),如果我们想求出如上图,以 ( a , b ) (a,b) (a,b)为左上角顶点,以 ( c , d ) (c,d) (c,d)为右下角顶点的矩形内部所有元素之和,怎么求?很简单, f [ c ] [ d ] − f [ c ] [ b − 1 ] − f [ a − 1 ] [ d ] + f [ a − 1 ] [ b − 1 ] f[c][d]-f[c][b-1]-f[a-1][d]+f[a-1][b-1] f[c][d]−f[c][b−1]−f[a−1][d]+f[a−1][b−1]即可,因为左上角的矩形被减掉了两次
  • 那么我们怎么求 f [ i ] [ j ] f[i][j] f[i][j]呢?,根据左、右、左上三个位置的 f f f值即可求出,也就是 f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j − 1 ] − f [ i − 1 ] [ j − 1 ] + f [ i ] [ j ] f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+f[i][j] f[i][j]=f[i−1][j]+f[i][j−1]−f[i−1][j−1]+f[i][j],这里同样左上角被加了两次,所以需要减去一个
    明白二维前缀和之后我们再来看这道题就显得很简单了,我们只需要枚举每个矩形,查看所有情况就可以了,注意顶点上的 1 1 1不能算在答案里
  • 但是这样看时间复杂度似乎是 O ( n 2 m 2 ) O(n^2m^2) O(n2m2)的,对于 400 400 400的数据范围看起来好像不行,这道题目似乎有点离谱,好像 c f cf cf里面做这种剪枝的不太多,极端情况应该是过不了,但是有一种剪枝方法,我们扩展矩形的方式是固定左上角,根据右下角顶点往右下扩展,先右后下,那么如果当前矩形左边,上下两条边及矩形内部的操作次数已经大于当前答案,那么继续往右也不会得到更优的答案,所以这里 b r e a k break break掉,加这个小小的剪枝可以通过此题
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 500;
char mp[MAXN][MAXN];
int f[MAXN][MAXN];
int cal(int a, int b, int c, int d){
    return f[a][b] + f[c - 1][d - 1] - f[a][d - 1] - f[c - 1][b];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t, n, m;
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin >> mp[i][j];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + mp[i][j] - '0';
            }
        }
        int ans = 20;
        for(int x=1;x<=n;x++){
            for(int y=1;y<=m;y++){
                for(int i=x+4;i<=n;i++){
                    for(int j=y+3;j<=m;j++){
                        // cout << x << ' ' << y << ' ' << i << ' ' << j << '\n';
                        int jia_l = mp[x][y] + mp[i][y] - '0' - '0';
                        int jia_r = mp[i][j] + mp[x][j] - '0' - '0';
                        int wai = cal(i, j, x, y);
                        int nei = cal(i - 1, j - 1, x + 1, y + 1);
                        int len = i - x - 1;
                        int width = j - y - 1;
                        int r = cal(i, j, x, j) - jia_r;
                        int num = nei + 2 * width + len - (wai - nei - jia_l - jia_r - r);
                        if(ans < num) break;
                        ans = min(ans, nei + 2 * (len + width) - (wai - nei - jia_l - jia_r));
                        // cout << wai << ' ' << nei << ' ' << jia_l << ' ' << jia_r << '\n';
                    }
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

上几道二维前缀和的简单例题
https://www.luogu.com.cn/problem/P1719

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 150;
int f[MAXN][MAXN];
int cal(int a, int b, int c, int d){
    return f[c][d] - f[c][b - 1] - f[a - 1][d] + f[a - 1][b - 1];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin >> f[i][j];
            f[i][j] += f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1];
        }
    }
    int ans = INT_MIN;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=i;k++){
                for(int q=1;q<=j;q++){
                    ans = max(ans, cal(k, q, i, j));
                }
            }
        }
    }
    cout << ans;
    return 0;
}

http://47.110.135.197/problem.php?id=5182
http://47.110.135.197/problem.php?id=5183

这篇关于Codeforces Round #745 (Div. 2) C. Portal 二维前缀和简单总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!