Codeforces Round #745 (Div. 2) C. Portal

大意：给定一个 n * m 的01矩阵。每次可以把把一个格子的0变1或者把1变0.问最少需要多少次操作可以使得其存在至少一个 a*b的子矩阵，满足四个角上的无限制，矩阵四条边必须是1，内部必须是0。其中a,b满足 a>=5,b>=4。
数据范围 5<=n<=400,4<=m<=400。
思路：C题没写出，B忘记讨论k=0的情况，被hack了。寄！！！
先不考虑具体前缀和实现的细节，很容易想到的一个思路，搞个二维前缀和然后枚举矩阵左上和右下的端点，时间复杂度 O ( n 4 ) O(n^4) O(n4) 显然不太行。所以我们接下来就是想想怎么优化。只要想办法去掉一维就够了。我们想到只要确定了矩阵的上下边界，那么对于左右边界的枚举其实就是一维的寻找长度>=b的连续区间的最值问题了，这是个经典问题：通过维护前缀或后缀最值来实现。记sum[x]为从1-x需要修改的次数，那么[l,r] 的修改次数即为sum[r]-sum[l-1]。当我们确定了 l 的时候，向后枚举r，维护最小值，找到最小的 sum[r]。所以我们可以提前预处理出后缀最小值。就可以省掉枚举 r 的时间复杂度。总的时间复杂度 O ( n 3 ) O(n^3) O(n3)。但是比较麻烦的一点，怎么去搞前缀和进而可以求任意一个子矩阵的修改次数呢？麻烦的地方在于对于矩阵的四条边的处理。根据我们上面的分析，对于每次我们固定左边界去枚举右边界，矩形的左边界的修改次数是固定的，我们查询的是左边界 右边的部分，我们可以把左边单独考虑这样就很容易计算了，在维护前缀和的时候把左边界当成和中间的部分一块算。
代码如下:

#include 
using namespace std;
const int N=410;
char g[N][N];
int sum[N][N],n,m,f[N];
int getsum(int lx,int ly,int rx,int ry)
{
    return sum[rx][ry]-sum[rx][ly-1]-sum[lx-1][ry]+sum[lx-1][ly-1];
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            sum[i][j]=0;

    for(int i=1;i<=n;i++)cin>>(g[i]+1);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(g[i][j]=='1');

    int mi=654321;

    for(int i=1;i<=n;i++)
        for(int j=i+4;j<=n;j++)
        {
            for(int k=4;k<=m;k++)
                f[k]=getsum(i+1,1,j-1,k-1)+(k-1)*2-getsum(i,1,i,k-1)-getsum(j,1,j,k-1)+j-i-1-getsum(i+1,k,j-1,k);

            for(int k=m-1;k>=4;k--)f[k]=min(f[k],f[k+1]);

            for(int k=1;k+3<=m;k++)
            {
                int t=f[k+3]-(getsum(i+1,1,j-1,k)+k*2-getsum(i,1,i,k)-getsum(j,1,j,k))+j-i-1-getsum(i+1,k,j-1,k);
                mi=min(mi,t);
            }

        }
    cout<>_;
    while(_--)solve();
    return 0;
}