网格问题

Published: November 13, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 最大权子矩形问题
• 二维最大面积子矩形问题
• 全0矩形问题
• 全0方形矩阵
• 01网格异或问题
  • 同值连通块
• 网格转换问题
• 互异矩形问题
• 最小和网格赋值方案

最大权子矩形问题

给定一个$n\times m$网格，每个网格上有一个整数，要求选择一个非空子矩形，要求子矩形中包含的数的总和最大。

我们可以暴力枚举子矩形的上下边界，现在的问题就是一个序列，要求求一段子序列使得总和最大，这是一个经典问题，可以$O(n)$求解。

整体时间复杂度为$O(n^2m)$（我们可以旋转整个网格得到时间复杂度$O(m^2n)$)。

二维最大面积子矩形问题

给定一个矩形大厅，大厅中共有$n$根柱子，第$i$根柱子的坐标为$(x_i,y_i)$，柱子很细，可以视作一个点。要求在大厅布置一个矩形舞台，要求舞台和柱子不能重合（允许落在边缘，但不允许落在内部），问舞台的最大面积。

提供一道题目。

可以发现舞台的边缘要么与大厅相接，要么与柱子相接。因此直接就给出了一个$O(n^5)$的算法。

我们可以暴力枚举矩形的上边界，之后在考虑不同的下边界。当上下边界固定的时候，落在上下边界中的点的横坐标记作$t_1,t_2,\ldots,t_k$，要让面积最大，这时候很显然问题等价于找到距离最大的一对相邻的横坐标。这个可以$O(n)$计算。于是时间复杂度优化到了$O(n^3)$。

下面我们考虑进一步优化，当下边界从$j$下移到$j-1$的时候，一些新的点会被加入考虑。实际上考虑加入一个新的点$m$，这个点左边横坐标为$l$，右边横坐标为$r$，其将原来某个连续的空间$[l,r]$切割为两部分$[l,m]$和$[m,r]$。这意味着相邻坐标最大距离有可能减小，减小不好处理，我们需要借助平衡树才好处理，这样的时间复杂度为$O(n^2\log_2n)$。

虽然区间分裂不好处理，但是如果我们反过来处理，我们从下向上枚举下边界，这时候就变成了一开始区间全部分裂，之后不断删除点，区间合并。这时候我们就可以很简单的维护最大区间，时间复杂度为$O(n^2)$。

全0矩形问题

题目1：给定一个$n\times m$网格，每个网格上写着数字0或1。要求选择一个全0矩形，满足矩形面积最大。

如果我们给0替换为1,1替换为负无穷，问题就变成了最大权子矩形问题，我们就有了$O(n^2m)$的算法。

我们可以暴力枚举子矩形的上边界$i$，并且对每个$j=1,\ldots,m$，记$f_i(j)$表示$(i,j)$上方的第一个1出现的纵坐标（如果不出现记做$n+1$)。我们知道一个最大面积子矩形必定不能再向上，左，右继续扩大，不能向上扩大是因为上方有1。我们分别考虑这个1出现的位置，其可能为$(f_i(j),j)$，对于给定1的位置，我们可以容易确定左右边界，左右边界可以通过递增队列来实现，因此对于给定$i$，我们可以$O(m)$算出相关的所有可能结果。

总的时间复杂度为$O(nm)$。

提供一道题目。

题目2：给定一个$n\times m$网格，每个网格上写着数字0或1。要求对于$1\leq i\leq n,1\leq j\leq m$输出$f(i,j)$，其中$f(i,j)$表示高为$i$宽度为$j$的全0矩形总数。

首先如果我们暴力枚举左上角顶点，可以得到$O((nm)^2)$的算法。

考虑枚举上下边界，我们可以发现一列可以被选择，当且仅当在上下边界内这一列都是$0$。这时候我们的到一个01序列。我们需要统计不同宽度的连续0序列的数目。我们可以将01序列划分为若干个不可扩增的0序列，并记录它们的长度为$w_1,\ldots,w_k$，记录$C(i)$表示$i$在$w$序列中出现的次数。记$g(i)$为长度为$i$的0序列数目，可以发现$g(i)=g(i+1)+\sum_{j=i}^m w_j$。这个我们可以通过后缀和可以$O(m)$求出。因此现在我们得到了$O(n^2m)$的算法。

接下来我们进一步优化。考虑我们处理了上边界为$U$，下边界为$D$的情况，这时候我们将$D$增大$1$，考虑会发生什么。我们可以发现一些$w$中的元素被分裂成两个，这对应于$C(i)$的常数次加减操作。并且每一列在这个过程中都最多仅贡献一次，因此仅考虑这些操作实际上是$O(m)$级别的。但是还有一个问题，我们在枚举下边界的时候每一行都需要复制$C$，这显然是很大的开销，我们可以通过维护前缀和的技术来实现，这样我们只需要$O(m)$级别的修改即可。还有一个问题就是对应不同的上边界我们需要维护不同的前缀和，但是由于我们最后只需要算出$C(i)$的总和而已，因此我们把这些前缀和数组合并在一起，一起维护即可。这样对于每个固定的上边界，我们的时间复杂度为$O(m)$。最后跑一次我们提到的计算$g$的算法，算出所有的$f(i,j)$即可。总的时间复杂度为$O(nm)$。

提供一道题目。

题目3：

全0方形矩阵

一个网格，每个网格上面写着数字0或1。一个方形矩形是全0的，当且仅当矩形中只包含数字0。

题目1：给定一个$n\times m$的$0,1$网格$G$，要求找到其中最大的全0方形矩形。如果无解，则输出$0$。

我们考虑以$(x,y)$为右下角的最大方形网格大小，记其为$f(x,y)$，如果$G_{i,j}=1$，则答案为$0$，否则为$\min(f(x-1,y),f(x-1,y-1),f(x,y-1))+1$。

证明可以通过上下界来证明。

时间复杂度为$O(nm)$。

题目2：给定一个$n\times m$的$0,1$网格$G$。之后要求做$k$次修改，第$i$次修改将某个位置的$0$改成$1$。要求在每次修改后输出当前最大的全0方形矩形的大小。其中$1\leq n, m, k\leq 2\times 10^3$。

提供一道题目。

首先增加$1$比较麻烦，我们逆向操作，先把所有操作执行完，之后逐步回退，这时候相当于把$1$改成$0$。

当删除一个$1$之后，考虑新的最大方形矩形的大小。如果增大，则最大方形矩形必定包含我们之前删除的点所在的行。

我们可以为每一列维护两个数组$U,D$，其中$U_{i,j}$表示从$(i,j)$向上移动第一个$1$的距离。同理$D_{i,j}$表示从$(i,j)$向下移动第一个$1$的距离。可以发现每一次修改后，我们仅需要更新一列，时间复杂度为$O(n)$。

之后我们尝试$max+1$是否存在，其中$max$表示已知最大全0方形矩形的大小。之后我们我们可以用遍历可能的最大矩形的右边界，同时用两个最小队列维护该行$U,D$的信息。一次判断的时间复杂度为$O(m)$。

考虑到判断最多只会发生$O(m+k)$次，因此总的时间复杂度应该为$O(nm+km)$。

01网格异或问题

题目1：给定一个大小为$n\times m$的01网格$A$。每次操作允许将某一行或某一列全部取反，问使得网格中所有元素变成$0$的最少操作次数，或者报告无解。

我们可以暴力枚举第一行是否需要取反，第一行确定，所有列是否需要翻转也同时确定了，同样的所有行也确定了。因总的时间复杂度为$O(nm)$。

同值连通块

同值连通块是指值相同且相邻的单元格并入同一个连通后得到。

题目1：给定一个大小为$n\times m$的01网格$A$。找到其中最大的子矩形，满足其中所有同值连通块都是一个矩形形状。其中$1\leq n,m\leq 1000$

如果某个子矩形$R$满足条件，那么上面条件等于$R$的所有$2\times 2$的子矩形的异或和都是$0$。我们可以先求出另外一个大小为$n-1\times m-1$的网格$B$，其中$B_{i,j}=\oplus_{i\leq x\leq i+1,j\leq y\leq j+1}A_{x,y}$。可以发现一个最大的子矩形，对应与$B$中的一个最大的全$0$矩阵，并加上尾部和右边一行。这个问题实际上是最大全0矩形问题，可以$O(nm)$解决。

题目2：给定一个大小为$n\times m$的01网格$A$。要求判断仅修改最多$k$个数的前提下，是否可以保证其中所有同值连通块都是一个矩形形状。其中$1\leq n,m\leq 200$，$0\leq k\leq 10$。

提供一道题目。

题目1已经提到过了$A$满足条件等于$A$的所有$2\times 2$的子矩形的异或和都是$0$。可以发现如果我们确定了第一行和第一列后，整个矩形都确定了，即确定两个序列$X,Y$，那么$A_{i,j}=X_i\oplus Y_j$。

由于$k$非常小，因此我们可以分情况讨论。

情况1：$n\leq k$，这时候暴力枚举所有的可能的$X$即可，$Y$可以贪心选择。时间复杂度为$O(nm2^n)$。

情况2：$n>k$，这时候至少有一行是不经过任何修改的。暴力枚举这一行，这一行一旦确定，$Y$也随之确定，之后其余行，就贪心选择使得这一行修改最少的方案。总的时间复杂度为$O(n^2m)$。

网格转换问题

问题1：给定两个大小为$n\times m$的网格$A,B$，给定$k$，要求每次选择$A$中连续的$k$个同行元素或同列元素，并修改一个任意值$v$。问是否可以通过一定的步骤，使得$A$转换为$B$。

提供一道题目。

首先我们可以将$A$和$B$都减去$B$，这时候$A$变成$A-B$，而$B=0$。我们现在希望做一些操作，使得$A$变成全$0$矩阵。如果$A$可以被转换，则称$A$是可零化的。

我们可以创建一个大小为$k\times k$的新的网格$C$，其中对于任意的$A$中下标$(i,j)$，我们将$A_{i,j}$加入到$C_{i\pmod k,j\pmod k}$中。我们实际上可以通过一些步骤将$A$的左上角的$k\times k$矩阵转换为$C$，同时其它部分转换为$0$，具体做法就是选择$A_{r,i}$到$A_{r,i-1+k}$之间所有元素增加$1$，选择$A_{r,i+1}$到$A_{r,i+k}$之间所有元素减少$1$，这等价于从$A_{r,i+k}$将一个$1$移动到$A_{r,i}$上。因此$C$能零化，则$A$也一定能零化。同理如果$A$能零化，那么将$A$中的操作，如果是选择行$r$，则在$C$中选择$r\pmod k$，如果选择列$c$，则在$C$中选择$c\pmod k$，修改的值不变，作用到$C$上去，此时$C$也同样能被零化。

因此$A$能被零化等价于$C$能被零化。最后考虑是否能零化$C$。这个问题等价于选择两个长度为$k$的向量$X,Y$，其中$C_{i,j}=X_i+Y_j$。我们可以枚举$X_0$，这时候就能确定$Y$，从而确定$X$。但是$X_0$可能性太多了，考虑$X_0$是一个可行解，那么$X_0+t$同样是一个可行解，因为我们只需要将$X$中所有元素都加上$t$，同时让$Y$中所有元素减少$t$即可得到一个新的可行解。故我们只要取$X_0=0$来测试即可。

时间复杂度为$O(nm)$。

问题2：给定两个大小为$n\times m$的网格$A,B$，给定$h,w$，要求每次选择$A$中大小为$h\times w$的子矩阵，将子矩阵中所有元素都修改一个任意值$v$。问是否可以通过一定的步骤，使得$A$转换为$B$。

记$R_{i,j}=A_{i,j}+A_{i,j+w}+A_{i,j+2w}+\ldots$，记$C_{i,j}=A_{i,j}+A_{i+h,j}+A_{i+2h,j}+\ldots$。可以发现每一次修改后，$R_{i,1},\ldots,R_{i,w}$任意两个元素的差值是不变的，同理$C_{1,j},\ldots,C_{h,j}$中任意两个元素的差值是不变的。简单记$\delta R_{i,j}=R_{i,j}-R_{i,1}$，同理记$\delta C_{i,j}=C_{i,j}-C_{1,j}$。可以发现一个网格的$(\delta R,\delta C)$是唯一的，并且两个可以相互转换的网格必须拥有相同的$(\delta R,\delta C)$。并且如果两个网格拥有相同的$(\delta R,\delta C)$，那么它们一定也是可以相互转换的，因为我们可以把左上角大小为$n-(h-1)\times m-(w-1)$的网格全部化零，此时剩下的元素是唯一确定的。

上面提供了一个$O(n\times m)$时间复杂度的算法来解决这个问题。

互异矩形问题

题目1：给定一个$n\times m$的矩形$A$，第$i$行第$j$列单元格包含一个整数$A_{i,j}$，要求找到其中最大面积的子矩形，满足矩形覆盖的元素两两不同。其中$1\leq n,m\leq 500$，且$1\leq A_{i,j}\leq 10^9$。

提供一道题目。

最简单的做法是暴力枚举所有子矩形，这样时间复杂度为$O(n^3m^3)$。

可以稍微优化一些，固定左上角，考虑不同的右下角，这样可以优化到$O(n^2m^2)$。

现在我们固定上边界，递增下边界。记$R(i)$表示以第$j$列为左边界，右边界的值，很显然$R(i)\leq R(i+1)$。考虑这时候我们下移下边界对$R(i)$带来的影响。这时候$R(i)$可能会减小。如何我们对每个单元格$(i,j)$预处理$left(i,j)$和$right(i,j)$，$left(i,j)$分别表示它左上角的所有值与它相同的单元格的最大$y$坐标，而$right(i,j)$则表示它的右上角的所有值与它相同的单元格的最小$y$坐标。这样我们下移下边界的时候，右边界的值就可以$O(m)$进行更新了。

现在的问题是如何维护$left(i,j)$和$right(i,j)$，直接计算比较复杂，需要为每个值维护一个单调队列。我们可以考虑上移上边界对$left(i,j)$的影响，此时它只可能增大。这时候我们可以$O(nm)$维护新的$left$值，$right$值的维护类似。

总的时间复杂度为$O(n^2m)$。

最小和网格赋值方案

要求找到一个$n\times m$的网格G，其中第$i$行的所有元素的异或值为$R_i$，第$j$列的所有元素的异或值为$C_j$。且要求所有元素的和最小。其中$1\leq n,m\leq 10^3$，$0\leq C_i,C_j\leq 10^9$。如果无解，则报告无解，否则输出任意一组可行解。

考虑到每个比特可以独立考虑，因此我们可以拆比特独立处理。

下面我们仅需要考虑$C_i,C_j$只可能是$0,1$的情况。

很显然有解的前提是$\oplus_{i=1}^nR_i=\oplus_{i=1}^mC_i$。之后我们会证明这个条件同时是充分的。容易发现和的一个下界为$\max(\sum_{i=1}^n R_i,\sum_{j=1}^mC_j)$。下面我们通过构造法在满足有解前提下一定可以达到下界。

不妨认为$A=\sum_{i=1}^n R_i\geq \sum_{j=1}^mC_j=B$，这时候$A,B$拥有相同的奇偶性，并且$R_1,\ldots,R_A=1$，$C_1,\ldots,C_B=1$。那么我们只需要设置$G_{1,1},G_{2,2},\ldots,G_{B,B},G_{B,B+1},G_{B,B+2},\ldots,G_{B,A}$为$1$即可。

上面我们提供了一个$O(nm\log_2M)$的算法。