[数据结构与算法]Codeforces Round #745 (Div. 2) C. Portal 二维前缀和简单总结

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

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