题解 【AT2699 [ARC081D] Flip and Rectangles】
command_block
2021-05-01 18:04:07
**题意** : 给出一个 $n\times m$ 的 $01$ 矩阵。
每次操作可以将一行或一列取反,可以进行任意多次操作,问矩阵中全 $1$ 矩形面积的最大值。
$n,m\leq 2000$ ,时限$\texttt{2s}$。
------------
首先考虑如何判定一个矩形经过操作能否变为全 $1$。
先观察一些性质 :
- 若某个矩形能被操作为全 $1$ ,那么其任意子矩形也一定可以。
- 行列任意交换不影响某个矩形是否能变为全 $1$。
任选位置 $[x,y]$ ,若 $A[x,y]=0$ 则将整个矩形取反,这样总有 $A[x,y]=1$。
先查看第 $x$ 行和第 $y$ 列,若某个数为 $0$ ,则翻转对应 行/列。
在这之后,若做其他操作,则第 $x$ 行和第 $y$ 列必被破坏。所以不能进一步操作,检查此时矩阵是否全黑即可。
这等价于,对于位置 $A[i,j]$ ($i\neq x,j\neq y$),检查 $! A[x,y],!A[x,j],!A[i,y],A[i,j]$ 的异或值是否为 $1$。
也即 $A[x,y],A[x,j],A[i,y],A[i,j]$ 的异或值是否为 $0$。
由于 $[x,y]$ 也是任选的,我们得到一条性质 : 任意一个子矩形的四个角的异或和为 $0$。
这同时也是充要条件。
> 在转化充要条件时,判定算法可能是构造性的。此时要尽量多想“有没有其他方法也可以完成构造?”,以得到更多性质。
> 比方说,在本题中,若直接选择第一行第一列开始构造(而不是任意的 $[x,y]$)就很难得到这个性质。
该条件依然难以维护,考虑进行简化 : 能否只考虑一小部分矩形的约束呢?
条件可以看作若干异或方程组,线性相关的方程组显然是无用的。
略微手玩方程之间的线性相关模式后,可以发现,只需要考虑所有的 $2\times 2$ 矩形,因为更大的矩形的四个角都可以用内部所有的 $2\times 2$ 矩形异或出来。
于是,对每个 $2\times 2$ 矩形,查看内部是否有奇数个 $1$ 。若是,则称为坏矩形。
若一个大矩形包含了坏矩形,则无法变为全 $1$ ,反之可以。
至此,我们将原问题转化为了最大全 $1$ 矩形问题。
(注意,长或宽为 $1$ 的矩形总是好的)
这是经典问题,这里用悬线法解决。
复杂度 $O(n^2)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 2050
using namespace std;
const int mod=998244353;
int n,m,l[MaxN][MaxN],r[MaxN][MaxN],up[MaxN][MaxN];
char a[MaxN][MaxN];
int main()
{
scanf("%d%d",&n,&m);
int ans=max(n,m);
for (int i=1;i<=n;i++){
scanf("%s",a[i]+1);
for (int j=1;j<=m;j++)
a[i][j]=(a[i][j]=='#');
}
n--;m--;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
a[i][j]=!((a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1])&1);
l[i][j]=r[i][j]=j;
}
for (int i=1;i<=n;i++){
for (int j=2;j<=m;j++)
if (a[i][j]&&a[i][j-1])
l[i][j]=l[i][j-1];
for (int j=m-1;j;j--)
if (a[i][j]&&a[i][j+1])
r[i][j]=r[i][j+1];
for (int j=1;j<=m;j++)
if (a[i][j]){
if (a[i-1][j]){
l[i][j]=max(l[i][j],l[i-1][j]);
r[i][j]=min(r[i][j],r[i-1][j]);
}up[i][j]=up[i-1][j]+1;
ans=max(ans,(r[i][j]-l[i][j]+2)*(up[i][j]+1));
}
}printf("%d",ans);
return 0;
}
```