题解 【AT2699 [ARC081D] Flip and Rectangles】

**题意** ： 给出一个 $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; } ```